Tarjan算法

Tarjan算法（以发现者Robert Tarjan命名）是一个在图中查找强连通分量的算法。虽然发表时间更早，它仍可以被视为Kosaraju算法的一个改进。它的效率跟Gabow算法差不多。

概述

此算法以一个有向图作为输入，并按照所在的强连通分量给出其顶点集的一个划分。图中的每个节点只在一个强连通分量中出现，即使是在有些节点单独构成一个强连通分量的情况下（比如图中出现了树形结构或孤立节点）。

算法的基本思想如下：任选一节点开始进行深度优先搜索（若深度优先搜索结束后仍有未访问的节点，则再从中任选一点再次进行）。搜索过程中已访问的节点不再访问。搜索树的若干子树构成了图的强连通分量。

节点按照被访问的顺序存入堆栈中。从搜索树的子树返回至一个节点时，检查该节点是否是某一强连通分量的根节点（见下）并将其从堆栈中删除。如果某节点是强连通分量的根，则在它之前出堆栈且还不属于其他强连通分量的节点构成了该节点所在的强连通分量。

根节点的性质

算法的关键在于如何判定某节点是否是强连通分量的根。注意“强连通分量的根”这一说法仅针对此算法，事实上强连通分量是没有特定的“根”的。在这里根节点指深度优先搜索时强连通分量中首个被访问的节点。

为找到根节点，我们给每个节点v一个深度优先搜索标号v.index，表示它是第几个被访问的节点（时间戳）。此外，每个节点v还有一个值v.lowlink，表示从v出发经有向边可到达的所有节点中最小的index（追溯值）。显然v.lowlink总是不大于v.index，且当从v出发经有向边不能到达其他index值更小的节点时，这两个值相等。 v.lowlink在深度优先搜索的过程中求得，v是强连通分量的根当且仅当v.lowlink = v.index。

伪代码

algorithm tarjan is
   input: 图 G = (V, E)
   output: 以所在的强连通分量划分的顶点集合
 
   index := 0
   S = empty // 初始化栈S为空栈
   for each v in V do
     if (v.index is undefined)
       strongconnect(v)
     end if
 
   function strongconnect(v)
     // 将未使用的最小index值作作为节点v的index
     v.index := index
     v.lowlink = index
     index := index + 1
     S.push(v)
 
     // 考虑节点v的后继节点
     for each (v, w) in E do
       if (w.index is undefined) then
         // 后继节点w未访问，递归调用
         strongconnect(w)
         v.lowlink = min(v.lowlink, w.lowlink)
       else if (w is in S) then
         // w已在栈S中，则其也在当前的强连通分量中
         v.lowlink := min(v.lowlink, w.index)
       end if
 
     // 若v是根则出栈，并得到一个强连通分量
     if (v.lowlink = v.index) then
       start a new strongly connected component
       repeat
         w = S.pop()
         add w to current strongly connected component
       until (w = v)
       output the current strongly connected component
     end if
   end function

变量index是深度优先搜索的节点计数器。 S是堆栈，初始为空，用于存储已经访问但未被判定属于任一强连通分量的节点。注意这并非一个一般深度优先搜索的堆栈，节点不是在以它为根的子树搜索完成后出堆栈，而是在整个强连通分量被找到时。

最外层循环用于查找未访问的节点，以保证所有节点最终都会被访问。 strongconnect进行一次深度优先搜索，并找到节点v的后继节点构成的子图中所有的强连通分量。

当一个节点完成递归时，若它的lowlink仍等于index，那么它就是强连通分量的根。算法将在此节点之后入堆栈（包含此节点）且仍在堆栈中的节点出堆栈，并作为一个强连通分量输出。

备注

1. 复杂度:对每个节点，过程strongconnect只被调用一次；整个程序中每条边最多被考虑一次。因此算法的运行时间关于图的边数是线性的，即$O(|V|+|E|)$。
2. 判断节点v'是否在堆栈中应在常量时间内完成，例如可以对每个节点保存一个是否在堆栈中的标记。
3. 同一个强连通分量内的节点是无序的，但此算法具有如下性质：每个强连通分量都是在它的所有后继强连通分量被求出之后求得的。因此，如果将同一强连通分量收缩为一个节点而构成一个有向无环图，这些强连通分量被求出的顺序是这一新图的拓扑序的逆序。

外部链接

• BYVoid对Tarjan算法的讲解（页面存档备份，存于互联网档案馆）