パスベースの強成分アルゴリズム

グラフ理論では、有向グラフの強く連結した成分は、深さ優先探索と2つのスタックを組み合わせたアルゴリズムを使って見つけられる。1つは現在の成分の頂点を追跡し、もう1つは現在の検索パスを追跡する。^[1]このアルゴリズムのバージョンは、Purdom (1970)、Munro (1971)、Dijkstra (1976)、Cheriyan & Mehlhorn (1996)、Gabow (2000) によって提案されており、このうちDijkstraのバージョンが初めて線形時間を達成した。^[2]

このアルゴリズムは、与えられたグラフGの深さ優先探索を実行し、2 つのスタックSとPを維持します(再帰関数の通常の呼び出しスタックに加えて)。スタックSには、深さ優先探索が頂点に到達した順序で、強連結成分にまだ割り当てられていないすべての頂点が含まれます。スタックPには、互いに異なる強連結成分に属することがまだ決定されていない頂点が含まれます。また、これまでに到達した頂点の数のカウンターCも使用し、これを使用して頂点の事前順序数を計算します。

深さ優先探索が頂点v に到達すると、アルゴリズムは次の手順を実行します。

1. vの事前順序番号をCに設定し、C を増分します。
2. v をSに押し込み、さらにPにも押し込みます。
3. vから隣接する頂点wへの各辺について:
   • wの事前順序番号がまだ割り当てられていない場合（エッジがツリーエッジの場合）、w を再帰的に検索します。
   • それ以外の場合、w がまだ強く接続されたコンポーネントに割り当てられていない場合（エッジは前方/後方/交差エッジです）：
     • Pの最上位要素の事前順序数がwの事前順序数以下になるまで、 Pから頂点を繰り返しポップします。
4. vがPのトップ要素の場合:
   • vがポップされるまでSから頂点をポップし、ポップされた頂点を新しいコンポーネントに割り当てます。
   • Pからvをポップします。

全体的なアルゴリズムは、グラフの頂点を通るループで構成され、事前順序番号がまだ割り当てられていない各頂点に対してこの再帰検索を呼び出します。

このアルゴリズムと同様に、Tarjan の強連結成分アルゴリズムもスタックとともに深さ優先探索を使用して、まだ成分に割り当てられていない頂点を追跡し、その成分の最後の頂点の拡張が完了したら、これらの頂点を新しい成分に移動します。ただし、スタックPの代わりに、Tarjan のアルゴリズムは、深さ優先探索で頂点が最初に訪問される順序で割り当てられた、頂点インデックス付きの事前順序番号配列を使用します。事前順序配列は、新しい成分を形成するタイミングを追跡するために使用されます。

• Cheriyan, J.; Mehlhorn, K. (1996)、「ランダムアクセスコンピュータ上の密なグラフとネットワークのアルゴリズム」、Algorithmica、15 (6): 521–549、doi :10.1007/BF01940880、S2CID  8930091。
• ダイクストラ、エドガー(1976)、『プログラミングの規律』、ニュージャージー州: プレンティス ホール、第 25 章。
• Gabow, Harold N. (2000)、「強い二連結成分に対するパスベースの深さ優先探索」(PDF)、Information Processing Letters、74 (3–4): 107–114、doi :10.1016/S0020-0190(00)00051-X、MR  1761551。
• マンロー、イアン（1971）、「有向グラフの推移閉包の効率的な決定」、情報処理レター、1（2）：56-58、doi：10.1016/0020-0190（71）90006-8。
• パードム、P. Jr. (1970)、「推移閉包アルゴリズム」、BIT、10 :76–94、doi :10.1007/bf01940892、S2CID  20818200。
• Sedgewick, R. (2004)、「19.8 有向グラフの強い構成要素」、Java アルゴリズム、パート 5 – グラフ アルゴリズム(第 3 版)、ケンブリッジ MA: Addison-Wesley、pp. 205–216。