DFSの後順によるトポロジカルソート
DFSを実行し、隣接頂点をすべて探索し終えた各頂点をスタックに積み、その後スタックから取り出して有効なトポロジカル順序を作ります。
「DFSの後順によるトポロジカルソート」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
DFSベースのトポロジカルソートの考え方
2つ目の古典的なトポロジカルソートアルゴリズムでは、ポストオーダー処理を伴うDFSを使用します。ノードのすべての隣接ノード（およびその子孫）を完全に探索した後、そのノードをスタックにプッシュします。すべてのノードの処理が終わったら、スタックからポップしてトポロジカル順序を読み取ります。すべての依存先の後にスタックへプッシュされたノードは、順序では先に来るため、ポストオーダーを反転したものがトポロジカルソートになります。
ポストオーダーの直感
コースAを受講するにはコースBが必要な依存関係グラフを考えてみます。DFSがAを訪問すると、まずBへ再帰します。Bには前提条件がないため、先に処理を終えて最初にプッシュされます。その後、Aの処理が終わってプッシュされます。スタックからポップすると出力はA、Bの順になりますが、最後に反転することでB、Aの順になります。つまり、最初にBを受講し、その後Aを受講します。ポストオーダーでは依存先が依存元より先にプッシュされるため、反転したスタックは有効なトポロジカル順序になります。
3色DFSによるサイクル検出
訪問状態として3つの状態を使用します。WHITE (0) = 未訪問、GREY (1) = 現在処理中（DFSの呼び出しスタック内）、BLACK (2) = 処理完了です。後退辺、つまりGREYのノードへ向かうエッジは、サイクルを示します。BLACKのノードへのエッジは安全です（そのノードはすでに完全に探索されています）。この3色方式によって、有向グラフ内のすべてのサイクルを正しく検出できます。
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)DFSによるトポロジカルソートの完全な実装
ノードに色を付け、ポストオーダーでスタックにプッシュし、サイクルを検出したらFalseを返す再帰的なDFSを使用します。すべてのノードを訪問した後、スタックを反転するとトポロジカル順序が得られます。
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))スタックオーバーフローを避ける反復DFS
大規模なグラフでは、Pythonの再帰制限（デフォルトは1000）が問題になる可能性があります。明示的なスタックを使う反復DFSでこれを回避できます。ポイントは、最初に(node, False)をプッシュすることです。Falseでポップされた場合は、(node, True)（「探索後にここへ戻る」という意味）をプッシュし、未訪問の隣接ノードをすべてFalse付きでプッシュします。Trueでポップされた場合は、そのノードをBLACKにして結果用スタックへプッシュします。
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]DFSとKahn法の比較
どちらもO(V + E)で動作します。主な違いは次のとおりです。Kahn法（BFS）は依存関係の早いものから自然にノードを生成し、サイクル検出も長さのチェックだけで簡単に行えます。DFSのポストオーダーは再帰的に動作し、後退辺を明示的に検出します。反転せずに前向きの順序で結果を得たい場合はKahn法が適しています。SCC検出など、別の目的で完全なポストオーダーが必要な場合はDFSが適しています。どちらも面接では十分に通用します。
木とDAGにおけるポストオーダー
木では、ポストオーダーによって左部分木 → 右部分木 → ルートの順に訪問します。DAGでは、ポストオーダーDFSによって、あるノードを処理する前にそのノードのすべての依存先を訪問します。これは、複数の前駆ノードや任意のグラフ構造へ一般化した同じ考え方です。DFS木のルート（開始ノード）は、その子孫の中では最後にプッシュされるため、反転したスタックでは最初に現れます。これは、前駆ノードを持たないノードにとって正しいトポロジカル上の位置です。
Alien Dictionary（LeetCode 269）
Alien Dictionaryでは、異星の言語でソートされた単語のリストが与えられ、文字の順序を導き出します。隣り合う単語を文字ごとに比較して最初の相違点を見つけると、c1がc2より前に来ることを意味するエッジc1 → c2が得られます。このようなエッジをすべて集め、トポロジカルソートを実行して異星の文字順を生成します。サイクルが存在する場合、その順序は無効です。
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'制約付きトポロジカルソート
元のリストにある要素の相対的な順序を維持するなど、追加の制約を満たすトポロジカルソートを求める問題もあります。Kahn法にカスタム優先度付きキューや事前ソートを組み合わせます。各ステップでキューの内容を安定ソートすることで、元の相対順序を維持します。このような制約付きの変形問題では、アルゴリズムの柔軟性についてのより深い理解が試されます。
トポロジカルソート問題の見分け方
面接問題でトポロジカルソートを示す手がかりとなる表現には、「依存関係が与えられる」、「前提条件」、「タスクの順序」、「ビルド順序」、「すべてのタスクを完了できるか」、「有効な順序を見つける」などがあります。いくつかの項目を他の項目より先に処理しなければならない順序付けの問題では、有向グラフを構築してKahn法またはDFSによるトポロジカルソートを適用します。同じ問題でサイクル検出も求められることがよくあります。
DFSとKahn法の出力の比較
同じグラフに対して、DFSとKahn法は異なる有効なトポロジカル順序を生成することがあります。どちらも正解です。DAGには複数の有効なトポロジカル順序が存在する場合があります。正しさを検証するには、グラフ内のすべてのエッジu → vについて、出力順序でuがvより前に現れることを確認します。辞書順最小など特定の順序が必要な面接問題では、最小ヒープを使ったKahn法を使用します。DFSのポストオーダーでは、辞書順最小の順序は自然には生成できません。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について理解度を確認します。
レッスンのまとめ
このレッスンでは、DFSのポストオーダーによるトポロジカルソートでは、すべての依存先を探索した後にノードをプッシュすること、3色マーキング（WHITE/GREY/BLACK）によってGREYノードへの後退辺を利用してサイクルを検出すること、そしてポストオーダーのスタックを反転すると有効なトポロジカル順序が得られることを学びました。次は、Course Schedule IとIIの問題にトポロジカルソートを直接適用します。
よくある質問
「DFSの後順によるトポロジカルソート」レッスンは無料ですか？
はい。「DFSの後順によるトポロジカルソート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「DFSの後順によるトポロジカルソート」で何を学びますか？
DFSを実行し、隣接頂点をすべて探索し終えた各頂点をスタックに積み、その後スタックから取り出して有効なトポロジカル順序を作ります。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「DFSの後順によるトポロジカルソート」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- Kahnのアルゴリズム：BFSトポロジカルソート
- DFSの後順によるトポロジカルソート
- Course Schedule IとII
- Kosarajuによる強連結成分