经典算法研究系列；BFS和DFS优先搜索算法

2022-06-20 14:24| 来源: 网络整理| 查看: 265

2015-01-24

328

经典算法研究系列；BFS和DFS优先搜索算法

关于此类BFS和DFS算法的文章，很多。但，都说不出个所以然来。读完此文，我想，你对图的广度优先搜索和深度优先搜索定会有个通通透透，彻彻底底的认识。

咱们由BFS开始：首先，看下算法导论一书关于此BFS 广度优先搜索算法的概述。算法导论第二版，中译本，第324页。广度优先搜索（BFS）在Prime最小生成树算法，和Dijkstra单源最短路径算法中，都采用了与BFS 算法类似的思想。

//u 为 v 的先辈或父母。 BFS(G, s) 1 for each vertex u ∈ V [G] - {s} 2 do color[u] ← WHITE 3 d[u] ← ∞ 4 π[u] ← NIL //除了源顶点s之外，第1-4行置每个顶点为白色，置每个顶点u的d[u]为无穷大， //置每个顶点的父母为NIL。 5 color[s] ← GRAY //第5行，将源顶点s置为灰色，这是因为在过程开始时，源顶点已被发现。 6 d[s] ← 0 //将d[s]初始化为0。 7 π[s] ← NIL //将源顶点的父顶点置为NIL。 8 Q ← Ø 9 ENQUEUE(Q, s) //入队 //第8、9行，初始化队列Q，使其仅含源顶点s。

10 while Q ≠ Ø 11 do u ← DEQUEUE(Q) //出队 //第11行，确定队列头部Q头部的灰色顶点u，并将其从Q中去掉。 12 for each v ∈ Adj[u] //for循环考察u的邻接表中的每个顶点v 13 do if color[v] = WHITE 14 then color[v] ← GRAY //置为灰色 15 d[v] ← d[u] + 1 //距离被置为d[u]+1 16 π[v] ← u //u记为该顶点的父母 17 ENQUEUE(Q, v) //插入队列中 18 color[u] ← BLACK //u 置为黑色

由下图及链接的演示过程，清晰在目，也就不用多说了：

ok，不再赘述。接下来，具体讲解深度优先搜索算法。深度优先探索算法 DFS //u 为 v 的先辈或父母。 DFS(G) 1 for each vertex u ∈ V [G] 2 do color[u] ← WHITE 3 π[u] ← NIL //第1-3行，把所有顶点置为白色，所有π 域被初始化为NIL。 4 time ← 0 //复位时间计数器 5 for each vertex u ∈ V [G] 6 do if color[u] = WHITE 7 then DFS-VISIT(u) //调用DFS-VISIT访问u，u成为深度优先森林中一棵新的树 //第5-7行，依次检索V中的顶点，发现白色顶点时，调用DFS-VISIT访问该顶点。 //每个顶点u 都对应于一个发现时刻d[u]和一个完成时刻f[u]。 DFS-VISIT(u) 1 color[u] ← GRAY //u 开始时被发现，置为白色 2 time ← time +1 //time 递增 3 d[u] 分享收藏微信二维码