拓扑排序

拓扑排序（topological ordering）把有限有向图的全部顶点排成一个线性顺序，使每条有向边的起点都在终点之前。这样的顺序存在，当且仅当图是有向无环图（DAG）。它保留依赖关系，却通常不规定彼此无依赖顶点的相对位置，因此结果可能不唯一。

例如，有向边为 $a\to c,b\to c,c\to d,b\to e,e\to f,d\to f$。一个拓扑顺序为 $a,b,c,e,d,f$：$c$ 需等到 $a,b$ 之后，$f$ 需等到 $d,e$ 之后。这里的“排序”不是按顶点大小比较，而是寻找符合全部先后约束的排列。

一条边只要求起点位置小于终点，不要求两个顶点在顺序中相邻。

入度零顶点与Kahn算法

某顶点若还有未处理前驱，就不能立刻放到结果末尾。若它在剩余图中的入度为零，则所有前驱都已处理，可以安全选入。Kahn算法维护一个装有这类顶点的队列：取出一个，追加到顺序中，再删除它的全部出边；某个后继的剩余入度因此降为零时，就加入队列。

主例取初始队列为 $[a,b]$，顶点出边按上面列举的次序检查。完整过程为：

本轮取出	已产生的顺序	更新后的队列	本轮使谁入度归零
a	a	b	无，c仍有来自b的边
b	a,b	c,e	c、e
c	a,b,c	e,d	d
e	a,b,c,e	d	无，f仍有来自d的边
d	a,b,c,e,d	f	f
f	a,b,c,e,d,f	空	无

例如删去 $e\to f$ 时，$f$ 还不能入队，因为边 $d\to f$ 仍来自未处理顶点。只看到某一个前驱完成就立即安排任务，会漏掉其余约束。

不变量、正确性与环检测

算法维护两个不变量：每个未处理顶点的计数等于来自未处理顶点的入边数；队列包含所有计数为零且尚未取出的顶点。初始用原图入度建立这两个条件。取出 $u$ 后，它不再属于剩余图；对每条 $u\to v$ 恰把 $v$ 的计数减一，正好删除这一条剩余入边。计数第一次归零才入队，且不会再增加，所以每个顶点至多入队一次，不变量保持。

若算法处理了全部顶点，则任意边 $u\to v$ 在选入 $v$ 时都已被删除；否则 $v$ 仍有来自未处理 $u$ 的入边，不可能计数为零。因此 $u$ 必先于 $v$，所得顺序满足所有边，正确。

若队列为空却仍有未处理顶点，这些顶点在剩余图中入度均正。任取其中一点，沿进入边不断找前驱；前驱始终留在有限剩余图中，所以必有顶点重复，重复之间形成有向环。因此失败确实证明原图含环。反过来，若存在有向环，环上每点只要前驱未处理就不能计数归零；不可能由环上某一点首先被处理，所以无法输出全部顶点。这完成了成功与失败两种结果的正确性证明。

可运行的Python实现

顶点编号为 $0,\dots ,n-1$，边为二元组 (起点, 终点)。函数不改写输入，返回顶点编号列表；含环时抛出异常。它按编号把初始入度零顶点入队，随后用先进先出队列；这给出可复算的一个顺序，并不保证字典序最小。

Python 3

from collections import deque

def topological_order(n, edges):
    if not isinstance(n, int) or n < 0:
        raise ValueError("invalid vertex count")
    edges = list(edges)
    adjacency = [[] for _ in range(n)]
    indegree = [0] * n
    seen = set()
    for u, v in edges:
        if not (isinstance(u, int) and isinstance(v, int)
                and 0 <= u < n and 0 <= v < n):
            raise ValueError("invalid endpoint")
        if (u, v) in seen:
            raise ValueError("duplicate directed edge")
        seen.add((u, v))
        adjacency[u].append(v)
        indegree[v] += 1
    queue = deque(v for v in range(n) if indegree[v] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adjacency[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
    if len(order) != n:
        raise ValueError("directed cycle")
    return order

edges = [(0, 2), (1, 2), (2, 3), (1, 4), (4, 5), (3, 5)]
assert topological_order(6, edges) == [0, 1, 2, 4, 3, 5]
assert topological_order(0, []) == []
assert topological_order(3, []) == [0, 1, 2]
assert topological_order(3, [(0, 1)]) == [0, 2, 1]
for cyclic in [[(0, 1), (1, 0)], [(0, 0)]]:
    try:
        topological_order(2, cyclic)
    except ValueError:
        pass
    else:
        raise AssertionError("cycle accepted")
print(topological_order(6, edges))

建立邻接表和入度需 $O(n+m)$ 时间；每个顶点入队、出队至多一次，每条边使入度减一次，所以总时间仍为 $O(n+m)$。邻接表、去重集合、计数、队列和结果共占 $O(n+m)$ 空间。孤立顶点入度为零，也会被输出；只从存在出边的顶点开始遍历会遗漏它们。

不唯一与失败的变式

变式。 主例若把初始队列改成 $[b,a]$，便可能得到另一个合法顺序。若要求字典序最小，可改用每次取最小可用顶点的优先队列，但代价一般变为 $O((n+m)\log n)$ 的粗上界，且这是额外的排序目标，不是拓扑顺序定义的一部分。

一个DAG的拓扑顺序唯一，当且仅当删除过程中每一步只有一个可选入度零顶点。如果每步只有一个，该位置显然被强制决定。若某步有两个不同候选 $u,v$，它们之间不能有边，否则终点入度就不为零；分别先取 $u$ 或先取 $v$ 后，剩余DAG都能继续排序，所以可得到不同顺序。

给主例增加边 $f\to b$ 后，环 $b\to e\to f\to b$ 会使部分顶点永远留在剩余图。程序可能先输出 $a$ 的内部前缀，但最终必须报告环；这个前缀不是覆盖全部顶点的拓扑排序。返回不完整列表而不检查长度，会把循环依赖误报为成功。

拓扑顺序适合规定计算依赖，却不等于最短完成时间的排程：若任务时长、可用人员或并行资源有限，还需另建调度模型。顺序只保证每条前置约束被尊重。