专题进阶 · 图算法推荐总顺序 · 第 56 / 148 课

用入度表达未完成依赖,证明取出入度零节点的安全性并检测环。

先学会这些,再进入本课 图的表示 队列
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

拓扑排序Topological Sort

在有向无环图中按依赖顺序排列节点;入度归零是 Kahn 算法的选择条件。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用入度表达未完成依赖,证明取出入度零节点的安全性并检测环。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

课程依赖为 0→2、1→2、2→3,箭头表示前者必须先完成。怎样得到合法学习顺序?

02一步步得到方法

把能立即开始的任务找出来

入度表示一个节点还有多少前置依赖。初始将入度为 0 的节点放入队列。取出 u 后,视为完成 u,对其每个后继 v 的入度减 1;变成 0 时,v 的全部依赖都已处理,可以入队。

若同时有多个可选节点,结果可能不唯一。普通队列返回某个合法顺序;若必须字典序最小,使用小根优先队列,每次选最小编号。

停止后为什么能判断有环

DAG 的非空剩余子图必有入度零节点,否则不断沿前驱回溯会在有限节点中重复,形成环。因此若输出数小于 V 且队列已空,剩余依赖里存在环。

拓扑顺序只适用于有向图,且只表示依赖关系,不代表最短路径或任务执行总时长。并行任务调度还要计算每项的最早开始和完成时间。

入度表示还有多少前置未完成

把所有入度0节点放进队列,代表它们已经没有未完成的前置。弹出节点后删除它的出边,相当于完成一个依赖,使后继入度减少。

如果只处理了部分节点就无入度0可选,剩下的依赖中存在环。拓扑序可能不唯一;若希望固定字典序,可用优先队列选择当前可用的最小节点,而不是误以为任何队列结果都唯一。

03把一个小例子完全算清楚

0→2、1→2、2→3。

步骤计算与状态为什么这样做
初始入度[0,0,2,1],队列 [0,1]可先学 0 或 1
完成 02 的入度降到 1仍等待 1
完成 12 的入度降到 0,入队前置全部满足
完成 2、3得到 [0,1,2,3]所有依赖在前

窄屏可左右滑动表格,阅读完整计算与理由。

依赖边 u→v 必须满足 u 在输出中早于 v。

04为什么这个方法成立

  1. 只有剩余入度零节点才能被取出,所以它的所有前驱都已输出。
  2. 删除它的出边正确更新后继的剩余依赖数。
  3. 输出全部节点则每条边方向都符合顺序;否则剩余子图含环。

05把推导翻译成代码

Python · 可独立运行的教学实现

from collections import deque
def topological_sort(n, edges):
    adj, indegree = [[] for _ in range(n)], [0]*n
    for u,v in edges:
        adj[u].append(v); indegree[v] += 1
    q = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                q.append(v)
    return order if len(order) == n else None

逐个理解关键决定

indegree[v] += 1
箭头指向被依赖约束的后继,不能把 u 的入度增加。
len(order) == n
空队列不总表示成功,要检查是否处理所有节点。

06时间、空间与实现范围

时间 O(V+E),空间 O(V+E),含邻接表。若用堆选最小编号,额外 O(V log V)。

仅能检测有环,不直接输出一个具体环;定位环可再对剩余子图 DFS。

07改变条件,检查哪里会出错

把输出长度不足当作节点不存在

这通常是依赖成环;不能把部分结果当作完整合法计划。

重复边只在入度或邻接表一边保留

入度增加与删除边的次数必须一致,否则可能提前入队或永远无法入队。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

加边 3→1 会怎样?

需要一点提示

1→2→3→1。

查看解析与答案

形成环,返回 None。

练习 2 · 边界与辨析

0 与 1 谁先必须固定吗?

需要一点提示

两者没有依赖。

查看解析与答案

不必须,两个顺序都合法。

练习 3 · 变式与迁移

每项有耗时,如何求最早完成时间?

需要一点提示

按拓扑顺序合并前驱结果。

查看解析与答案

finish[v]=duration[v]+max(finish[u]),u 为前驱,无前驱时从零开始。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。