图遍历Graph traversal
按一定顺序访问可达顶点和边，记录已经访问的状态，为路径、依赖与连通性分析提供基础。
怎样选择#
- V 为顶点数，E 为边数。O(V+E) 依赖邻接表等能按实际边数遍历邻接关系的表示；邻接矩阵遍历通常为 O(V²)。
- 从一个起点出发只访问其可达部分；要遍历整个不连通图，需要从未访问的顶点继续启动。
算法对照#
| 具体算法 | 问题与前提 | 时间复杂度 | 辅助空间 | 选择与取舍 |
|---|---|---|---|---|
| 广度优先搜索 | 无权图的最少边数路径或按层探索 | 邻接表 | ，不含图本身与最终路径输出 | 队列维护前沿；首次发现的层数对应起点到顶点的最少边数。 |
| 深度优先搜索 | 依赖关系、访问次序、环与回溯分析 | 邻接表 | ，包括访问状态和最坏递归 / 显式栈 | 递归或显式栈；有向图环检测还需区分正在访问与已完成状态。 |
左右滑动查看完整对照。点击算法名称，查看原理、约束和实现。
工程中的应用#
Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS，检查跳转目标、可达性及控制流结构。
附源码片段 · 图处理与编译
LLVM 的 legacy 调用图 pass 管理器使用 Tarjan SCC 迭代器，将相互递归的函数作为一组，并按被调用方优先的顺序处理分组。
附源码片段 · 图处理与编译