形式陈述

有向图 $G=(V,E)$$G=(V,E)$ 的拓扑序是顶点的线性排列 $v_1,\ldots,v_n$$v_1,\dots ,v_n$，使每条边 $(v_i,v_j)\in E$$(v_i,v_j)\in E$ 都满足 $i<j$$i<j$。有限有向图存在拓扑序当且仅当它无有向环，即为 DAG。Kahn 算法反复取入度为零的顶点并删除其出边；若最终取完所有顶点，所得顺序合法，否则剩余子图含环。DFS 按完成时间逆序也可构造。两者均为 $O(|V|+|E|)$$O(|V|+|E|)$。

直觉

把所有“必须先于”的局部约束扩展成一条总执行顺序；无环保证总能找到当前没有未完成前驱的任务。

例子与边界

课程先修关系、构建依赖和任务 DAG 都可拓扑排序。没有边的图有 $n!$$n!$ 个拓扑序，说明结果一般不唯一。若存在 $a\to b\to c\to a$$a\to b\to c\to a$，任何线性顺序都会违反至少一条边。拓扑排序不是按顶点标签数值排序，也不适用于含环依赖，除非先收缩强连通分量或改变问题语义。

推论与应用

拓扑序用于依赖调度、动态规划、编译构建和偏序线性扩张。Kahn 算法还可同时检测环，并可用优先队列选择字典序最小的合法顺序。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Ch. 20, depth-first search and topological sorting。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 3, DAGs and topological order。