数据结构-图的遍历——BFS广度优先搜索-题解（C++代码）

解题思路:无非就是根据0到3，四个数字结点的连结方式来，用广度优先搜索进行遍历
//    0 1 2 3               0
// 0 0 0 0 1                |
// 1 0 0 1 1               3—1
// 2 0 1 0 1                |
// 3 1 1 1 0               2

第一层0，第二层3，第三层1，2

（1）先从0开始遍历，搜索和0连结并未遍历过的，0是本身，1未连结，2未连结，3连结且未遍历过

（2）0遍历完了，丢出去，将0下一层遍历到的3扔进去，准备开始搜索

（3）3开始搜索，0连结但遍历过了，1连结且未遍历过，2连结且未遍历过，3是本身，搜索完成

（4）3遍历完了，丢出去，将3下一层遍历到的1和2扔进去，准备开始搜索先扔进去的1

（5）1开始搜索，0未连结，1是本身，2未连结，3连结但遍历过了，搜索完成

（6）1遍历完了，丢出去，1没有下一层搜索到的结点，不管他

（7）2开始搜索，0未连结，1未连结，2是本身，3连结但遍历过了，搜索完成，没有要扔进去的，丢出去

（8）2遍历完了也没有要搜索的，丢出去，队列已空，广搜遍历结束。

对于每个遍历的结点，每次要做的事情，我们就可以将其加入代码来实现我们所需要的功能

参考代码:

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=100+5;
int map[maxn][maxn];       // 结点连接图
bool vis[maxn];                // 结点是否已经遍历过
int n;                               // 几个结点
void bfs(){
    queue<int>q;           // 遍历的队列
    q.push(0);                 // 从0开始
    vis[0]=true;              // 0遍历过
    cout<<"0"<<" ";      // 遍历0要做的事情：将0打印出来
    while(!q.empty()){     // 每次搜索有下一层（即队列不为空时）一直遍历搜索
        int now=q.front();   // 提取该结点并搜索
        for(int i=0;i<n;i++){   // 搜索每个结点
            if(!vis[i] && map[now][i]){  // 每个结点是否遍历过或者与其连结
                q.push(i);                // 连结就遍历该结点并作为下一层进入队列
                cout<<i<<" ";         // 做遍历要做的事情：将结点打印出来
                vis[i]=1;                  // 别忘了设置已经遍历过
            }
        }
        q.pop();                            // 遍历完了就把当前已经遍历过的扔掉
    }
}
int main()
{
    memset(vis,0,sizeof(vis));      // 每个结点还没遍历过
    while(cin>>n){                          // 输入结点的连结情况
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>map[i][j];
            }
        }
        bfs();                                      // 开始广搜遍历
        cout<<endl;
    }
    return 0 ;
}