广度优先搜索,与深度优先相对,就是一级一级地,先把同级的所有结点都访问一遍,再访问下一级的结点。
在广度优先搜索中,要发现与起点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();
}