SCC | Notion

SCCとは強連結成分のこと. 名前がかっこいいね.

雑な説明

どんなDirected GraphもSCCを求めればDAGになる. 閉路を一つの頂点とみなす.

ついでにDAGのトポロジカルソートも同時に行える.

丁寧な説明

有向グラフにおいてお互いに行き来が可能な頂点の集合.

具体的な方法

有向グラフ $G$ を考える. また逆グラフを $G^T$ と表記する.

$G$ の任意の頂点 $v$ から帰りがけDFSをして0からラベル付けをしていく.
1を未探索の頂点がなくなるまで繰り返す.
$G^T$ に上記の処理でつけたラベルを移す.
$G^T$の探索を行う.
- 未探索の中で一番ラベルが大きい頂点から探索を行う.
- 探索した頂点の集合が1つのSCC.
- 未探索の頂点がなくなるまで上記2つの処理を繰り返す.

簡単な説明

1と2でラベル付け

SCCが他のSCCと比べて上流下流なのかの判断をつけるため.
最大のラベルを持っている頂点が $G$ の最も上流のSCCに属する頂点.(DFS帰りがけで探索しているため.)
- 一回目の探索で見つけられなかった頂点は必ず初回の探索のどの頂点よりも上流のSCCに属す.

4での $G^T$ の探索

参考