问题标题: 酷町堂：6153 无向图的广度优先搜索

6153   无向图的广度优先搜索

经验值：0 时间限制：1000毫秒

题目描述 Description

给出一个无向图，求出其广度优先搜索的结果。要求：同一层上的所有结点，按照编号从小到大输出。

输入描述 Input Description

第一行，两个整数，n m，表示图中有n个点，m条边
接下来m行，每行两个整数，x y，表示x和y之间存在一条边
再接下来一行，一个整数，st，表示起点编号

输出描述 Output Description

按顺序打印从st可以到达的所有点的编号，之间用空格隔开

样例输入 Sample Input

6 6 1 3 1 2 2 5 2 4 3 5 5 6 2

样例输出 Sample Output

2 1 4 5 3 6

数据范围及提示 Data Size & Hint

n <= 100

/*
广度优先遍历的思想是：首先以一个未被访问过的点作为起点，访问其相邻的所有点， 
然后在这些点中再访问与其相邻的所有点，直到所有点都被访问完为止 











*/
#include <iostream>
using namespace std;
int n,m,st,a,b,cur,book[1005],g[1005][1005];
int que[10005],head,tail=1,flag;
void bfs()
{
	head=1;
	que[tail++]=st;//将st号顶点加入队列 
	book[st]=1;
	while(1)
	{
		cur=que[head];//当前正在访问的节点编号
		for(int i=1;i<=n;i++)
		{
			if(g[cur][i]==1&&!book[i])//判断cur到i是否直达，并且i还要没有访问过 
			{
				que[tail++]=i;
				book[i]=1;
			}
			//如果tail==n+1，则所有的点都被访问 
			if(tail==n+1)//为什么是n+1，因为tail是指向队列的末尾的下一个元素的位置，元素1~n 
			{
				flag=1;
				break;
			}
		}
		if(flag==1)break;
		head++;
	}
	return ;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j)g[i][j]=0x3f3f3f3f;
		}
	}
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		g[a][b]=g[b][a]=1;
	}
	cin>>st;
	bfs();
	for(int i=1;i<tail;i++)
	{
		cout<<que[i]<<" ";
	}
	return 0;
}

Runtime Error 80分

求改正！

袁瑞琳在2021-08-25 16:41:02追加了内容

题号有错，是无向图的广度优先搜索