トポロジカルソート（グラフ→依存解決） — ビルド順や依存解決
「依存関係を持つタスクを順序付けする」典型アルゴリズムが トポロジカルソート。
Java での実装は、有向非巡回グラフ（DAG） を前提に、入次数管理（Kahn のアルゴリズム）や DFS を使います。ビルド順・依存解決・科目履修順などに応用できます。
基本の考え方
- 対象: 有向グラフ（頂点＝タスク、辺＝依存関係）。
- 条件: サイクルがあると順序付けできない。
- 目的: 「依存を満たす順序」で全頂点を並べる。
- 代表的アルゴリズム:
- Kahn のアルゴリズム（入次数法）
- 入次数が 0 のノードをキューに入れる → 取り出して順序に追加 → 出辺を削除 → 新たに入次数 0 になったノードを追加 → 繰り返し。
- DFS 法
- 再帰で探索し、終了時にスタックへ積む → 逆順に取り出す。
- Kahn のアルゴリズム（入次数法）
コード例（Kahn のアルゴリズム）
import java.util.*;
public class TopologicalSort {
public static List<String> topoSort(Map<String, List<String>> graph) {
// 入次数を数える
Map<String, Integer> indegree = new HashMap<>();
for (String node : graph.keySet()) {
indegree.putIfAbsent(node, 0);
for (String nei : graph.get(node)) {
indegree.put(nei, indegree.getOrDefault(nei, 0) + 1);
}
}
// 入次数0のノードをキューへ
Queue<String> q = new ArrayDeque<>();
for (var e : indegree.entrySet()) {
if (e.getValue() == 0) q.add(e.getKey());
}
List<String> order = new ArrayList<>();
while (!q.isEmpty()) {
String cur = q.poll();
order.add(cur);
for (String nei : graph.getOrDefault(cur, List.of())) {
indegree.put(nei, indegree.get(nei) - 1);
if (indegree.get(nei) == 0) q.add(nei);
}
}
// サイクル検出（全ノードを処理できなかった場合）
if (order.size() != indegree.size()) {
throw new IllegalStateException("Cycle detected!");
}
return order;
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("A", List.of("C"));
graph.put("B", List.of("C", "D"));
graph.put("C", List.of("E"));
graph.put("D", List.of("F"));
graph.put("E", List.of("F"));
graph.put("F", List.of());
System.out.println(topoSort(graph)); // [A, B, C, D, E, F] のような順序
}
}
例題で理解する
例題1: ビルド順の決定
- 依存:
compile→test→package→deploylint→compile
- 結果: lint → compile → test → package → deploy
Map<String, List<String>> build = Map.of(
"lint", List.of("compile"),
"compile", List.of("test"),
"test", List.of("package"),
"package", List.of("deploy"),
"deploy", List.of()
);
System.out.println(topoSort(build));
例題2: 科目履修順
- 依存:
- 「数学基礎」→「線形代数」→「機械学習」
- 「統計基礎」→「機械学習」
- 結果: 数学基礎 → 統計基礎 → 線形代数 → 機械学習
例題3: サイクル検出
- 依存: A→B, B→C, C→A
- 結果: IllegalStateException（サイクルあり）
テンプレート集
- 基本構造
Map<String, List<String>> graph = new HashMap<>();
graph.put("task1", List.of("task2", "task3"));
graph.put("task2", List.of("task4"));
graph.put("task3", List.of());
graph.put("task4", List.of());
List<String> order = topoSort(graph);
- サイクル検出
if (order.size() != graph.size()) {
throw new IllegalStateException("Cycle detected!");
}
- DFS 法（簡易版）
void dfs(String node, Set<String> visited, Deque<String> stack, Map<String,List<String>> g) {
visited.add(node);
for (String nei : g.getOrDefault(node, List.of())) {
if (!visited.contains(nei)) dfs(nei, visited, stack, g);
}
stack.push(node);
}
落とし穴と回避策
- サイクルがあると失敗: 必ず検出して例外やエラーを返す。
- 入次数の初期化忘れ: 存在しないノードも indegree に入れる。
- ビューの扱い:
entrySetで効率よく走査。 - 順序は一意でない: 複数の正解順序があり得る。
- 大規模グラフ: ノード数が多い場合は効率的なデータ構造（ArrayDeque, ArrayList）を選ぶ。
まとめ
- トポロジカルソートは「依存関係を持つタスクを順序付け」する基本アルゴリズム。
- Kahn のアルゴリズム（入次数法）と DFS 法が代表的。
- ビルド順・科目履修・依存解決などに応用できる。
- サイクル検出と複数解の存在を理解して使うと、実務でも安全に活用できる。
👉 練習課題として「モジュール依存関係を Map で表し、トポロジカルソートでビルド順を出力する」プログラムを書いてみると理解が深まります。