BFS 宽度优先搜索
BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。
BFS特点:每次搜索指定点,并将其所有未访问过的邻近节点加入搜索队列,循环搜索过程直到队列为空。
算法描述如下:
(1)将起始节点放入队列尾部
(2)While(队列不为空)
取得并删除队列首节点Node
处理该节点Node
把Node的未处理相邻节点加入队列尾部
之所以称之为宽度优先算法,是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展,
s为初始点 while 从Q中选一点 /* 选最先插入进Q的点,则为广度遍历,可以说先进先出。*/ /* 选最后插入进Q的点,则为深度遍历,可以说后进先出。 */ if then /* N(v):v的邻接点 */ else return H=(R,T)
procedure BFS(G,S);
begin
1. for 每个节点u∈V[G]-{s} do
begin
2. color[u]←White;
3. d[u]←∞;
4. π[u]←NIL;
end;
5. color[s]←Gray;
6. d[s]←0;
7. π[s]←NIL;
8. Q←{s}
9. while Q≠φ do
begin
10. u←head[Q];
11. for 每个节点v∈Adj[u] do
12. if color[v]=White then
begin
13. color[v]←Gray;
14. d[v]←d[v]+1;
15. π[v]←u;
16. Enqueue(Q,v);
end;
17. Dequeue(Q);
18. color[u]←Black;
end;
end;
过程BFS按如下方式执行,
第1-4行置每个结点为白色,置d[u]为无穷大,每个结点的父母置为NIL,
第5行置源结点S为灰色,即意味着过程开始时源结点已被发现。
第6行初始化d[s]为0,第7行置源结点的父母结点为NIL,第8行初始化队列0,使其仅含源结点s,以后Q队列中仅包含灰色结点的集合。
程序的主循环在9-18行中,只要队列Q中还有灰色结点,即那些已被发现但还没有完全搜索其邻接表的结点,循环将一直进行下去。
第10行确定队列头的灰色结点为u。第11-16行的循环考察u的邻接表中的每一个顶点v。如果v是白色结点,那么该结点还没有被发现过,算法通过执行第13-16行发现该结点。首先它被置为灰色,距离d[v]置为d[u]+1,而后u被记为该节点的父母,最后它被放在队列Q的队尾。当结点u的邻接表中的所有结点都被检索后,
第17-18行使u弹出队列并置成黑色。
C++ 的实现