22.3 深度优先搜索

深度优先搜索所使用的策略就像其名字所隐含的:只要可能，就在图中尽量“深入”。深度优先搜索总是对最近才发现的结点v的出发边进行探索，直到该结点的所有出发边都被发现为止。一旦结点v的所有出发边都被发现，搜索则“回溯”到v的前驱结点(v是经过该结点才被发现的)，来搜索该前驱结点的出发边。该过程一直持续到从源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。该算法重复整个过程，直到图中的所有结点都被发现为止。

前驱子图 深度优先树 深度优先森林 树边

发现 完成

时间戳

DFS(G)

for each vertex u ∈ G.V
	u.color = WHITE
    u.Π = NIL
time = 0
for each vertex u ∈ G.V
	if u.color = WHITE
    	DFS-VISIT(G,u)

DFS-VISIT(G,u)

time = time + 1//white vertex u has just been discovered
u.d = time
u.color = GRAY
for each v ∈ G:Adj[u]//explore edge (u,v)
	if v.color == WHITE
    	v.Π = u
        DFS-VIST
u.color = BLACK//blacken u; it is finished
time = time +1
u.f = time

图22-4描述的是深度优先搜索算法在图22-2上运行的过程。

图 22-4 深度优先搜索算法 DFS在有向图上的运行过程

发现时间 完成时间

探索

注意，深度优先搜索的结果可能依赖于算法 DFS中第5行对结点进行检查的次序和算法DFS- VISIT的第4行对一个结点的邻接结点进行访问的次序。不过，这些不同的访问次序在实际中并不会导致问题，因为我们通常可以对任意的深度优先搜索结果加以有效利用，并获得等价的结果。

深度优先搜索的性质

括号化结构

图 22-5 深度优先搜索的性质

定理 22.7 括号化定理

证明

推论 22.8 后代区间的嵌套

证明

从定理22.7立即可得。

定理 22.9 白色路径定理 在深度优先森林中，当一个结点是另一个结点的后代时的另一个重要特征

证明

边的分类

定理 22.10 在对无向图的深度优先搜索中，从来不会出现前向边和横向边

在对无向图G进行深度优先搜索时，每条边要么是树边，要么是后向边。

证明

在本章后面的小节中，我们将看到这些定理的几种应用。

练习

22.3-9

Give a counterexample to the conjecture that if a directed graph G contains a path from u to v, then any depth-first search must result in v.d≤u.f.

给出一个反例来证明这样的猜想：如果有向图G包含一条从u到v的路径，那么任何深度优先搜索都必须得到v.d≤u.f。

Solution

考虑顶点{1,2,3}上的有向图，并且具有边（1,2），（1,3），（2,1），然后存在从2到3的路径。然而，如果我们在1开始一个DFS，在3之前处理2，我们将得到2.f=3<4=3.d，这为给定的猜想提供了一个反例。