什么是广度优先搜索？

欢迎大家来到IT世界,在知识的湖畔探索吧!

什么是广度优先搜索？

广度优先搜索（又称宽度优先搜索）算法的核心思想是：初始化，生成第一层结点，检查目标结点是否在这些第一层结点中，若没有，再将所有第一层的结点逐一扩展（即其后继结点），得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再逐一扩展第二层的所有结点……，如此依次扩展，检查下去，直到发现目标结点为止。即：

1. 从图中的某一顶点 V0​​ 开始，先访问 V​0​​；
2. 访问所有与 V​0​​ 相邻接的顶点 V​1​​，V​2​​，……，V​t​​；
3. 依次访问与 V​1​​，V​2​​，……，V​t​​ 相邻接的所有未曾访问过的顶点；
4. 循此以往，直至所有的顶点都被访问过为止。

这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。

欢迎大家来到IT世界,在知识的湖畔探索吧!

灰色格子表示墙，不可以走；其它颜色格子可以走。

图的广度优先遍历

题目描述

读入一个用邻接矩阵存储的无向图，输出它的广度优先遍历序列。

输入格式

第1行1个正整数n，表示图中顶点数，2≤n≤100；

接下来的n行是一个n×n的邻接矩阵，a[i][j]=1表示顶点i和顶点j之间有直接边相连，a[i][j]=0表示没有直接边相连。保证i=j时，a[i][j]=0，并且a[i][j]=a[j][i]。

输出格式

输出1~n的某一种排列，表示从顶点1开始，对该图进行宽度优先遍历得到的顶点序列，每两个数之间用一个“-”分隔。

样例

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 

欢迎大家来到IT世界,在知识的湖畔探索吧!

欢迎大家来到IT世界,在知识的湖畔探索吧!1-2-3-4-5-7-8-6 

提示

参考程序：数组模拟队列

#include 
  
    #include 
   
     using namespace std; const int N = 105; int n; int g[N][N]; int q[N]; bool book[N]; bool is_first = true; void bfs(){ int hh = 0, tt = -1; q[++tt] = 1; book[1] = true; while(hh <= tt){ int t = q[hh++]; if(is_first){ cout << t; is_first = false; } else cout << "-" << t; for(int i = 1; i <= n i ifgti booki qtt='i;' booki='true;' int main cin>> n; for(int i = 1; i <= n; i++) for(int j = 1; j <= n j cin>> g[i][j]; bfs(); return 0; }