算法与数据结构之广度优先搜索

广度优先搜索，与深度优先相对，就是一级一级地，先把同级的所有结点都访问一遍，再访问下一级的结点。

在广度优先搜索中，要发现与起点s距离为k+1的点，就要先发现所有距离为k的点。因此，可以依次求出起点到各顶点的最短距离。

广度优先搜索

在下述算法中，将各顶点v到起点s的距离存储在d[v]中。

1、将起点s放入队列Q中（访问）

2、只要Q不为空，就循环执行以下的处理：

·从Q取出顶点u进行访问（访问结束）

·将与u相邻的未访问结点v放入Q，同时将d[v]更新为d[u]+1

和上一篇将深度优先搜索的文章一样，我们用三种颜色来表示结点的状态。

白色：未访问

灰色：正在访问中

黑色：访问完毕

---

怎么存储接下来要访问的结点呢？

这就需要用到队列。每次发现新的未访问结点，就压入队列，然后当当前结点的所有未访问相邻节点均被访问之后，就把当前结点丢弃，再取出下一个结点进行访问。接下来就是重复上面的过程，直到队列为空，访问结束。

分析

邻接矩阵实现的深度优先搜索算法中，程序要调查每个结点是否与其他所有顶点相邻，因此时间复杂度为O(N²)，不适用于较大规模的图

题目：

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C

实现代码：

#include<bits/stdc++.h>
using namespace std;
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n;
int color[MAX+1];
int M[MAX+1][MAX+1];
int d[MAX+1];


void bfs()
{
    for(int i=0;i<=n;i++)
        d[i] = -1;
    queue<int>q;
    color[1] = GRAY;
    q.push(1);
    d[1] = 0;


    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        color[u] = BLACK;
        for(int i=1;i<=n;i++)
        {
            if(color[i]==WHITE&&M[u][i]==1)
            {
                q.push(i);
                color[i] = GRAY;
                d[i] = d[u] + 1;
            }
        }
    }

    for(int i=1;i<=n;i++)
        cout<<i<<" "<<d[i]<<endl;
}

int main()
{
   cin>>n;
   for(int i=0;i<n;i++)
   {
        int u,k;
        cin>>u>>k;
        for(int j=0;j<k;j++)
        {
            int v;
            cin>>v;
            M[u][v] = 1;
        }
   }

   bfs();

}

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~