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算法的講解（頁面存檔備份，存於網際網路檔案館）