算法刷题系列（三十九）：拓扑排序——安排有向无环图的依赖顺序

算法刷题系列（三十九）：拓扑排序——安排有向无环图的依赖顺序

课程先修、任务依赖和构建顺序都可以表示成有向边。若 u → v 表示 u 必须先于 v，拓扑序就是一个让每条边都从较早位置指向较晚位置的顶点排列。只有有向无环图（DAG）才存在拓扑序。

Kahn 算法

顶点的入度是指向它的边数。任何非空 DAG 至少有一个入度为零的顶点：若每个顶点入度都大于零，沿着前驱不断回走，在有限图中必然重复顶点，从而形成环。

Kahn 算法把所有入度为零的顶点放入队列，取出并加入序列，再删除它的出边（邻居入度减一）。邻居入度降到零时入队。关键不变量是：队列中的节点已经没有尚未处理的前驱，可以安全地安排在当前序列末尾。

Java 实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class TopologicalSort {
    public static List<Integer> sort(List<List<Integer>> graph) {
        int n = graph.size();
        int[] indegree = new int[n];
        for (List<Integer> neighbors : graph) {
            for (int neighbor : neighbors) {
                if (neighbor < 0 || neighbor >= n) {
                    throw new IllegalArgumentException("neighbor out of range");
                }
                indegree[neighbor]++;
            }
        }

        Deque<Integer> ready = new ArrayDeque<>();
        for (int node = 0; node < n; node++) {
            if (indegree[node] == 0) {
                ready.addLast(node);
            }
        }

        List<Integer> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            int node = ready.removeFirst();
            order.add(node);
            for (int neighbor : graph.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    ready.addLast(neighbor);
                }
            }
        }
        return order.size() == n ? order : new ArrayList<>();
    }
}

空列表代表发现环；顶点数为零时，空列表同时也是合法的空拓扑序，调用方若要区分这两种情况，可返回包含 hasCycle 字段的结果对象。

Python 实现

from __future__ import annotations

from collections import deque

def topological_sort(graph: list[list[int]]) -> list[int] | None:
    n = len(graph)
    indegree = [0] * n
    for neighbors in graph:
        for neighbor in neighbors:
            if not 0 <= neighbor < n:
                raise ValueError("neighbor out of range")
            indegree[neighbor] += 1

    ready = deque(node for node, degree in enumerate(indegree) if degree == 0)
    order: list[int] = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                ready.append(neighbor)
    return order if len(order) == n else None

assert topological_sort([[2], [2], [3], []]) is not None
assert topological_sort([[1], [2], [0]]) is None
assert topological_sort([]) == []

正确性与复杂度

每次加入队列的顶点当前入度为零，说明未处理的前驱边数为零，因此把它追加到结果不会违反任何依赖。处理它时恰好移除所有出边，使后继入度反映剩余未处理前驱。若最终处理了全部顶点，所得顺序满足每条边的先后约束；若仍有顶点未处理，它们的剩余子图中每个顶点都有未消除入边，必含有向环。

每个顶点入队、出队至多一次，每条边处理一次，时间为 O(V+E)；邻接表和入度、队列使用 O(V+E) 空间。

多解、优先级与常见错误

• 拓扑序通常不唯一。若需要字典序最小的序列，可用最小堆替换普通队列，复杂度增加为 O((V+E) log V)。
• 不能只根据初始入度为零的节点判断是否有环；必须把队列处理到结束，并检查结果顶点数。
• 重边会在计算与减少入度时各自计数一次，因此只要邻接表一致，算法仍正确。
• 边方向要与“谁依赖谁”的约定一致。若 u 依赖 v，应建边 v → u。
• 有环时不应返回看似有效的部分序列并当作完整答案；必须明确告知无解或返回环检测状态。

Kahn 算法把依赖约束转换成可反复移除的零入度节点。处理数量不足 V 本身就是环检测，不需要额外再运行一次 DFS。