广度优先搜索

广度优先搜索(Breadth-First Search, BFS, 台湾称“横向优先搜寻”)是最简单的图搜索算法之一。广度优先搜索的特点是总是沿已发现与未发现的边界,向外依次扩展。设起始节点为s,则广度优先搜索算法首先会发现与s距离为k的所有结点后,才会发现与s距离为k+1的结点。
广度优先搜索在运行过程中将结点标识为三种状态:

  • 白色:未被发现的结点;
  • 灰色:已被发现,但与其相连的结点尚未全部发现的结点(下一轮进行发现的结点,也是发现结点集的边界);
  • 黑色:已被发现,且与之相连的其他结点也已经发现。

广度优先搜索因为存在单一的起始结点s,因此整个发现过程可以看作是以s为根节点的一棵树,称为广度优先树,广度优先搜索的过程也是建立一棵以s为根的广度优先树的过程。
广度优先树中对每个结点u记录三种信息:

  • π[u]:广度优先树中u的父结点,意味着u第一次被发现时所通过的上一级结点;
  • d[u]:u与根节点s的距离,如果是无权图,也是su的最短距离;
  • color[u]:u结点的颜色。

设图G = (V, E)V是顶点集,E是边集。s是起始节点。
则广度优先搜索(Breadth-First Search, BFS)算法如下:
[code=’c#’]
// 初始化整个图(除去起始结点s)
foreach(Vertex u in V[G] – {s})
{
u.Color = BFSColor.WHITE;
u.D = int.MaxValue;
u.π = null;
}

// 设置起始结点s
s.Color = BFSColor.GRAY;
s.D = 0;
s.π = null;

// 初始化一个队列
Queue q = new Queue();
q.Enqueue(s);
while(q.Count > 0)
{
Vertex u = q.Dequeue();
foreach(Vertex v in u.Neighbors)
{
if(v.Color == BFSColor.WHITE)
{
v.Color = BFSColor.GRAY;
v.D = u.D + 1;
v.π = u;
q.Enqueue(v);
}
}
u.Color = BFSColor.BLACK;
}
[/code]
广度优先搜索(Breadth-First Search, BFS)的算法复杂度是O(V+E),其中O(V)时间用于第一步初始化,O(E)时间用于遍历(因为每个结点的邻接表只会访问一次)。

推荐文章

发表评论