经典算法研究系列；BFS和DFS优先搜索算法-CDA数据分析师官网

热线电话：13121318867

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

2015-01-24

经典算法研究系列；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] <-time                   //记录u被发现的时间
4 for each v ∈ Adj[u]   //检查并访问 u 的每一个邻接点 v
5       do if color[v] = WHITE            //如果v 为白色，则递归访问v。
6             then π[v] ← u                   //置u为 v的先辈
7                         DFS-VISIT(v)        //递归深度，访问邻结点v
8 color[u] <-BLACK         //u 置为黑色，表示u及其邻接点都已访问完成
9 f [u] ▹ time ← time +1 //访问完成时间记录在f[u]中。

//完

第1-3行，5-7行循环占用时间为O（V），此不包括调用DFS-VISIT的时间。
对于每个顶点v(-V，过程DFS-VISIT仅被调用依次，因为只有对白色顶点才会调用此过程。
第4-7行，执行时间为O（E）。
因此，总的执行时间为O(V+E)。

CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>> “CDA报名” 了解CDA考试详情；