6.4.4 拓扑排序

DAG的拓扑序使每条边u→v中u都在v之前。Kahn算法统计入度，把所有0入度顶点入队；不断取出并删除其出边，新产生0入度者入队。输出不足V个说明存在环。

手工状态

边A→C,B→C,C→D：初始0入度A、B，可能输出A,B,C,D或B,A,C,D；C必须在A、B之后，D在C之后。

结构与代码

队列选择不同会产生不同合法序；若要字典序最小，用小根堆。复杂度 O(V+E)。DFS按完成时间逆序也能得到拓扑序，并用灰色回边检测环。

正确性依据

每次输出0入度点不会违反前置依赖；删除后递归缩小DAG。若剩余图无0入度点，则沿前驱必进入环。

错解反馈

把拓扑序当唯一；初始只入一个0入度点；修改入度却不防重复入队。

迁移训练

课程A、B均为C前置，C为D前置，列出全部拓扑序。答案A B C D与B A C D。