Tarjan算法简介

  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/