Computing · Algorithms
Topological Sort
拓扑排序
~ 14 min · v11
拓扑排序
cs-algo/topological-sort · COMP2521
0 / 3
1 先看：箭头表示"必须先学"，给我一个合法顺序
每个圈是一个知识点，箭头 A → B 表示"学 B 之前必须先学 A"。圈里的小数字是还没满足的前置数（入度）。怎么排出一条能顺着学下来的顺序？点「下一步」：每次挑一个入度为 0（前置都学完了）的点拿走，看它的箭头消失、下游入度跟着减。
Kahn 算法单步演示
已排出的顺序
（还没开始）
点「下一步」：算法会先找入度为 0 的点。
拓扑排序：把有向无环图（DAG）的所有点排成一条直线，使每条边都从前指向后（依赖永远排在被依赖的前面）。上面那条"先学谁后学谁"的顺序就是一个拓扑序。
演示用的是 Kahn 算法：反复取"入度为 0（没有未满足前置）"的点加入结果，再删掉它的出边、让下游入度减一，直到取完。
2 凭什么对：入度为 0 = 前置都齐了
Kahn 的每一步都很朴素，但合在一起就保证了"边永远从前指向后"。
入度为 0 才能取
一个点入度为 0，意味着指向它的依赖都已被取走。这时把它排进结果，绝不会排在它的某个前置之前——边方向得到保证。
取走后减下游
取走 u 等于"u 学完了"，于是 u 指向的每个点入度减一。某个点减到 0，就轮到它能取了。用一个队列装"当前入度为 0"的点即可。
复杂度 O(V+E)
每个点进出队列一次、每条边被处理一次。先 O(E) 数好所有入度，再线性推进——线性时间。
顺序通常不唯一：某一步若有多个点入度同时为 0，先取哪个都行，会得到不同但都合法的拓扑序。另一种做法是 DFS 后序逆序，同样得到拓扑序。
3 有环 = 无解（Kahn 顺手就能检测）
点上面的「加一条成环的边」按钮再跑一遍：你会看到算法中途卡住——还有点没取完，但再也找不到入度为 0 的点了。
为什么：环里的每个点都被环上的下一个点"依赖"着，谁的入度都降不到 0（"要先学 A 才能学 B，又要先学 B 才能学 A"——死锁）。
所以 Kahn 顺手就是一个环检测器：如果最终取出的点数 < 总点数，说明图里有环，不存在拓扑序。
所以 Kahn 顺手就是一个环检测器：如果最终取出的点数 < 总点数，说明图里有环，不存在拓扑序。
现实意义：课程先修成环 = 排不出课表；构建系统里模块循环依赖 = 编译不了。拓扑排序正是这些"按依赖定顺序"问题的通用解，前提是依赖关系无环。
4 自测
三道题，点选项即时判对错。
去做例题：用 Kahn 算法求拓扑序 + 判断有无环
去做例题
一句话带走：
拓扑排序 = 把 DAG 排成一条线，让每条边都从前指向后（依赖在前）。Kahn 算法：反复取入度为 0 的点、删其出边、减下游入度，用队列推进，O(V+E)。顺序通常不唯一。只要取出点数 < 总点数，就说明有环、无拓扑序——这也是它顺带的环检测能力。凡是"按依赖关系定先后"的问题（排课、任务调度、构建顺序），都靠它。