アルゴリズム・データ構造図鑑 · 基礎から応用へ

強連結成分分解:互いに行き来できる頂点をまとめる

有向グラフの相互到達可能性を成分へまとめ、縮約DAGと二回のDFSの意味を理解する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 片道の到達では同じ成分にならない
  2. 三つの成分を縮約する
  3. 二回の探索で境界を見つける
  4. 何を出力し何を数えるか
  5. この記事をロゲイアに質問する理解を確かめる

片道の到達では同じ成分にならない

有向グラフでuからvへもvからuへも道があるとき、二つの頂点は同じ強連結成分に属します。道の長さ0も認めるので各頂点は自分自身へ到達でき、孤立した頂点も一つの成分です。辺の向きを無視した連結成分とは異なり、片方向につながっているだけでは一つにまとめません。相互到達可能性は同値関係になるため、頂点集合を重複のない成分へ分けられます。成分の中のすべての頂点対に直接の辺が必要なわけではなく、複数の辺を通る道があれば十分です。

三つの成分を縮約する

辺A→B、B→A、B→C、C→D、D→C、D→Eがあると、成分は{A,B}、{C,D}、{E}です。それぞれを一頂点へ縮めると、最初の成分から二番目、二番目から三番目への辺だけが残ります。この縮約グラフに有向閉路があれば、その閉路上の成分は互いに到達でき、別成分とした定義に反します。したがって縮約グラフはDAGです。元のグラフに閉路があっても、成分単位では依存関係をトポロジカル順で考えられます。

二回の探索で境界を見つける

Kosaraju型の方法は、向きを逆にしたグラフでDFSの終了順を求め、その逆順で元のグラフをDFSします。まだ成分番号が付いていない頂点からの一回の探索で、同じ強連結成分をまとめます。逆向きで終了順を取るという約束と、元のグラフを処理する順番は一組です。単なる頂点番号順やDFS開始順に置き換えると、外の成分へ越えてまとめてしまうことがあります。対称な別の説明では元と逆グラフの役割を交換するため、二つの版を途中で混ぜないようにします。

何を出力し何を数えるか

隣接リストでは二回のDFSと逆グラフの構築を合わせて時間O(V+E)です。逆向きの辺を別に保持するならその領域もO(V+E)、訪問済み印や成分番号はO(V)です。深いグラフでは再帰スタックの上限にも注意し、必要なら明示的スタックを使います。返す成分番号は実装によって変わり、番号そのものに大小の意味があるとは限りません。テストでは番号の一致ではなく、互いに到達可能な頂点が同じ集合になっているか、縮約が非巡回かを確かめます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ