Tarjan算法简介

Author: 2015-08-30

ACM

, ,

　　Tarjan算法由Robert Tarjan提出，可看作是Kosaraju算法的一个升级版，可用于获取有向图的强联通分量。该算法从任意起点开始进行DFS，每个节点只访问一次，其搜索树即为图的生成森林，图的强联通分量可以从森林的特定子树中恢复出来。

　　在使用栈进行DFS时，首先将任意节点入栈，然后递归地搜索与该节点相连的其他节点。某一节点u递归搜索结束时：

  • 如果节点u和栈上节点u之前的其他节点还有相连的路径，则将节点u保留在栈上；
  • 反之，如果节点u和栈上节点u之前的任何节点都不相连，则u就是其强联通分量的根节点，该强连通分量包含节点u和栈上节点u之后的所有节点{V}。节点集{V}中的每一个点都有连向u的路径，且没有连向栈上节点u之前任何节点的路径（因为如果节点集{V}中的某一个点和栈上节点u之前的某一节点x相连，则u也一定和x相连，与“节点u和栈上节点u之前的任何节点都不相连”的前提条件矛盾）。

　　Wiki上给出了Tarjan算法的伪代码如下：

algorithm tarjan is
  input: graph G = (V, E)
  output: set of strongly connected components (sets of vertices)

  index := 0
  S := empty
  for each v in V do
    if (v.index is undefined) then
      strongconnect(v)
    end if
  end for

  function strongconnect(v)
    // Set the depth index for v to the smallest unused index
    v.index := index
    v.lowlink := index
    index := index + 1
    S.push(v)
    v.onStack := true

    // Consider successors of v
    for each (v, w) in E do
      if (w.index is undefined) then
        // Successor w has not yet been visited; recurse on it
        strongconnect(w)
        v.lowlink  := min(v.lowlink, w.lowlink)
      else if (w.onStack) then
        // Successor w is in stack S and hence in the current SCC
        v.lowlink  := min(v.lowlink, w.index)
      end if
    end for

    // If v is a root node, pop the stack and generate an SCC
    if (v.lowlink = v.index) then
      start a new strongly connected component
      repeat
        w := S.pop()
        w.onStack := false
        add w to current strongly connected component
      until (w = v)
      output the current strongly connected component
    end if
  end function

每一个节点v都按照其被搜索到的顺序进行了编号，即v.index；此外还用一个值v.lowlink来表示从能节点v到达的节点中最小的编号。v.lowlink是由从v开始的DFS计算得到的，从v开始的DFS会找到从v能到达的所有节点。如果有v.lowlink < v.index，表明v和栈上v之前的节点有连接，则v必须留在栈上；如果有v.lowlink == v.index，则v是一个强联通分量的根节点，必须从栈上移除。

　　最后附上一个例题：https://blog.nex3z.com/2015/08/21/ural-1198-jobbery/