トポロジカルソート
最終更新
有向非巡回グラフ（DAG）のトポロジカルソートとは、すべての辺 u → v について u が v より前に来るような、頂点の線形な並べ方です。「各前提条件が先に完了するように、これらのタスクをどの順序で実行できるか？」といった問いに答えます。上の再生を押すと、カーンのアルゴリズムが妥当な順序で頂点を取り出す様子を確認できます。
カーンのアルゴリズムは、残りの入辺を持たない頂点（入次数 0）を繰り返し取り出して順序に追加し、その出辺を取り除きます。これにより新たな入次数 0 の頂点が現れることがあります。DAG 上でのみ機能します。閉路が存在すると、一部の頂点は決して入次数 0 に達せず、妥当な順序は存在しません。実行時間は O(V + E) です。
時間計算量と空間計算量
| 指標 | 計算量 | 備考 |
|---|---|---|
| 時間 | O(V + E) | 各頂点は一度出力され、各辺は一度取り除かれる |
| 空間 | O(V) | 入次数のカウント + 準備集合 + 順序 |
| 必要条件 | DAG | 閉路にはトポロジカルソートが存在しない |
| 結果 | 一意ではない | 妥当な順序は複数存在しうる |
ステップごと（カーンのアルゴリズム）
| ステップ | 何が起こるか |
|---|---|
| 1 | 各頂点の入次数（入辺の数）を計算する。 |
| 2 | 入次数 0 のすべての頂点を準備集合に集める。 |
| 3 | 準備集合から頂点を取り出し、出力順序に追加する。 |
| 4 | その各後続頂点の入次数を 1 減らす。 |
| 5 | 入次数 0 に達した後続頂点は準備集合に加わる。 |
| 6 | 準備集合が空になるまで繰り返す。 |
実例による手順
辺 A→C, B→C, C→D, C→E, D→F, E→F を持つ DAG のソート（初期入次数 A:0 B:0 C:2 D:1 E:1 F:2）:
| ステップ | 準備集合 | 順序 | 動作 |
|---|---|---|---|
| 0 | {A, B} | [] | A と B は入次数 0 で始まるため、どちらも準備完了。 |
| 1 | {B} | [A] | A を出力。辺 A→C により C の入次数が 2 → 1 に下がる。 |
| 2 | {C} | [A, B] | B を出力。辺 B→C により C が 1 → 0 に下がり、C が準備完了になる。 |
| 3 | {D, E} | [A, B, C] | C を出力。辺 C→D と C→E により D と E が 0 に下がり、どちらも準備完了になる。 |
| 4 | {E} | [A, B, C, D] | D を出力。辺 D→F により F の入次数が 2 → 1 に下がる。 |
| 5 | {F} | [A, B, C, D, E] | E を出力。辺 E→F により F が 1 → 0 に下がり、F が準備完了になる。 |
| 6 | {} | [A, B, C, D, E, F] | F を出力。準備集合は空で、6 頂点すべてが並んだ — 完了。 |
トポロジカルソートを使うべきとき
| 使うべきとき | 避けるべきとき |
|---|---|
| 依存関係を守る順序が必要なとき（ビルド手順、パッケージのインストール、コースの前提条件）。 | グラフが無向のとき — トポロジカル順序は有向グラフに対してのみ定義される。 |
| グラフが DAG で、任意の妥当な線形順序が欲しいとき。 | グラフに閉路が含まれる可能性があり、それでも全順序が必要なとき（存在しない）。 |
| 閉路を安価に検出したいとき — 失敗したトポロジカルソートは閉路の存在を証明する。 | 何らかの重みに基づく最短または最適な順序が必要なとき。素朴なトポロジカルソートは重みを無視する。 |
順序を O(V + E) で一度だけ処理するとき。 | 辺が絶えず変化し、更新のたびに再ソートが必要なとき。増分的な構造の方が適する。 |
Topological Sortのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なTopological Sortの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのTopological Sortのコード
Python
1from collections import deque2
3
4def topological_sort(graph):5 # Kahn's algorithm: repeatedly remove nodes with no incoming edges6 in_degree = {node: 0 for node in graph}7 for node in graph:8 for neighbor in graph[node]:9 in_degree[neighbor] += 110 queue = deque(node for node in graph if in_degree[node] == 0)11 order = []12 while queue:13 node = queue.popleft()14 order.append(node)15 for neighbor in graph[node]:16 in_degree[neighbor] -= 117 if in_degree[neighbor] == 0:18 queue.append(neighbor)19 if len(order) != len(graph):20 raise ValueError("Graph has a cycle, no topological order")21 return order22
23
24graph = {25 "shirt": ["tie", "jacket"],26 "tie": ["jacket"],27 "pants": ["shoes", "jacket"],28 "socks": ["shoes"],29 "shoes": [],30 "jacket": [],31}32
33print(" -> ".join(topological_sort(graph)))JavaScriptでのTopological Sortのコード
JavaScript
1const graph = {2 A: ["C"],3 B: ["C", "D"],4 C: ["E"],5 D: ["F"],6 E: ["F"],7 F: [],8};9
10// Kahn algorithm: repeatedly take a node with no incoming edges11function topologicalSort() {12 const inDegree = {};13 for (const node in graph) inDegree[node] = 0;14 for (const node in graph) {15 for (const next of graph[node]) inDegree[next]++;16 }17 const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);18 const order = [];19 while (queue.length > 0) {20 const node = queue.shift();21 order.push(node);22 for (const next of graph[node]) {23 if (--inDegree[next] === 0) queue.push(next);24 }25 }26 if (order.length !== Object.keys(graph).length) {27 throw new Error("Graph has a cycle");28 }29 return order;30}31
32console.log("Topological order:", topologicalSort().join(" -> "));JavaでのTopological Sortのコード
Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 // DAG: an edge u -> v means u must come before v9 List<List<Integer>> adj = List.of(10 List.of(2),11 List.of(2, 3),12 List.of(4),13 List.of(4),14 List.of(5),15 List.of()16 );17 int[] inDegree = new int[n];18 for (List<Integer> next : adj) {19 for (int v : next) inDegree[v]++;20 }21
22 // Kahn: start from every node with no prerequisites23 Queue<Integer> queue = new ArrayDeque<>();24 for (int i = 0; i < n; i++) {25 if (inDegree[i] == 0) queue.add(i);26 }27
28 StringBuilder order = new StringBuilder("Topological order:");29 while (!queue.isEmpty()) {30 int node = queue.poll();31 order.append(" ").append(node);32 for (int next : adj.get(node)) {33 if (--inDegree[next] == 0) queue.add(next);34 }35 }36 System.out.println(order);37 }38}C++でのTopological Sortのコード
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Directed acyclic graph: adj[u] lists nodes that depend on u7 std::vector<std::vector<int>> adj = {8 {}, // 09 {}, // 110 {3}, // 2 -> 311 {1}, // 3 -> 112 {0, 1}, // 4 -> 0, 113 {0, 2}, // 5 -> 0, 214 };15 int n = static_cast<int>(adj.size());16 std::vector<int> inDegree(n, 0);17 for (const auto& neighbors : adj) {18 for (int v : neighbors) ++inDegree[v];19 }20 // Kahn's algorithm: start from nodes with no incoming edges21 std::queue<int> ready;22 for (int u = 0; u < n; ++u) {23 if (inDegree[u] == 0) ready.push(u);24 }25 std::cout << "Topological order: ";26 while (!ready.empty()) {27 int u = ready.front();28 ready.pop();29 std::cout << u << " ";30 // Removing u unlocks neighbors whose in-degree drops to 031 for (int v : adj[u]) {32 if (--inDegree[v] == 0) ready.push(v);33 }34 }35 std::cout << "\n";36 return 0;37}CでのTopological Sortのコード
C
1#include <stdio.h>2
3#define N 64
5int main(void) {6 // Directed acyclic graph: adj[u][v] = 1 means an edge u -> v7 int adj[N][N] = {0};8 adj[2][3] = 1;9 adj[3][1] = 1;10 adj[4][0] = 1;11 adj[4][1] = 1;12 adj[5][0] = 1;13 adj[5][2] = 1;14 int inDegree[N] = {0};15 for (int u = 0; u < N; u++) {16 for (int v = 0; v < N; v++) inDegree[v] += adj[u][v];17 }18 // Kahn's algorithm: start from nodes with no incoming edges19 int queue[N];20 int head = 0, tail = 0;21 for (int u = 0; u < N; u++) {22 if (inDegree[u] == 0) queue[tail++] = u;23 }24 printf("Topological order: ");25 while (head < tail) {26 int u = queue[head++];27 printf("%d ", u);28 // Removing u unlocks neighbors whose in-degree drops to 029 for (int v = 0; v < N; v++) {30 if (adj[u][v] && --inDegree[v] == 0) queue[tail++] = v;31 }32 }33 printf("\n");34 return 0;35}トポロジカルソートに関するよくある質問
トポロジカルソートは何に使われますか？
各依存関係が、それを必要とするものより前に来るようにタスクを並べます。実際の用途には、ビルドシステムやパッケージマネージャー（先に依存関係をコンパイル）、前提条件付きのコース編成、表計算の数式評価順序などがあります。
トポロジカルソートの時間計算量はどれくらいですか？
カーンのアルゴリズムも DFS ベースの手法も
O(V + E) の時間で動作します。各頂点が一度処理され、各辺が一度調べられるためです。追加で O(V) の空間を使います。なぜトポロジカルソートには DAG が必要なのですか？
有向閉路は矛盾を生みます。
a が b より前に来る必要があり、かつ b が a より前に来る必要があるなら、どんな線形順序も両方を満たせません。したがってトポロジカルソートは、グラフが有向非巡回グラフであるとき、かつそのときに限り存在します。カーンのアルゴリズムは、すべての頂点を出力する前に終了したときに閉路を検出します。カーンのアルゴリズムと DFS によるトポロジカルソートの違いは何ですか？
カーンのアルゴリズムは反復的で BFS に似ています。入次数 0 の頂点を繰り返し取り除くため、閉路検出と順序付けが完全に明示的になります。DFS の手法は頂点を再帰的に訪問し、各頂点の再帰が終わるたびに順序の先頭に追加して、完了時刻の逆順を生成します。どちらも
O(V + E) です。カーンは深い再帰を避け準備集合を自然に示し、DFS は多くの場合書くのが短くて済みます。通常のソートではなくトポロジカルソートをいつ使うべきですか？
順序が比較可能なキーではなく、要素間の依存関係で定義される場合にトポロジカルソートを使います。
O(n log n) のマージソートのような比較ソートは値で並べますが、トポロジカルソートは「前に来なければならない」という辺で並べ、比較ソートと違って同じ入力に対して多くの妥当な答えを生成できます。トポロジカルソートの結果は一意ですか？
通常は一意ではありません。2 つ以上の頂点が同時に準備完了（入次数 0）になるたびに、任意の順序で出力できるため、ほとんどの DAG は複数の妥当なトポロジカル順序を許します。順序が一意になるのは、各ステップでちょうど 1 つの頂点だけが準備完了である場合だけで、これは DAG が単一の鎖（ハミルトン路）を成すときに起こります。
関連リソース
その他の可視化
