图论基础——遍历图的BFS

1.问题分析

续上一篇博客，用DFS遍历图：图论基础——遍历图的DFS

同时我们也可以用BFS来对这个图进行遍历，遍历的时间戳标注在上面：

2.算法设计 

 利用广度优先搜索来遍历这个图的过程如下：

首先以一个未被访问过的顶点作为起始顶点，比如1号顶点作为起点.再将一号顶点放入队列中，然后将1号顶点相邻的未访问过的顶点即2、3、5号顶点一次再放入队列中，如下图：

接下来再将二号顶点相邻的未被访问过的4号顶点加入到队列中：

至此，所有顶点都被遍历了，BFS结束。

3.源代码 

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N=111;
const int INF=9999999;
int main()
{
    int edge[N][N];
    int marked[N]= {0};
    int n;
    int m;
    int point_a;
    int point_b;
    int cur;
    int que[11111];
    int head;
    int tail;
    cout << "请输入顶点个数n和边的条数m："<< endl;
    cin >> n>> m;
    //初始化
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i==j)
            {
                edge[i][j]=0;
            }
            else
            {
                edge[i][j]=INF;
            }
        }
    }
    cout << "请输入连接边的两个顶点：" << endl;
    for(int i=1; i<=m; i++)
    {
        cin >> point_a >> point_b;
        edge[point_a][point_b]=1;
        edge[point_b][point_a]=1;
    }
    //队列初始化
    head=1;
    tail=1;
    que[tail]=1;
    tail++;
    marked[1]=1;
    while(head<tail && tail<=n)
    {
        cur=que[head];//当前访问的结点
        for(int i=1; i<=n; i++)
        {
            if(edge[cur][i]==1 && marked[i]==0)
            {
                que[tail]=i;
                tail++;
                marked[i]=1;
            }
            if(tail > n)
            {
                break;
            }
        }
        head++;//出列
    }
    cout << "遍历结点的顺序是："<< endl;
    for(int i=1; i<tail; i++)
    {
        cout <<que[i];
    }
    cout << endl;
    return 0;
}

 

4.测试结果