什么是拓扑排序？

Question

什么是拓扑排序？

Accepted Answer

**拓扑排序**将**DAG**（有向无环图）的顶点进行线性排序，使得每条边 u->v 都有 u **在** v **之前**。它回答了这个问题：「在给定任务依赖关系的情况下，我应该按什么顺序执行这些任务？」

## 思路

两种常见方法：**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 流水线。

拓扑排序同时也可用于有向图的循环检测。

认识到问题是「有约束的排序」并使用拓扑排序是高级工程师的标志。