情報科学と人工知能のノート

初等的な知識から最新論文の解説まで色々集めていきます.備忘録兼用.

有向グラフの強連結成分分解

ナイーブなアルゴリズム

ある頂点  v からグラフ探索(深さ優先探索など.なんでもよい)を始めて訪れることができた頂点の集合  V_1 と,グラフの全ての辺を逆向きにしてから  v からグラフ探索を始めて訪れることのができた頂点の集合  V_2 に対し, V_1 \cap V_2 によって誘導される部分グラフが  v を含む強連結成分です.
よってせいぜい  O(|V|(|V| + |E|)) くらいの時間計算量のアルゴリズムで全ての強連結成分を調べ上げることができます.
これを線形時間で達成するのが以降の話です.

アルゴリズム

強連結成分分解は深さ優先探索を合計で二回分行うことによって達成できます.

  1. トポロジカルソートと全く同じ方法で頂点に番号を付ける.
  2. グラフの全ての辺を逆向きにする.
  3. 番号の最も大きい頂点から深さ優先探索を行う.訪れた頂点が一つの強連結成分.
  4. 得られた強連結成分をグラフから取り除き,まだグラフが空でなければ 3 に戻る.

ステップ 1 が深さ優先探索一回分,ステップ 3,4 が合計で一回分です.

アルゴリズムの正しさ

頂点に番号を付ける以外に特にフラグをたてたりしていないのですが,この方法できちんと全ての強連結成分を調べ上げることができます.

まず,ステップ 1 ではグラフに対してトポロジカルソートのような番号付けを行っています.もし入力グラフが DAG であれば,当然トポロジカルソートによる順序付けそのものが各頂点の番号になります.また入力グラフが有向サイクルを含むグラフであったとしても「グラフの各強連結成分を一頂点に縮約し,それぞれの強連結成分の頂点の番号の中で最も大きな値を縮約後の頂点の番号とする」という処理を行うと,縮約後の番号は縮約後の DAG のトポロジカルソートになっています.

すなわち番号の最も大きな頂点を含む強連結成分に入る辺は存在しないので,グラフの辺を逆向きにすると,この強連結成分から出る辺が存在しないことになります.よって,最も大きな番号を持つ頂点からグラフ探索を行うと,この頂点を含む強連結成分の各頂点だけをかき集めることができます.
この強連結成分を取り除いた後も同様に,縮約後の DAG のトポロジカルソートで次に来る強連結成分に含まれる頂点が次に選ばれますので,以下同様に正しく強連結成分のみを集めることができます.