求有向图的拓扑序。

核心回答

用Kahn算法：建立邻接表和每个顶点的入度，把入度为0的顶点加入队列；每次取出一个顶点写入结果，将其所有出边对应后继的入度减一，新变成0的后继入队。若最终输出顶点数不足n，图中存在环，没有完整拓扑序。

时间O(V+E)，空间O(V+E)。拓扑序只要求每条u→v的边中u出现在v之前，通常不唯一。

实现

约定顶点编号0到n-1，edges中的(u,v)表示u必须先于v。函数有环返回None，空图返回空列表，避免两种结果混淆。

from collections import deque


def topological_order(n, edges):
    if n < 0:
        raise ValueError("n must be non-negative")
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("vertex out of range")
        graph[u].append(v)
        indegree[v] += 1
    ready = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                ready.append(v)
    return order if len(order) == n else None

重复边在邻接表与入度中都按相同次数处理，因此不会破坏结果；若业务认为重复依赖应去重，建图时统一去重即可。

为什么能判环

入度为0表示剩余图中没有未满足前置依赖，放入结果是安全的。DAG若还剩顶点，就必有至少一个入度为0的点；否则不断沿前驱回溯，有限顶点中必重复，构成环。

若队列耗尽仍有未输出顶点，它们被环或依赖环的路径阻塞。注意剩余顶点不一定全在环上；要给出具体环，可再做DFS颜色标记或强连通分量分析。

例如边0→1、0→2、1→3、2→3，初始只有0可选；移除0后1、2都可选，随后才能输出3，所以[0,1,2,3]与[0,2,1,3]均合法。孤立点也必须出现在完整结果中。

追问

字典序最小怎么办？ 用最小堆替代普通队列，每次取最小可选顶点，时间变为O(E+VlogV)。

能直接作为并行调度吗？ 同一时刻就绪的独立任务可以并行，但应在前置任务真正成功后再释放后继；排序时模拟删除与真实执行完成不是同一事件，失败和取消还需单独策略。

参考资料