当前位置: 代码迷 >> 综合 >> 图的遍历之深度优先
  详细解决方案

图的遍历之深度优先

热度:97   发布时间:2024-01-14 21:56:29.0
#include<stdio.h>
int book[101],sum,n,e[101][101];
void dfs(int cur)//cur是当前所在顶点的编号;
{printf("%d ",cur);sum++;//每访问一个顶点,sum加一if(sum==n)  return ;//所有顶点都已经访问则直接退出for(int i=0;i<=n;i++)//从一号顶点到n号顶点依次尝试,看哪些顶点与当前顶点cur有边相连;{//看看当前顶点cur的到顶点是否有边,并判断顶点i是否已经访问过了if(e[cur][i]==1&&book[i]==0){book[i]=1;//标记顶点i已经访问过了;dfs(i);//从顶点i出发再继续遍历}}return;
}
int main()
{int i,j,m,a,b;scanf("%d%d",&n,&m);//初始化矩阵for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(i==j)  e[i][j]=0;else e[i][j]=0x3f3f3f3f;//读入顶点的边for(i=1;i<=m;i++){scanf("%d%d",&a,&b);e[a][b]=e[b][a]=1;//这里是无向图}//从一号城市出发book[1]=1;//标记一号已经遍历访问过了dfs(1);//从一号开始遍历
}


  相关解决方案