Tarjanの強連結成分アルゴリズム

Tarjanの強連結成分アルゴリズム

タージャンのアルゴリズムアニメーション
データ構造	グラフ
最悪の場合の パフォーマンス	${\displaystyle O(|V|+|E|)}$

タージャンの強連結成分アルゴリズムは、有向グラフの強連結成分(SCC)を見つけるためのグラフ理論のアルゴリズムです。このアルゴリズムは線形時間で実行され、コサラジュのアルゴリズムやパスベースの強連結成分アルゴリズムなどの代替手法の時間制限と一致します。このアルゴリズムは発明者であるロバート・タージャンにちなんで名付けられました。^[1]

このアルゴリズムは、有向グラフを入力として受け取り、グラフの頂点をグラフの強連結成分に分割します。グラフの各頂点は、強連結成分の 1 つにのみ出現します。有向サイクル上にない頂点は、それ自体が強連結成分を形成します。たとえば、入次数または出次数が 0 の頂点や、非巡回グラフの頂点などです。

このアルゴリズムの基本的な考え方は、深さ優先探索 (DFS) が任意の開始ノードから開始される (その後、まだ見つかっていないノードに対して深さ優先探索が実行される) というものです。深さ優先探索ではよくあることですが、探索ではグラフのすべてのノードを 1 回だけ訪れ、すでに訪れたノードは再訪しません。したがって、探索ツリーのコレクションはグラフのスパニング フォレストです。強く接続されたコンポーネントは、このフォレストの特定のサブツリーとして復元されます。これらのサブツリーのルートは、強く接続されたコンポーネントの「ルート」と呼ばれます。強く接続されたコンポーネントのノードは、探索によって発見されたコンポーネントの最初のノードである場合、ルートとして機能する可能性があります。

ノードは、訪問された順にスタック上に配置されます。深さ優先探索がノードvとその子孫を再帰的に訪問する場合、この再帰呼び出しが戻ったときに、それらのノードがすべてスタックからポップされるとは限りません。重要な不変特性は、入力グラフ内にそのノードからスタック上の前のノードへのパスが存在する場合にのみ、ノードが訪問後にスタック上に残ることです。言い換えると、DFS では、ノードは、接続されたすべてのパスがトラバースされた後にのみスタックから削除されることを意味します。DFS がバックトラックする場合、単一のパス上のノードを削除し、新しいパスを開始するためにルートに戻ります。

およびその子孫を訪問する呼び出しの終了時に、それ自体にスタック上の前のノードへのパスがあるvかどうかがわかります。パスがある場合、呼び出しは戻り、スタックに残して不変条件を保存します。パスがない場合、 は、スタック上の より後のノードとともに で構成される強く連結されたコンポーネントのルートである必要があります(このようなノードはすべて に戻るパスを持ちますが、それより前のノードへのパスはありません。なぜなら、 が以前のノードへのパスを持っていた場合は、 が以前のノードへのパスも持つことになるため、これは false です)。 をルートとする連結されたコンポーネントはスタックからポップされて返され、この場合も不変条件を保存します。 vvvvvvvv

各ノードにvは一意の整数 が割り当てられv.index、ノードは発見された順に連続して番号付けされます。また、の DFS サブツリーを通じてv.lowlinkから到達可能であることがわかっているスタック上の任意のノード (それ自体を含む) の最小インデックスを表す値も保持します。したがって、 の場合は をスタックに残す必要がありますが、 の場合は v を強連結成分のルートとして削除する必要があります。 値は、 から到達可能なノードを検索する深さ優先検索中に から計算されます。 vvvvv.lowlink < v.indexv.lowlink == v.indexv.lowlinkvv

vローリンクは、グラフのどの部分からでも到達可能な最小のインデックスであるローポイントとは異なります。 ^{[1] : 156  [2]}

アルゴリズムtarjanは、入力:グラフG = ( V , E )、
    出力:強く連結されたコンポーネントの集合 (頂点の集合)です。
    
   
    index  := 0
     S  := 空のスタック
    V内の各 vに対して、  v .index が未定義の場合は
            strongconnect( v )を実行します。  
         
   
    function strongconnect( v )
         // v の深さインデックスを未使用の最小のインデックスに設定します
        v .index := index 
        v .lowlink := index 
        index  := index + 1
         S .push( v )
         v .onStack := true
      
        // 
        E内の各( v、w )について、 v の後続を検討します。w .indexが未定義の場合、後続 w はまだ訪問されていません。これを再帰的に処理します
                。strongconnect( w )
                 v .lowlink := min( v .lowlink, w .lowlink)
             else if w .onStack then // 後続 w はスタック S 内にあるため、現在の SCC 内にあります。// wがスタック上にない場合、( v 、 w ) は既に見つかった SCC を指すエッジであるため、無視する必要があります。// 次の行については以下を参照してください。v .lowlink := min( v .lowlink, w .index)  
             
                 
                
                
                
                
      
        // vがルートノードの場合、スタックをポップしてSCCを生成します。if 
        v  .lowlink = v .index then
            新しい強く連結されたコンポーネントを開始する
            繰り返し
                w  := S .pop()
                 w .onStack := falsew ≠ vの場合、現在の強連結成分に
            w を
                追加します。 
            現在の強く連結されたコンポーネントを出力する

変数indexは、深さ優先探索ノード番号カウンタです。Sはノード スタックで、最初は空で、探索されたが、まだ強く接続されたコンポーネントにコミットされていないノードの履歴を格納します。これは通常の深さ優先探索スタックではありません。検索がツリーを上って返されるときにノードがポップされず、強く接続されたコンポーネント全体が見つかった場合にのみノードがポップされます。

最も外側のループは、まだ訪問されていない各ノードを検索し、最初のノードから到達できないノードも最終的にはトラバースされるようにします。関数はstrongconnect、グラフの単一の深さ優先検索を実行し、ノードからのすべての後続ノードを検索しv、そのサブグラフの強く接続されたコンポーネントをすべて報告します。

各ノードが再帰を終了したときに、そのローリンクがまだそのインデックスに設定されている場合、そのノードはスタック上のそのノードより上位にあるすべてのノードによって形成される、強く接続されたコンポーネントのルート ノードです。アルゴリズムは、現在のノードまでスタックをポップし、これらのノードすべてを強く接続されたコンポーネントとして提示します。

Tarjan の論文では、wがスタック上にある場合、v.lowlinkは割り当て で更新されます。^{[1] : 157}一般的なバリエーションは、代わりに を使用することです。^{[3] [4]}この修正されたアルゴリズムは、Tarjan が定義したようにローリンク数を計算しませんが、テストは依然として強く接続されたコンポーネントのルートノードを識別するため、全体的なアルゴリズムは有効です。^[2]v.lowlink := min(v.lowlink, w.index)v.lowlink := min(v.lowlink, w.lowlink)v.lowlink = v.index

時間の複雑さ: Tarjan 手順は各ノードに対して 1 回呼び出されます。forall ステートメントは各エッジを最大 1 回考慮します。したがって、アルゴリズムの実行時間は G 内のエッジとノードの数に比例します。 ${\displaystyle O(|V|+|E|)}$

この複雑さを実現するには、wスタック上にあるかどうかのテストを一定時間で実行する必要があります。これは、上記の疑似コードのように実行できます。つまり、各ノードにスタック上にあるかどうかを示すフラグを格納し、フラグを調べることでこのテストを実行します。

空間計算量: Tarjan 手順では、頂点ごとにindexおよびlowlinkフィールド用に 2 ワードの補足データが必要で、 用に 1 ビットonStack、 が未定義のときを判定するための 1indexビットが必要です。さらに、 を保持するために各スタック フレームに 1 ワードv、エッジ リストの現在の位置用に 1 ワードが必要です。最後に、スタックの最悪ケースのサイズSは である必要があります(つまり、グラフが 1 つの巨大なコンポーネントである場合)。これにより、マシン ワード サイズが であるかどうかの最終的な分析が行われます。Nuutila と Soisalon-Soininen のバリエーションでは、これが に削減され、その後、Pearce のバリエーションでは のみが必要です。^{[5] [6]}${\displaystyle |V|}$${\displaystyle O(|V|\cdot (2+5w))}$${\displaystyle w}$${\displaystyle O(|V|\cdot (1+4w))}$${\displaystyle O(|V|\cdot (1+3w))}$

各強く連結されたコンポーネント内のノードの順序については特別なことは何もありませんが、このアルゴリズムの有用な特性の 1 つは、強く連結されたコンポーネントがその後続のコンポーネントよりも先に識別されないことです。したがって、強く連結されたコンポーネントが識別される順序は、強く連結されたコンポーネントによって形成されるDAGの逆位相ソートを構成します。 ^[7]

ドナルド・クヌースは、著書『スタンフォードグラフベース』の中で、タージャンのSCCアルゴリズムを彼のお気に入りの実装の一つとして紹介しています。^[8]

彼はまたこう書いている: ^[9]

彼がこの問題のために考案したデータ構造は驚くほど美しく組み合わさっており、有向グラフを探索する際に確認する必要のある量が常に魔法のように手元にあります。また、彼のアルゴリズムは副産物としてトポロジカルソートも行います。

• さまざまな言語での実装を示す Rosetta コード
• Tarjan の強連結成分アルゴリズムの PHP 実装
• Tarjan の強連結成分アルゴリズムの JavaScript 実装