前言:

这篇文章还是是为了帮助一些

像我这样的菜鸟

找到简单的题解

问题描述:

输入格式

输出格式

8
0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0
1 0 0 0 0 0 1 1
0 1 0 0 0 1 0 0
0 1 0 0 0 1 0 0
0 0 0 1 1 0 0 0
0 0 1 0 0 0 0 1
0 0 1 0 0 0 1 0

1-2-3-4-5-7-8-6

问题提示

问题解析:

只需要把上一题的DFS改为BFS即可

非常简单

直接上代码了

图的遍历 深度优先遍历(爱思创)_吾乃狙击神蛐的博客-CSDN博客

代码BFS部分: 

queue<int> q;
void bfs(int x)
{
	vis[x]=1;
	q.push(x);//入队
	while(!q.empty())//判空
	{
		int cur=q.front();//存储队首
		for(int i=1;i<=n*2;i++)
		{
			if(g[cur][i]==1 && vis[i]==0)
			{
				q.push(i);
				vis[i]=1;//打标记
			}
		}
		if(q.front()!=1) cout<<"-"<front();//输出答案
		q.pop();//别忘了出队
	}
	cout<
	return ;
}

完整代码:

#include
using namespace std;
int g[1001][1001],vis[1001];
int n,m;
queue<int> q;
void bfs(int x)
{
	vis[x]=1;
	q.push(x);
	while(!q.empty())
	{
		int cur=q.front();
		for(int i=1;i<=n*2;i++)
		{
			if(g[cur][i]==1 && vis[i]==0)
			{
				q.push(i);
				vis[i]=1;
			}
		}
		if(q.front()!=1) cout<<"-"<front();
		q.pop();
	}
	cout<
	return ;
}
int main()
{
	cin>>n;
	int x,y;
	for(int j = 1 ; j <= n ;j++)
	{
		for(int i = 1 ; i <= n ;i++)
		{
			cin>>g[j][i];//模仿上一题输入
		}	
	}
	cout<<1;
	bfs(1);
	return 0;
}

如果BFS不熟可以看我之前的文章

c++二叉树BFS3题解（爱思创）_吾乃狙击神蛐的博客-CSDN博客

AC