Kosarajuによる強連結成分
元のグラフでDFSを実行して終了順を取得し、グラフを転置してから終了順の逆順にもう一度DFSを実行し、SCCを特定します。
「Kosarajuによる強連結成分」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
強連結成分の定義
有向グラフの強連結成分（SCC）とは、その集合内の任意のノードから他の任意のノードへ到達する経路が存在する、極大なノード集合です。たとえば、ノードA、B、Cがサイクル（A→B→C→A）を形成している場合、それらはすべて同じSCCに属します。自己ループを持たない単一のノードも、それ自体で1つのSCCです。SCCによって、有向グラフの循環構造を明らかにできます。
Kosaraju法：2回のDFSパス
Kosaraju法は、2回のDFSパスを使ってO(V + E)でSCCをすべて見つけます。パス1では、元のグラフに対してDFSを実行し、完了順（ポストオーダー）にノードをスタックへプッシュします。パス2では、転置（反転）グラフに対して、完了順を逆にした順序（スタックからポップした順序）でDFSを実行します。パス2における各DFS木が1つのSCCになります。
Kosaraju法が機能する理由
パス1では、DFS木の完了が最後になるSCCは、他のSCCへの出ていくエッジを持たないSCCです（縮約DAGにおける「シンク」SCC）。転置グラフでは、このSCCは他のSCCから入ってくるエッジを持たないため、そこからパス2のDFSを開始すると、そのSCC内にとどまります。以降のパス2のDFSも、それぞれのSCC内にとどまります。これは、SCC間のすべてのエッジが反転され、すでに訪問済みのSCCへ向かうためです。
パス1：完了順の構築
元のグラフに対してDFSを実行し、各ノードの処理が終わった後（ポストオーダー）にそのノードをスタックへプッシュします。このパスでは成分自体には関心を持たず、完了順だけを求めます。最後に処理を終えるノードは、縮約DAGにおける「ソース」SCCに属します。
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graphパス2：転置グラフでのDFS
完了順のスタックからノードをポップし（完了時刻が最も大きい順）、転置グラフに対してDFSを実行します。未訪問のノードから開始する各DFSは、正確に1つのSCCを見つけます。このDFSで到達したすべてのノードに、同じ成分に属するという印を付けます。
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarグラフの転置
転置グラフでは、すべてのエッジの向きを反転します。元のグラフにu → vがある場合、転置グラフにはv → uがあります。転置してもSCCは保持されます。元のグラフでAとBが同じSCCに属している場合、すべての経路が反転しても互いに接続されたままなので、転置グラフでも同じSCCに属します。上で示したように入力の解析中に転置グラフを構築すれば、別途転置する手順を省略できます。
大規模グラフ向けの反復版
大規模なグラフでは、Pythonの再帰制限を回避するため、再帰的DFSを明示的なスタックを使う反復的DFSに置き換えます。反復版ではノードをスタックに積んで処理し、帰りがけ順を再現するために別の「return」マーカーを保持します。
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')Tarjan法：SCCの別解
Tarjanのアルゴリズムは、Kosaraju法の2回の走査と比較して、1回のDFS走査でSCCを見つけます。ノードのスタックを保持し、各ノードに発見時刻とローリンク値を割り当てます。あるノードの発見時刻とローリンク値が等しい場合、そのノードはSCCのルートです。Tarjan法は実装がやや複雑ですが、転置グラフを構築する必要がありません。どちらもO(V + E)です。
SCCの応用
SCCは次のような用途で使用されます。(1) コンパイラの最適化 — 相互再帰する関数の特定。(2) ソーシャルネットワーク分析 — 密接に結び付いたコミュニティの発見。(3) 2-SAT問題 — 2リテラル節の充足可能性の判定。(4) ウェブクローリング — 相互リンクが密なページ群の特定。(5) 縮約DAG — SCCを見つけた後、グラフの縮約はDAGになるため、閉路を含むグラフに対してトポロジカルな分析を行えます。
縮約DAG
有向グラフの縮約では、各SCCを1つのノードにまとめ、構成要素であるSCC間に辺が存在する場合に、2つのスーパー ノードの間に辺を追加します。結果は常にDAGになるため、トポロジカルソートを実行できます。これにより、DAGでのみ機能するアルゴリズム（DPなど）を、縮約上で処理することで一般の有向グラフに適用できます。
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]SCCの数とグラフの性質
有向グラフに含まれるSCCの数から、そのグラフの閉路構造が分かります。DAGにはn個のSCCがあります（各ノードがそれぞれ独立したSCCです）。強連結グラフにはSCCがちょうど1個あります。一般に、SCCを縮約すると、それらはDAGを形成します。これが縮約です。縮約DAGに一意なソース（入次数0のノード）と一意なシンク（出次数0のノード）がある場合、特定の連結性が成り立ちます。これらの性質は、最小限の辺を追加した後の到達可能性を問う問題で検証されます。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、SCCは、すべてのノードから他のすべてのノードへ到達できる極大集合であること、Kosaraju法は2回のDFS走査を使用し、最初は元のグラフで完了順を求め、次に転置グラフを走査すること、そして任意の有向グラフを縮約するとDAGになり、さらなる分析に利用できることを学びました。次は、挿入、検索、プレフィックス操作のためのTrieNodeデータ構造を構築します。
よくある質問
「Kosarajuによる強連結成分」レッスンは無料ですか？
はい。「Kosarajuによる強連結成分」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「Kosarajuによる強連結成分」で何を学びますか？
元のグラフでDFSを実行して終了順を取得し、グラフを転置してから終了順の逆順にもう一度DFSを実行し、SCCを特定します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「Kosarajuによる強連結成分」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- Kahnのアルゴリズム：BFSトポロジカルソート
- DFSの後順によるトポロジカルソート
- Course Schedule IとII
- Kosarajuによる強連結成分