Tarjan 强连通分量算法Tarjan's strongly connected components algorithm
在一次深度优先遍历中，利用访问编号、low-link 和成员栈识别有向图的强连通分量。
- 核心约束
- 成员栈保存已发现但尚未归入分量的顶点；某顶点的 low-link 等于访问编号时，从栈顶到该顶点构成一个完整分量。
- 适用问题
- 有向依赖环识别、递归调用图分组，以及将强连通分量压缩为 DAG。
- 边界与取舍
- low-link 只按算法规则处理 DFS 子树和仍在成员栈内的顶点；成员栈与递归调用栈职责不同。深图需要考虑显式 DFS 栈。
时间与空间#
V 为顶点数，E 为有向边数；这里指 Tarjan 算法。
- 时间复杂度
- 辅助空间
- ，含 DFS 状态、活动栈和分量编号
邻接表表示；lowlink 更新必须区分仍在栈中的节点与已完成分量。每个顶点进出栈一次，分量内部任意两点互相可达。
工程中的应用#
1 个案例 · 附源码LLVM 的 legacy 调用图 pass 管理器使用 Tarjan SCC 迭代器，将相互递归的函数作为一组，并按被调用方优先的顺序处理分组。
附源码片段 · 图处理与编译