強連結成分分解の意味とアルゴリズム

更新 2021/03/07

深さ優先探索を2回すれば強連結成分分解できる。

強連結成分分解とは

有向グラフにおいて
「お互いに行き来できる   ⟺  \iff⟺ 同じグループ」を満たすように頂点をグループ分けすることを強連結成分分解と言います。
例えば図において頂点
aaa
 から
ccc
，ccc
 から
aaa
 はそれぞれ矢印をたどっていけるので同じグループ（強連結成分）に属します。一方，頂点
ddd
 から
ccc
 へのパスは存在しないので，ccc
 と
ddd
 は異なる強連結成分に属します。
図の場合，強連結成分分解は
{{a,b,c},{d,e},{f},{g}}\{\{a,b,c\},\{d,e\},\{f\},\{g\}\}{{a,b,c},{d,e},{f},{g}}
 となります。

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

前提知識として深さ優先探索が必要です。→深さ優先探索と幅優先探索

適当な頂点から深さ優先探索を行う，その際各頂点 $v$ に対して頂点 $v$ から進めなくなった順番 $t(v)$ を格納する。
グラフの矢印を全て逆向きにしたものに対して深さ優先探索を行う。その際 $t(v)$ が大きい頂点からスタートする。行き止まったところまでを一つの連結成分とする。

例

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

まず適当な頂点 $a$ から深さ優先探索をする。 $a→b→c→d→e→f$ まで行ってぶつかる。 $f$ から進めないので $t(f)=1$ とする。次に $e$ に戻ると $g$ に進める。 $g$ から進めないので $t(g)=2$ 。 $e$ に戻ると $e$ から進めないので $t(e)=3$ 。以下同様。
次に枝を逆向きにした有向グラフで深さ優先探索を行う。 $t(v)$ が一番大きい頂点 $a$ からスタート。 $a→c→b$ まで進んで行き止まるので $\{a,b,c\}$ が一つの連結成分。残った頂点の中で $t(v)$ が一番大きい頂点 $d$ からもう一度深さ優先探索。 $d→e$ と進んで行き止まるので $\{d,e\}$ が一つの連結成分。以下同様。

ちなみに深さ優先探索は線形時間なので，強連結成分分解のアルゴリズムの計算量も線形，つまり $O(|V|+|E|)$ です。

アルゴリズムの正しさの証明

証明の概略

アルゴリズムの正しさ出力した一つの頂点集合 $V'$ が確かに強連結成分であることを示す。2の深さ優先探索で得られる（頂点集合が $V'$ である）木を $T$ とし，その根を $v$ とする。

成分内の二つの頂点が互いに行き来できることの証明
成分内の任意の頂点 $u$ に対して，
(i)枝を逆向きにしたグラフで $v$ から $u$ へのパスがあるのでもとのグラフで $u$ から $v$ へのパスがある。
(ii) $t(v) > t(u)$ であることと(i)よりもとのグラフで $v$ から $u$ へのパスがある（→注）。
他の頂点からこの成分にはたどりつけないことの証明
$T$ から他の頂点には枝が伸びていないので，もとのグラフで他の頂点から $V'$ の頂点へはたどりづけない。

注：理由をちゃんと書くと少し長くなるので省略しました。難しくないので考えてみてください！

強連結成分分解という名前はかなり強そうです。

この記事の監修者

マスオ

高校数学の美しい物語の管理人。「わかりやすいこと」と「ごまかさないこと」の両立を意識している。著書に『高校数学の美しい物語』『超ディープな算数の教科書』。記事の誤植やわかりにくい等のご指摘はお気軽にメールください！