深度优先搜索 | Codeboy's Blog

形式陈述

给定有限图 $G=(V,E)$ ，深度优先搜索（DFS）依次从尚未发现的顶点启动搜索。访问 $u$ 时先记录发现时间 $d[u]$ ，随后逐一扫描邻接点；遇到未发现顶点 $v$ ，置 $\pi[v]=u$ 并递归访问 $v$ 。当 $u$ 的邻接表全部处理完，记录完成时间 $f[u]$ 。父边组成深度优先森林；只从指定源点启动时，则只覆盖其可达部分。

递归调用或等价的显式栈在任一时刻保存一条 DFS 树根到当前顶点的活动路径。对白—灰—黑三色状态，白色尚未发现，灰色已发现但未完成，黑色已经完成。时间区间满足括号定理：任意两个顶点的区间

[d[u],f[u]]\quad\text{与}\quad[d[v],f[v]]

要么不交，要么一个严格包含另一个；在后一种情形中，外层顶点是内层顶点在 DFS 森林中的祖先。这个嵌套不变量支撑环检测、拓扑排序和许多 low-link 算法。

设 $n=|V|$ 、 $m=|E|$ 。在邻接表表示下，每个顶点发现、完成各一次，有向弧扫描一次，无向边扫描两个表项，因此确定性最坏时间为

\Theta(n+m),

颜色、父指针、时间戳与最深调用栈共用 $O(n)$ 辅助空间。邻接矩阵版本要为每个访问顶点扫描一整行，最坏为 $\Theta(n^2)$ 。

直觉

DFS 把“稍后继续处理的分支”留在栈帧中，先把当前分支走到底。发现时间记录进入嵌套区间的时刻，完成时间记录退出；搜索树因此把一次线性扫描转成了祖先关系。邻接次序会改变树、时间戳和输出顺序，却不会改变从给定源可达的顶点集合。

DFS 的当前活动路径、递归调用栈与完成子调用后的回溯 — DFS 的递归栈与回溯

与按层推进的广度优先搜索相比，DFS 没有距离单调性。它换来的信息是活动路径和退出顺序：灰色顶点恰是当前递归祖先，遇到指向灰色祖先的边便得到了一个有向圈证据。

例子与边界

在有向图

1\to2,\quad1\to3,\quad2\to4,\quad3\to4,\quad4\to2

中，若 $1$ 的邻接表先列 $2$ ，发现序可为 $1,2,4,3$ 。扫描 $4\to2$ 时 $2$ 仍为灰色，这条回边与树路 $2\leadsto4$ 合成有向圈。稍后从 $3$ 扫描 $3\to4$ 时 $4$ 已为黑色；仅凭“目标已访问”不能把它误报成回边。

有向图中，指向白点的是树边，指向灰色祖先的是回边；指向黑点的边要结合时间区间区分前向边与交叉边。有向图无环当且仅当任意完整 DFS 森林都没有回边。无向图的非树边只连接祖先与后代，但扫描父边的反向记录不构成圈；若允许平行边，必须按边 ID 排除那一条父边，因为另一条平行边确实形成长度为二的多重图圈。

DFS 首次找到的路径一般不是最短路：在边 $s\to a,a\to t,s\to t$ 中，若先深入 $a$ ，得到两条边的树路，尽管直达边只需一步。递归实现还可能在长度为 $n-1$ 的链上耗尽语言运行时栈；显式栈能控制存储位置，但仍需 $\Theta(n)$ 最坏空间。若要精确复现递归版的完成时间，栈帧必须同时保存“邻接表已经扫描到哪里”，而不能只压入顶点编号。

推论与应用

逆完成序可构造拓扑排序，两次 DFS 可分解强连通分量，发现时间与Low-link 值可识别桥、割点和分量。它们共享遍历骨架，正确性却分别依赖“无回边”“凝聚图次序”或“子树能回到多早”的附加不变量。

发现/完成区间还把 DFS 树的子树映成嵌套区间，树的 Euler Tour 技巧据此支持祖先或子树查询。一般有向图的非树边不会因此消失；只有先明确要查询的是 DFS 森林结构，才能把区间结论用于原图问题。

在单入口 flow graph 中，Lengauer–Tarjan 算法借 DFS 编号组织半支配点，但 DFS parent 只代表首次到达，未必支配子节点。边一旦插删，原有搜索树、时间区间和边分类都可能改变；本页的线性界只描述一次静态遍历，不是动态图维护保证。

参考资料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 20。
Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，§3.3。

形式陈述 ​

反向链接

形式陈述