拓扑排序 / 入度消除

遍历与连通性 · HTML

数学 / 逻辑形态

维护剩余入度 indeg[v]；输出任一 indeg=0 节点并删除其出边。若最终输出少于 V，剩余子图含环。

识别信号

• 出现 prerequisite、dependency、build order。
• 要求满足所有先后约束的排列。
• 要判断能否完成全部任务或是否有有向环。
• 完成前置节点会让后继少一个未满足条件。

容易误判的相似信号

核心不变量

frontier 中节点在当前剩余图中入度为零；输出 u 后只有 u 的直接后继入度减少。

状态、转移与处理顺序

Python 骨架

from collections import deque

def topo_order(nodes, edges):
    graph = {u: [] for u in nodes}
    indeg = {u: 0 for u in nodes}
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1
    q = deque(u for u in nodes if indeg[u] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == len(nodes) else None

正确性思路

1. 输出时剩余入度为零，因此所有未满足前置项均不存在，顺序始终合法。
2. 任意非空 DAG 都有零入度节点，所以算法不会在无环剩余图上卡住。
3. 若卡住且仍有节点，沿剩余前驱不断追踪必重复节点，形成有向环。

复杂度

边界条件

• 无边时任意顺序合法。
• 自环节点永不归零。
• 重复边必须在入度和邻接中一致保留或一致去重。
• 没有出现在边中的孤立任务也要纳入。

错误模式

选择与排除规则

• 要显式顺序或并行层级：优先 Kahn 法。
• 只判环且递归颜色自然：可用 DFS 三色。
• 要唯一顺序：每步检查 frontier 是否只有一个节点。

相关模板

原创微型例子

Recall prompts

• 为何非空 DAG 必有零入度点？
• processed<V 为什么证明有环？
• 怎样判断拓扑序唯一？

我的补充