Tarjan 算法

定义

Tarjan 算法由图灵奖得主 Robert Tarjan 于 1972 年提出,用于求有向图的强连通分量(SCC),即最大化的顶点子集,其中任意两点相互可达。

原理

算法基于深度优先搜索,为每个顶点记录访问时间戳 dfn 和能追溯到的最早祖先 low,同时用栈保存当前搜索路径上的顶点。当某顶点满足 dfn 等于 low 时,栈中从它到栈顶的所有顶点构成一个强连通分量。整个过程只需一次 DFS,时间复杂度 O(V+E)。

应用

用于将有向图缩点成 DAG 以便进一步处理、2-SAT 问题求解、编译器中的循环依赖检测等。Tarjan 的同类思想还衍生出求割点、桥和双连通分量的算法。

对比

与 Kosaraju 算法(需两次 DFS 和反向图)相比,Tarjan 只需一次遍历,常数更小,是竞赛与工程中的主流选择。