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 |
| 完成 0 | 2 的入度降到 1 | 仍等待 1 |
| 完成 1 | 2 的入度降到 0,入队 | 前置全部满足 |
| 完成 2、3 | 得到 [0,1,2,3] | 所有依赖在前 |
窄屏可左右滑动表格,阅读完整计算与理由。
依赖边 u→v 必须满足 u 在输出中早于 v。
04为什么这个方法成立
- 只有剩余入度零节点才能被取出,所以它的所有前驱都已输出。
- 删除它的出边正确更新后继的剩余依赖数。
- 输出全部节点则每条边方向都符合顺序;否则剩余子图含环。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
加边 3→1 会怎样?
需要一点提示
1→2→3→1。
查看解析与答案
形成环,返回 None。
0 与 1 谁先必须固定吗?
需要一点提示
两者没有依赖。
查看解析与答案
不必须,两个顺序都合法。
每项有耗时,如何求最早完成时间?
需要一点提示
按拓扑顺序合并前驱结果。
查看解析与答案
finish[v]=duration[v]+max(finish[u]),u 为前驱,无前驱时从零开始。