トポロジカルソート
トポロジカルソート
このレッスンで分かること
O(n + m)- トポロジカルソート (topological sort) は、有向非巡回グラフ (DAG, Directed Acyclic Graph) のノードを、すべての辺
u -> vについてuがvより前に並ぶよ…- 手順は次のとおりです
トポロジカルソート とは
有向非巡回グラフ (DAG) のノードを、すべての辺 u->v で u が v より前に来るように並べた配列を返す。
トポロジカルソート (topological sort) は、有向非巡回グラフ (DAG, Directed Acyclic Graph) のノードを、すべての辺 u -> v について u が v より前に並ぶよう線形に並べる操作です。実世界の応用は非常に多く、たとえば次のとおりです。
- ビルドシステムでのタスク実行順序 (
AがBに依存するならBが先) - 大学のカリキュラム (前提科目を先に履修)
- Make / Bazel / Gradle のターゲット解決
- レシピの調理順序 (玉ねぎを切ってから炒める)
本レッスンでは、ノード数 n と有向エッジリスト edges = [[u, v], ...] (u -> v の意味) を受け取って、トポロジカル順に並べた配列を返す topoSort(n, edges) を実装します。Kahn の 入次数ベース BFS アルゴリズム で書きます。
トポロジカルソートは「依存関係の解決」の代名詞。Kahn のアルゴリズムは入次数 = 0 のノードから順に取り出していくシンプルな手順。
Kahn のアルゴリズム
手順は次のとおりです。
- すべてのノードの 入次数 (in-degree) を計算する
- 入次数 0 のノードをキューに入れる (どこにも依存していないノード)
- キューが空になるまで繰り返す
- ノード
uを取り出して結果に追加 uの各出力先vの入次数を1減らす。0 になったらキューに追加
- ノード
- 結果配列の長さが
nと等しければ成功。少なければサイクルがあって不可能
図のポイント (テキスト併記)
- この例だと
[A, B, C, D, E]や[A, C, B, D, E]のような順序がトポロジカル順になります
この例だと [A, B, C, D, E] や [A, C, B, D, E] のような順序がトポロジカル順になります。順序が一意でないことに注意してください (テストケースでは入次数 0 のノードを ID 昇順で取り出して安定化します)。
Python での実装
Python
from collections import deque
def topoSort(n, edges):
indeg = [0] * n
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
indeg[v] += 1
queue = deque(i for i in range(n) if indeg[i] == 0)
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
queue.append(v)
return resultポイントは 入次数の管理。indeg[v] を 1 つずつ減らしていき、0 になったタイミングで「もう全ての前提タスクが終わった」とみなしてキューに入れます。
JavaScript での実装
JavaScript
function topoSort(n, edges) {
const indeg = new Array(n).fill(0);
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
indeg[v]++;
}
const queue = [];
for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
const result = [];
let head = 0;
while (head < queue.length) {
const u = queue[head++];
result.push(u);
for (const v of adj[u]) {
indeg[v]--;
if (indeg[v] === 0) queue.push(v);
}
}
return result;
}サイクル検出にも使える
Kahn のアルゴリズムは副作用として サイクル検出 にもなります。最終的に result.length < n なら、減らせなかったノードがあるということなので、循環依存が存在します。A -> B -> A のような依存関係はビルド不能なので、ビルドツールはここで「circular dependency」エラーを吐きます。
計算量
O(n + m)。BFS と同じ線形時間です。
Kahn のトポロジカルソートは BFS そのもの。入次数を 1 ずつ減らしていく挙動が「依存解消」の直感とぴったり一致する。
よくある間違い
1 つ目は 無向エッジ として扱ってしまい、adj[v].append(u) まで追加するケース。トポロジカルソートは 有向グラフ専用 なので、片方向しか追加してはいけません。2 つ目は入次数の更新を「ノード取り出し前」にやってしまい、計算が崩れるパターン。取り出してから、出力辺をたどって減らす が正しい順序です。3 つ目はサイクル時に空配列を返さずに途中までの結果を返してしまうこと。テストによっては result.length < n のとき空配列で返す仕様にしている場合もあるので注意します (本問題ではテストの DAG はサイクルなし)。
やってみよう
n=5, edges=[[0,1],[0,2],[1,3],[2,3],[3,4]]で[0,1,2,3,4]または[0,2,1,3,4](実装で異なる) のような順序が返る。- 完全に独立 (
edges=[]) なら[0,1,2,...,n-1]が返る。 - 鎖
[0,1],[1,2],[2,3]なら[0,1,2,3]確定。
ビルド順序、講義履修、依存解決。トポロジカルソートは現実世界の「順序問題」を一手に解く道具。
よくある質問
Q. トポロジカルソートはいつ使う？
A. 依存関係の順序を解決したいときに使います。タスクスケジューラ（A の前に B が必要）、ビルドシステム（依存ファイルの順）、コース履修順序などが代表的な応用例です。サイクルがある場合は順序が定義できず、検出も同時に可能です。
Q. Kahn 法と DFS 法の違いは？
A. Kahn 法は「入次数 0 のノードを順に取り出す」BFS ベース、DFS 法は「帰りがけ順を逆にする」方式です。実装の好みで選んで構いません。サイクル検出は Kahn 法だと「全ノード処理できなかった = サイクル」と判定できて分かりやすいです。
Q. 順序が複数あるときの安定性は？
A. トポロジカルソートは唯一解を保証しません。複数の妥当な順序があり得る場合、入力の順序・優先度キューの使用などで結果が変わります。決定的に同じ順序が欲しいときは、ノード ID 順の優先度キュー（小さい ID 優先）を併用してください。
次のレッスン
次は 2 部グラフ判定 で、無向グラフが 2 部グラフ（隣接ノードを 2 色で塗り分け可能かどうか）を BFS の彩色で判定する方法を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- トポロジカルソート の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. トポロジカルソート とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- Kahn のアルゴリズム (入次数を使う BFS) で実装すること
- 同点 (入次数 0 が複数) のときは ID が小さいノードを先に取り出すこと
- 有向エッジは片方向のみ追加すること
入出力例
test-cases.txt
topoSort(4, [[0,1],[1,2],[2,3]]) → [0,1,2,3]
topoSort(3, []) → [0,1,2]
topoSort(4, [[0,1],[0,2],[1,3],[2,3]]) → [0,1,2,3]
topoSort(5, [[0,1],[0,2],[1,3],[2,3],[3,4]]) → [0,1,2,3,4]
topoSort(1, []) → [0]
topoSort(6, [[0,1],[0,2],[1,3],[2,3],[3,4],[3,5]]) → [0,1,2,3,4,5]