Tarjan算法

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

概述

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

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

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

根结点的性质

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

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

伪代码

algorithm tarjan is
  input: 图 G = (V, E)
  output: 以所在的强连通分量划分的顶点集

  index := 0
  S := empty    // 置栈为空
  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算法的讲解