拓扑排序
拓扑排序（Topological sorting）要解决的问题是给一个有向无环图的所有节点排序。
比如学习大学课程中有：程序设计、算法语言、高等数学、离散数学、编译技术、普通物理、数据结构、数据库系统等。按照例子中的排课，当我们想要学习 数据结构 的时候，就必须先学会 离散数学 和 编译技术。当然还有一个更加前的课程 算法语言。
这些课程就相当于几个顶点 \(u\), 顶点之间的有向边 \((u,v)\) 就相当于学习课程的顺序。教务处安排这些课程，使得在逻辑关系符合的情况下排出课表，就是拓扑排序的过程。
在一个 DAG（有向无环图）中，我们将图中的顶点以线性方式进行排序，使得对于任何的顶点 \(u\) 到 \(v\) 的有向边 \((u,v)\), 都可以有 \(u\) 在 \(v\) 的前面。
还有给定一个 DAG，如果从 \(i\) 到 \(j\) 有边，则认为 \(j\) 依赖于 \(i\)。如果 \(i\) 到 \(j\) 有路径（i 可达 j），则称 \(j\) 间接依赖于 \(i\)。
拓扑排序的目标是将所有节点排序，使得排在前面的节点不能依赖于排在后面的节点。
构造拓扑序列步骤：
-
从图中选择一个入度为零的点；
-
输出该顶点，从图中删除此顶点及其所有的出边。
重复上面两步，直到所有顶点都输出，拓扑排序完成，或者图中不存在入度为零的点，此时说明图是有环图，拓扑排序无法完成，陷入死锁。
Kahn 算法
过程
初始状态下，集合 \(S\) 装着所有入度为 \(0\) 的点，\(L\) 是一个空列表。
每次从 \(S\) 中取出一个点 \(u\)（可以随便取）放入 \(L\), 然后将 \(u\) 的所有边 $(u, v_1), (u, v_2), (u, v_3) \cdots $删除。对于边 \((u, v)\)，若将该边删除后点 \(v\) 的入度变为 \(0\)，则将 \(v\) 放入 \(S\) 中。
不断重复以上过程，直到集合 \(S\) 为空。检查图中是否存在任何边，如果有，那么这个图一定有环路，否则返回 \(L\)，\(L\) 中顶点的顺序就是构造拓扑序列的结果。
伪代码如下：
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is not empty do
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
参考：