深度优先搜索(DFS)算法

正如名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的顶点，如果它还有以此为起点而未探测到的边，就沿此边继续汉下去。当结点v的所有边都己被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。

和广度优先搜索类似，每当扫描已发现结点u的邻接表从而发现新结点v时，深度优先搜索将置v的先辈域π[v]为u。和宽度优先搜索不同的是，前者的先辈子图形成一棵树，而后者产生的先辈子图可以由几棵树组成，因为搜索可能由多个源顶点开始重复进行。因此深度优先搜索的先辈子图的定义也和宽度优先搜索稍有不同：

G_π=(V,E_π),E_π={(π[v],v)∈E:v∈V∧π[v]≠NIL}

深度优先搜索的先辈子图形成一个由数个深度优先树组成的深度优先森林。E_π中的边称为树枝。

和宽度优先搜索类似，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，结束时又被置成黑色(即当其邻接表被完全检索之后)。这一技巧可以保证每一顶点搜索结束时只存在于一棵深度优先树上，因此这些树都是分离的。

除了创建一个深度优先森林外，深度优先搜索同时为每个结点加盖时间戳。每个结点v有两个时间戳：当结点v第一次被发现(并置成灰色)时记录下第一个时间戳d[v]，当结束检查v的邻接表时(并置v为黑色)记录下第二个时间截f[v]。许多图的算法中都用到时间戳，他们对推算深度优先搜索进行情况是很有帮助的。

下列过程DFS记录了何时在变量d[u]中发现结点u以及何时在变量f[u]中完成对结点u的检索。这些时间戳为1到2|V|之间的整数，因为对每一个v中结点都对应一个发现事件和一个完成事件。对每一顶点u，有

d[u]

在时刻d[u]前结点u为白色，在时刻d[u]和f[u]之间为灰色，以后就变为黑色。

下面的伪代码就是一个基本的深度优先搜索算法，输人图G可以是有向图或无向图，变量time是一个全局变量，用于记录时间戳。

 procedure DFS(G);
   begin
1    for 每个顶点u∈V[G] do
       begin
2        color[u]←White;
3        π[u]←NIL;
       end;
4    time←0;
5    for 每个顶点u∈V[G] do
6      if color[u]=White
7          then DFS_Visit(G,u);
end;

 procedure DFS_Visit(G,u);
  begin
1   color[u]←Gray;              Δ白色结点u已被发现
2   d[u]←time←time+1;
3   for 每个顶点v∈Adj[u] do     Δ探寻边(u,v)
4      if color[v]=White 
          then begin
5                π[v]←u;
6                DFS_Visit(G,v);
               end;
7   color[u]←Black;             Δ完成后置u为黑色
8   f[u]←time←time+1;
end;

图2说明了DFS在图1所示的图上执行的过程。被算法探寻到的边要么为阴影覆盖 (如果该边为树枝)，要么成虚线形式 (其他情况)。对于非树枝的边，分别标明B(或F)以表示反向边、交叉边或无向边。我们用发现时刻Z完成时刻的形式对结点加盖时间戳。

图1 一个有向图图

图2 深度优先搜索算法DFS在有向图图1上的执行过程

执行如下。第1-3行把所有结点置为白色，所有π域初始化为NIL。第4行复位全局变量time，第5-7行依次检索V中的结点，发现白色结点时，调用DFS_Visit去访问该结点。每次通过第7行调用DFS_Visit时，结点u就成为深度优先森林中一棵新树的根，当DFS返回时，每个结点u都对应于一个发现时刻d[u]和一个完成时刻f[u]。

每次开始调用DFS_Visit(u)时结点u为白色，第1行置u为灰色，第2行使全局时间变量增值并存于d[u]中，从而记录下发现时刻d[u]，第3-6行检查和u相邻接的每个顶点v，且若v为白色结点，则递归访问结点v。在第3行语句中考虑到每一个结点v∈Adj[u]时，我们可以说边(u,v)被深度优先搜索探寻。最后当以u为起点的所有边都被探寻后，第7-8行语句置u为黑色并记录下完成时间f[u]。

算法DFS运行时间的复杂性如何？DFS中第1-2行和5-7行的循环占用时间为O(V),这不包括执行调用DFS_Visit过程语句所耗费的时间。事实上对每个顶点v∈V，过程DFS_Visit仅被调用一次，因为DFS_Visit仅适用于白色结点且过程首先进行的就是置结点为灰色，在DFS_Visit(v)执行过程中，第3-6行的循环要执行|Adj[v]|次。因为∑_v∈V|Adj[v]| =θ(E)，因此执行过程DFS_Visit中第2-5行语句占用的整个时间应为θ(E)。所以DFS的运行时间为θ(V+E)。

深度优先搜索的性质

依据深度优先搜索可以获得有关图的结构的大量信息。也许深度优先搜索的最基本的特征是它的先辈子图G，形成一个由树组成的森林，这是因为深度优先树的结构准确反映了DFS_Visit中递归调用的结构的缘故，即u=π[v]当且仅当在搜索u的邻接表过程中调用了过程DFS_Visit(v)。

图3 深度优先搜索的性质

深度优先搜索的另一重要特性是发现和完成时间具有括号结构，如果我们把发现顶点u用左括号“(u”表示，完成用右括号“u)”表示，那么发现与完成的记载在括号被正确套用的前提下就是一个完善的表达式。例如，图3显示了深度优先搜索的性质。(a)对一个有向图进行深度优先搜索的结果。结点的时间戳与边的类型的表示方式与图2相同。(b)图中的括号表示对应于每个结点的发现时刻和完成时刻的组成的区间。每个矩形跨越相应结点的发现时刻与完成时刻所设定的区间。图中还显示了树枝。如果两个区间有重叠，则必有一个区间嵌套于另一个区间内，且对应于较小区间的结点是对应于较大区间的结点的后裔。(c)对(a)中图的重新描述，使深度优先树中所有树枝和正向边自上而下，而所有反向边自下而上从后裔指向祖先。下面的定理给出了标记括号结构的另外一种办法。

定理1 括号定理

在对有向图或无向图G=(V,E)的任何深度优先搜索中，对于图中任意两结点u和v，下述三个条件中有且仅有一条成立：

• 区间[d[u],f[u]]和区间[d[v],f[v]]是完全分离的；
• 区间[d[u],f[u]]完全包含于区间[d[v],f[v]]中且在深度优先树中u是v的后裔；
• 区间[d[v],f[v]]完全包含于区间[d[u],f[u]]中且在深度优先树中v是u的后裔。

证明:

先讨论d[u]

对于d[v]

推论1 后裔区间的嵌入

在有向或无向图G的深度优先森林中，结节v是结点u的后裔当且仅当d[u]

证明：直接由定理1推得。（证毕）

在深度优先森林中若某结点是另一结点的后裔，则下述定理将指出它的另一重要特征。

定理2 白色路径定理

在一个有向或无向图G=(V,E)的深度优先森林中，结点v是结点u的后裔当且仅当在搜索发现u的时刻d[u]，从结点u出发经一条仅由白色结点组成的路径可达v。

证明:

→：假设v是u的后裔，w是深度优先树中u和v之间的通路上的任意结点，则w必然是u的后裔，由推论1可知d[u]

←：设在时刻d[u]，从u到v有一条仅由白色结点组成的通路，但在深度优先树中v还没有成为u的后裔。不失一般性，我们假定该通路上的其他顶点都是u的后裔(否则可设v是该通路中最接近u的结点，且不为u的后裔)，设w为该通路上v的祖先，使w是u的后裔(实际上w和u可以是同一个结点）。根据推论1得f[w]≤f[u]，因为v∈Adj[w]，对DFS_Visit(w)的调用保证完成w之前先完成v，因此f[v]

边的分类

在深度优先搜索中，另一个令人感兴趣的特点就是可以通过搜索对输入图G=(V,E)的边进行归类，这种归类可以发现图的很多重要信息。例如一个有向图是无回路的，当且仅当深度优先搜索中没有发现“反向边”。

根据在图G上进行深度优先搜索所产生的深度优先森林G，我们可以把图的边分为四种类型。

1. 树枝，是深度优先森林G_π中的边，如果结点v是在探寻边(u,v)时第一次被发现，那么边(u,v)就是一个树枝。
2. 反向边，是深度优先树中连结结点u到它的祖先v的那些边，环也被认为是反向边。
3. 正向边，是指深度优先树中连接顶点u到它的后裔的非树枝的边。
4. 交叉边，是指所有其他类型的边，它们可以连结同一棵深度优先树中的两个结点，只要一结点不是另一结点的祖先，也可以连结分属两棵深度优先树的结点。

在图2和图3中，都对边进行了类型标示。图3(c)还说明了如何重新绘制图3(a)中的图，以使深度优先树中的树枝和正向边向下绘制，使反向边向上绘制。任何图都可用这种方式重新绘制。
可以对算法DFS进行一些修改，使之遇到边时能对其进行分类。算法的核心思想在于可以根据第一次被探寻的边所到达的结点v的颜色来对该边(u,v)进行分类(但正向边和交叉边不能用颜色区分出)。

1. 白色表明它是树枝。
2. 灰色说明它是反向边。
3. 黑色说明它是正向边或交叉边。

第一种情形由算法即可推知。在第二种情形下，我们可以发现灰色结点总是形成一条对应于活动的DFS_Visit调用堆栈的后裔线性链，灰色结点的数目等于最近发现的结点在深度优先森林中的深度加1，探寻总是从深度最深的灰色结点开始，因此达到另一个灰色结点的边所达到的必是它的祖先。余下的可能就是第三种情形，如果d[u]d[v]，则(u,v)便是交叉边。

因此可以得到下面结论：对于某条边(u,v)，

• 当且仅当d[u]
• 当且仅当d[v]
• 当且仅当d[v]

该结论的证明略。

在无向图中，由于(u,v)和(v,u)实际上是同一条边，所以对边进行这种归类可能产生歧义。在这种情况下，图的边都被归为归类表中的第一类，对应地，我们将根据算法执行过程中首先遇到的边是(u,v)还是(v,u)来对其进行归类。

下面我们来说明在深度优先搜索无向图时不会出现正向边和交叉边。

定理3

在对无向图G进行深度优先搜索的过程中，G的每条边要么是树是反向边。

证明：

设(u,v)为G的任意一边，不失一般性，假定d[u]