トポロジカルソートとは何か？

Question

トポロジカルソートとは何か？

IT Interview Practice · Accepted Answer

**Topological sort** は **DAG** (directed acyclic graph、有向非環グラフ) の頂点を線形に順序付けし、すべてのエッジ u->v に対して u が v **より前** にくるようにします。これは「与えられた依存関係のもとで、これらのタスクをどの順序で実行できるか？」という質問に答えます。

## 基本的な考え方

2つの一般的なアプローチがあります：**Kahn のアルゴリズム** (入次数が0のノードを繰り返し削除) または **DFS** (逆後順序)。有効な順序付けは **サイクルが存在しない場合のみ** 存在します。

## 例 (Kahn のアルゴリズム)

```python
from collections import deque

def topo_sort(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1                 # count incoming edges
    queue = deque([u for u in indeg if indeg[u] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1                 # "remove" the edge
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None  # None -> cycle

topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
```

## 計算量

- **時間:** O(V + E)。**空間:** O(V)。

## 使用場面 / 落とし穴

**ビルドシステム**、タスクスケジューリング、コース履修要件、依存関係解決に使用します。結果が V より短い場合、グラフは **サイクル** を持ちます (有効な順序は存在しません)。通常、順序付けは **一意ではありません**。

## なぜ重要なのか

依存関係の順序付けはあらゆる場所にあります — コンパイラ、パッケージマネージャー、スプレッドシート再計算、CI パイプライン。

Topological sort は有向グラフのサイクル検出としても機能します。

問題を「制約条件下での順序付け」と認識し、トポロジカルソートに頼ることは、シニアレベルの強い信号です。

基本的な考え方

例 (Kahn のアルゴリズム)

計算量

使用場面 / 落とし穴

なぜ重要なのか

関連する質問