形式陈述

深度优先搜索从未访问顶点出发，沿一条尚未探索的边尽可能深入；当当前顶点没有未访问邻居时回溯。可用递归调用栈或显式栈实现。标准版本为每个顶点记录发现时间 $d[u]$$d[u]$、完成时间 $f[u]$$f[u]$ 与父节点 $\pi[u]$$\pi [u]$，所得父边形成深度优先森林。

在邻接表表示下，DFS 每个顶点发现一次、每条边扫描常数次，故时间为

$$ O(|V|+|E|), $$$$O(|V|+|E|),$$

辅助状态与栈最坏为 $O(|V|)$$O(|V|)$。

直觉

DFS 暂时忽略其他分支，沿当前路径走到底再返回。递归栈保存“还要回来继续探索”的未完成顶点，因此自然暴露嵌套结构。

例子与边界

DFS 首次找到的源到顶点路径一般不是最短路。递归实现可能在很深图上耗尽语言运行时栈，显式栈可避免该工程限制，但不改变最坏空间阶。邻接点遍历顺序不同会产生不同 DFS 树和时间戳，却不改变算法性质。

推论与应用

DFS 用于拓扑排序、强连通分量、割点、桥、圈检测和回溯搜索。发现/完成区间具有嵌套性质，可据此分类树边、回边、前向边和交叉边；无向图中的边分类比有向图更简单。

参考资料

• 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。