深度优先搜索DFS
沿一条路径深入，再回退访问未探索分支。
- 核心约束
- 已访问状态防止重复探索或无限循环。
- 适用问题
- 依赖分析、环检测、连通分量与遍历。
- 边界与取舍
- 递归深度可能很大；有向图需区分访问状态。
时间与空间#
V 为顶点数，E 为边数；邻接表表示，访问时设置标记。
- 时间复杂度
- 辅助空间
- ，包括访问状态和最坏递归 / 显式栈
每条邻接边检查有限次；无向图通常保存双向邻接。普通 DFS 不保证最短路径；很深的图可能使语言调用栈溢出。
工程中的应用#
2 个案例 · 附源码Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS，检查跳转目标、可达性及控制流结构。
附源码片段 · 图处理与编译
LLVM 的 legacy 调用图 pass 管理器使用 Tarjan SCC 迭代器，将相互递归的函数作为一组，并按被调用方优先的顺序处理分组。
附源码片段 · 图处理与编译
基础原理参考资料
Princeton · DepthFirstPaths递归 DFS 的访问标记、路径状态和复杂度。