#include<stdio.h>
#define INF 0x3f3f3f3f
int main()
{int i,j,m,n,a,b,cur,book[101]= {0},e[101][101];int que[10001],head,tail;scanf("%d%d",&n,&m);
//初始二维矩阵;for(i=1; i<=n; i++)for(j=1; j<=n; j++)if(i==j)e[i][j]=0;elsee[i][j]=INF;
//读入顶点之间的边;for(i=1; i<=m ; i++){scanf("%d %d",&a,&b);e[a][b]=e[b][a]=1;//这里是无向图,所以需要将e【b】【a】也赋值为1;}
//队列初始化;head=1;tail=1;
//从1号顶点出发,将一号顶点加入队列que[tail]=1;tail++;book[1]=1;//标记1号顶点已访问;//当队列不为空时候循环;while(head<tail){cur=que[head];//当前正在访问的顶点编号;for(i=1; i<=n; i++)//从1到n依次尝试{if(e[cur][i]==1&&book[i]==0)//判断从顶点cur到i是否有边,并判断顶点i是否已经访问过;{
//如果从顶点到顶点i有边,并且顶点i没有被访问过,将顶点i入队;que[tail]=i;tail++;book[i]=1;//表示顶点i已经被访问过;}}
//如果tail大于n说明所有顶点都已经被访问过if(tail>n){break;}head++;//注意这个地方,千万不要忘记当一个顶点扩展结束后,head++,然后才能继续往下拓展}for(i=1; i<tail ; i++)printf("%d ",que[i]);}
详细解决方案
图的遍历之广度优先
热度:61 发布时间:2024-01-14 21:56:41.0
相关解决方案