強連結成分(SCC)とは

強連結成分(SCC, Strongly Connected Component) = 有向グラフにおいて、互いに行き来が可能な頂点の集合。

  • SCC を求めることを 強連結成分分解 という
  • 元の有向グラフが DAG でなくとも、そのグラフの SCC は DAG を形成する

スライド11

強連結成分分解の方法

処理の流れ

  1. 対象グラフ \(G\) の探索:頂点ラベリング
    1. 適当に選んだ \(G\) の未探索の頂点から深さ優先探索を行い、帰りがけ に頂点を番号ラベリングする
      • 番号は1つずつ増やしていく
    2. 未探索の頂点がなくなるまで繰り返す
      • 2回目以降の探索において、それ以前の探索で訪問済みの頂点は探索対象に含めない
  2. \(G\) の逆グラフ \(G^T\) を作成
    • 1で \(G\) に付与した番号ラベルを引き継ぐ
  3. 逆グラフ \(G^T\) の探索:SCC 分解
    1. 未探索のうち、番号ラベルが一番大きい頂点 からグラフ探索
    2. 探索した頂点の集合 = 1つの SCC
    3. 未探索の頂点がなくなるまで繰り返す

基本的な考え方(つまり何をやっているのか?)

説明の便宜上、SCC1 → SCC2 のパスが存在する場合、「SCC1 は SCC2 より上流にある」 と表現する。

  • \(G\) の頂点ラベリング
    • 目的:各頂点が属する SCC が他と比べて上流・下流どちらなのかの判断をつけること
    • 最大の番号ラベルを持つ頂点 = \(G\) の最も上流の SCC に属する頂点
      • 頂点 A からスタートする1回の深さ優先探索を行うと、A と同じ or A より下流の SCC の頂点はすべて探索できる
      • 帰りがけ探索でラベリングするので、上流 SCC には下流 SCC のどの頂点よりも番号が大きい頂点が最低1つ存在する
      • 未探索の頂点 B が残っていた場合、頂点 B は A よりも上流の SCC に属する
      • 次に頂点 B からスタートする深さ優先探索を行うと、探索された頂点全てに A より大きな番号が割り当てられる
  • 逆グラフ \(G^T\) の探索
    • 最大の番号ラベルを持つ頂点 = \(G^T\) の最も下流の SCC に属する頂点
      • 逆グラフなので、\(G\) とは上流・下流関係が逆転
    • 最下流の頂点から探索をスタートするので、たどり着ける頂点は同じ SCC に属するものだけ
      • つまり、1回の探索でたどった頂点は全てを同じ SCC のもの
    • よって「未探索のうち、最大ラベルのものから探索スタート」を繰り返せば、1回の探索につき1つ SCC が求められる

【NOTE】トポロジカルソート

この手法では、SCC は \(G^T\) において下流(\(G\) において上流)のものから順に求まる
→ 順にリストに格納していけば、トポロジカルソート済みの SCC リストが得られる

具体例

例題として、以下の有向グラフ \(G\) における SCC を求める。

スライド04

適当に選んだ頂点から深さ優先(帰りがけ探索)し、1から番号を増やしながらラベリング:

スライド05

まだラベルのない頂点があるので、その中から適当に頂点を選び、そこから同様に深さ優先探索(帰りがけ探索):

スライド06

\(G\) のエッジをすべて逆向きにしたグラフ \(G^T\) を用意:

スライド07

頂点のうち、ラベル番号が最大のものを選んでグラフ探索 → 通った頂点はすべて1つの SCC に属する

スライド08

未探索の頂点のうち、ラベル番号が最大のものを選んでグラフ探索 → 通った頂点はすべて1つの SCC に属する

スライド09

未探索の頂点のうち、ラベル番号が最大のものを選んでグラフ探索 → 通った頂点はすべて1つの SCC に属する

スライド10

すべての頂点を探索し、SCC が全て求まった:

スライド11