深度优先搜索

深度优先搜索(DFS)

通用DFS的用途比通用BFS更广泛，DFS记录顶点颜色、前驱、变灰时间、变黑时间。顶点有三种色(白/灰/黑=未到达/已到达并开始当前顶点的子DFS/已到达且全部邻接顶点的子DFS结束亦即当前顶点的子DFS结束)。时间的定义是每次变色时间加一，其用于描述搜索的推进。顶点由白变灰意味着其子DFS的开始，该DFS会一直持续到该顶点变黑。任意子DFS在结束时比开始只会新增染黑的顶点。DFS往往要求访问完源点所有可达顶点后(此时根据可达顶点的前驱可得DFS树)，若顶点集尚有未达顶点，就从中选新源点在“当前时间”继续DFS(最终根据所有顶点的前驱可得DFS森林)。该要求意味在解决很多问题时从任意源点DFS不影响结果，而且往往需访问所有顶点。

括号化结构

DFS结束后所有顶点记录两个时间。在其中任取两个不同顶点u与v，下述情况有且只有一种成立。因为各顶点上子DFS的推进基于调用栈，顶点的染灰与染黑仅发生于该顶点的子DFS的开始与结束。父DFS的调用结束仅发生于其全部子DFS从开始到结束执行完，不可能出现子DFS结束前父DFS已结束的情况，故两区间不会交叉。

1) \([u.t_1,u.t_2]\)完全分离于\([v.t_1,v.t_2]\)，此时在DFS森林二者无后裔关系；

2) \([u.t_1,u.t_2]\)完全包含\([v.t_1,v.t_2]\)，此时在DFS树v是u的后裔；

3) \([v.t_1,v.t_2]\)完全包含\([u.t_1,u.t_2]\)，此时在DFS树u是v的后裔；

括号化结构：后代区间嵌套

\({u.t_1}<{v.t_1}<{v.t_2}< {u.t_2}\) \({<=>} \) 该DFS的树(森林)中v是u的后裔。

证明：该命题的充分性与必要性很容易从括号化结构中直接得出。

括号化结构：白色路径定理

DFS在\({u.t_1}\)时从u出发可沿一组白色顶点到达v \({<=>} \) 该DFS的树(森林)中v是u的后裔。

证明：设在DFS森林中顶点w为u的后代，根据后代区间嵌套可知\({u.t_1}<{w.t_1}\)，所以u染灰时刻w为白色，由于w可任意选择，必要性得证。假设“DFS在\({u.t_1}\)时从u到v有白色路径，该白色路径中的所有顶点除v以外都为DFS树(森林)中u的后裔”。取白色路径中v的前驱w，根据假设w为u的后裔或w=u，根据后代区间嵌套\(w.t_2 \leq u.t_2\)。w变黑时其邻接顶点v不可能为白色，故\(w.t_2 > v.t_1\)。由于u染灰时刻v为白色所以\(u.t_1 < v.t_1 \)。综上有\(u.t_2 > v.t_1 > u.t_1\)，根据括号化结构v为u的后裔，故充分性得证。

边分类方法

按图的某DFS树(森林)可以完备把边分成4类，任何图都可把边按这4种方向“重画”。

1) 树边: DFS树(森林)中的边，若DFS在u下置灰v则\((u,v) \)是该DFS树(森林)的树边;

2) 后向边: DFS树(森林)中从后裔顶点指向祖先顶点的非树边;

3) 前向边: DFS树(森林)中从祖先顶点指向后裔顶点的非树边;

4) 横向边: DFS树(森林)中同个树的无祖先后裔关系顶点间的边，或是不同树间的边；

边分类方法：分类算法

DFS(包括BFS)可保证“仅访问一次”边集中的所有元素，因为所有白顶点都会被访问，但仅被染灰一次，且仅在染灰时访问其所有邻接顶点。在DFS中可利用这次访问把整个图的边按上述方法分类：

1) 当访问到u的邻接顶点v时v为白色，则\((u,v)\)为该DFS对应的树边；

2) 当访问到u的邻接顶点v时v为灰色，则\((u,v)\)为该DFS对应的后向边；

3) 当访问到u的邻接顶点v时v为黑色，则\((u,v)\)为该DFS对应的前向边或横边；

证明：情况(1)本身即记录前驱顶点时的步骤。情况(2)中v为灰色，即当前亦处于v的子DFS，而u刚从白变灰，故存在v到u的路径。并且对于v的子DFS而言其之所以访问了\((u,v)\)边，其只能通过把白色顶点变为灰色才能一层一层访问到u，所以从u向上找前驱必然可以找到v，所以u与v位于同一个生成树中，且v是u的祖先。

边分类方法：无向图的边分类

对无向图进行DFS其所有边都为树边或反向边。

证明：在无向图中\((a,b)\)与\((b,a)\)代表同一条边。在无向图任取一条边\((u,v)\)，并设在DFS中\(u.t_1<v.t_1\)。如果首次访问该边在u染灰时，此时v为白色，该边为树边。如果首次访问该边在v染灰时，此时u不可能为黑色，因为v是u的邻接顶点且v的子DFS未结束，所以u为灰色，该边为反向边。