拓扑排序

拓扑排序是图论中的一个概念，主要应用于有向图。它的目的是对图中的顶点进行线性排序，使得对于任何从顶点 \(u\) 到顶点 \(v\) 的有向边，\(u\) 在排序中都出现在 \(v\) 之前。这种排序特别适用于解决表示“先决条件”关系的问题，如任务调度、课程规划等场景。

一个常用的算法是 Kahn 算法，其步骤如下：

1. 计算图中所有顶点的入度。
2. 将所有入度为 0 的顶点放入一个队列中。
3. 当队列非空时，执行以下操作：
   • 从队列中移除一个顶点 \(u\)，并将其加入到排序结果中。
   • 遍历从 \(u\) 出发的所有边 \(u \rightarrow v\)，将每个相邻顶点 \(v\) 的入度减 1。
   • 如果某个相邻顶点 \(v\) 的入度变为 0，则将 \(v\) 加入队列。
4. 重复步骤 3，直到队列为空。
5. 如果排序结果中的顶点数量与图中的顶点总数相同，则图不存在环，否则图中存在环，无法进行拓扑排序。我们可以使用拓扑排序判断图是否有环。