bfs即广度优先搜索，等同于树的层序遍历，下面用一个题目来讲解

题目：图的广度优先遍历

问题描述

已知无向图的邻接矩阵，以该矩阵为基础，给出广度优先搜索遍历序列，并且给出该无向图的连通分量的个数。在遍历时，当有多个点可选时，优先选择编号小的顶点。（即从顶点1开始进行遍历）

输入格式

第一行是1个正整数，为顶点个数n（n<100），顶点编号依次为1，2，…，n。后面是邻接矩阵，n行n列。

输出格式

共2行。第一行输出为无向图的广度优先搜索遍历序列，输出为顶点编号，顶点编号之间用空格隔开；第二行为无向图的连通分量的个数。

样例输入

6

0 1 0 0 0 0

1 0 0 0 1 0

0 0 0 1 0 0

0 0 1 0 0 0

0 1 0 0 0 1

0 0 0 0 1 0

样例输出

1 2 5 6 3 4

2

 

先说一下核心部分——bfs函数

 1 void bfs(int k){
 2     queue<int> Q;//初始化
 3     Q.push(k);
 4     while(!Q.empty())
 5     {
 6         int p=Q.front();
 7         vis[p]=1;
 8         for(int i=1;i<=n;i++)
 9         {
10             if(grid[p][i]==1&&vis[i]==0)
11             {
12                 Q.push(i);
13             }
14         }
15         cout<<p<<" ";
16         Q.pop();
17     }
18 }

一开始我是这么写的，提交oj只有50分，我又读了一遍题，确定没有多组数据，输出符合要求，不是无向图需要存双相边的问题

乍一看没有什么问题，定义Q，点入队列，然后队列非空循环，取出队首元素，标记访问，把其他和它相连但是没有访问过的顶点入队，弹出队首元素。样例也通过了。但是对于一个3*3的强联通图，它会把3输出2遍。

原因就是在取出队首元素后，对于和它相邻且为抵达的节点我们没有标记访问就直接入队，这是有问题的，在1节点出队后，队首元素是2，2 3是有边的，但是我们vis【3】还是标记为未访问过，因此3又被入一次队

解决的办法就是在取出队首元素的时候就把所有与之相联的节点都打上标记

 1 void bfs(int k){
 2     queue<int> Q;
 3     Q.push(k);
 4     while(!Q.empty())
 5     {
 6         int p=Q.front();
 7         vis[p]=1;
 8         for(int i=1;i<=n;i++)
 9         {
10             if(grid[p][i]==1&&vis[i]==0)
11             {
12                 Q.push(i);
13                 vis[i]=1;//修改后新加的代码
14             }
15         }
16         cout<<p<<" ";
17         Q.pop();
18     }
19 }

至此我们可以总结一下bfs函数的通用模板

 1 void bfs(int k){
 2     vis[k]=1; 
 3     queue<int> Q;
 4     Q.push(k);
 5     
 6     while(!Q.empty())
 7     {
 8         int p=Q.front();//取出队首元素 
 9     
10         for(int i=1;i<=n;i++)//利用队首元素进行扩展，并打上标记 
11         {
12             if(grid[p][i]==1&&vis[i]==0)
13             {  
14                 Q.push(i);
15                 vis[i]=1;            
16             }
17         }
18         Q.pop();//弹出没有用的队首 
19     }
20 }