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

在广度优先搜索中,要发现与起点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();

}

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

你也可能喜欢

发表评论