Topological Sorting

拓扑排序是一种对有向无环图（DAG）进行排序的算法，其目的是将图中的所有顶点线性排列，使得对于每一条有向边 $u\to v$，顶点 $u$ 在顶点 $v$ 之前。换句话说，拓扑排序确保了所有的依赖关系都被满足。

拓扑排序的应用场景包括：

1. 任务调度：在有依赖关系的任务中，确保先完成依赖的任务再进行后续任务。
2. 编译顺序：在编译程序时，确保先编译依赖的模块。
3. 课程安排：在学习课程时，确保先学习先修课程。

拓扑排序的常用算法有两种：

1. Kahn 算法：通过计算每个顶点的入度，逐步将入度为 0 的顶点加入排序结果，并更新其邻接顶点的入度。

   L ← 包含已排序的元素的列表，目前为空
   S ← 入度为零的节点的集合
   当 S 非空时：
       将节点n从S移走
       将n加到L尾部
       选出任意起点为n的边e = (n,m)，移除e。如m没有其它入边，则将m加入S。
       重复上一步。
   如图中有剩余的边则：
       return error   (图中至少有一个环)
   否则：
       return L   (L为图的拓扑排序)
   

2. 深度优先搜索（DFS）：通过对图进行DFS遍历，记录每个顶点的完成时间，最后反转完成时间的顺序得到拓扑排序。

   L ← 一个空的 用来存放已排序的节点的列表
   当图中存在未永久标记的节点时：
       选出任何未永久标记的节点n
       visit(n)
   
   function visit(节点 n)
       如n被永久标记：
           return
       如n被临时标记：
           stop   (不是定向无环图，至少有一个环)
   
       将n临时标记
   
       对于每一个以n为起点的边(n,m)：
           visit(m)
   
       去掉n的临时标记
       将n永久标记
       在L的起始位置插入n（如L已有内容 后移它们以空出起始位置）