拓扑排序

拓扑排序是一种针对有向无环图的线性排序算法。这种排序序列需要满足一个条件：对于图中的每一条有向边 (u -> v)，在排序序列中，顶点 u 都必须出现在顶点 v 之前。拓扑排序常被用来解决具有依赖关系的问题，例如任务调度、课程安排等。

我们来循序渐进地理解它：

1. 核心思想与前提条件

   • 依赖关系：拓扑排序的核心是处理依赖关系。例如，在学习《数据结构》之前必须先学习《程序设计基础》，那么“《程序设计基础》”就是“《数据结构》”的前置条件。
   • 有向无环图（DAG）：拓扑排序只能应用于有向无环图。如果图中存在环，那么依赖关系就会形成循环（A依赖B，B依赖C，C又依赖A），这将导致无法找到一个满足所有条件的线性序列，因此拓扑排序也就无解。

2. 算法步骤（基于BFS的Kahn算法）
   这是一种直观且常用的方法，其核心是不断选择“入度”为零的顶点。

   • 步骤一：理解入度

     • 入度：指向某个顶点的边的数量。例如，如果有一条边 A -> B，那么对于顶点 B 来说，它的入度就增加了1。一个没有任何边指向它的顶点，其入度为0。

   • 步骤二：初始化

     • 计算图中每个顶点的入度，并存储在一个数组中（例如，inDegree[]）。
     • 初始化一个队列（Queue），用于存放所有当前入度为0的顶点。

   • 步骤三：循环处理

     • 当队列不为空时，执行以下循环：
       1. 出队：从队列中取出一个顶点（我们称它为 currentVertex）。
       2. 加入结果：将这个 currentVertex 加入到最终的拓扑排序结果序列中。
       3. 处理邻接点：遍历 currentVertex 所指向的所有邻接顶点（我们称其中一个为 neighbor）。
          • 将 neighbor 的入度减1（因为指向它的前驱节点 currentVertex 已经被移除了）。
          • 检查减1之后，neighbor 的入度是否变成了0。
          • 如果入度变为0，则将 neighbor 入队。

   • 步骤四：检查环路

     • 循环结束后，检查拓扑排序结果序列的长度。
     • 如果结果序列包含了图中所有的顶点，那么拓扑排序成功，这个序列就是其中一个有效的解。
     • 如果结果序列的长度小于图中顶点的总数，说明图中存在环，因此无法进行拓扑排序。

3. 举例说明
   假设我们有4门课程及其依赖关系：

   • 课程编号：0, 1, 2, 3
   • 依赖关系：学习1之前必须先学0，学习2之前必须先学1，学习3之前必须先学1。
   • 用图表示就是：0 -> 1， 1 -> 2， 1 -> 3。

   现在我们用Kahn算法来排序：

   • 初始化：
     • 计算入度：顶点0的入度为0，顶点1的入度为1，顶点2的入度为1，顶点3的入度为1。
     • 队列初始化：将入度为0的顶点0入队。队列 = [0]。
   • 第一轮循环：
     • 出队：取出顶点0。
     • 结果序列：[0]。
     • 处理0的邻接点（只有顶点1）：将顶点1的入度从1减为0。
     • 因为顶点1的入度变为0，将其入队。队列 = [1]。
   • 第二轮循环：
     • 出队：取出顶点1。
     • 结果序列：[0, 1]。
     • 处理1的邻接点（顶点2和3）：
       • 顶点2的入度从1减为0，入队。
       • 顶点3的入度从1减为0，入队。
     • 队列 = [2, 3]。
   • 第三轮循环：
     • 出队：取出顶点2。
     • 结果序列：[0, 1, 2]。
     • 顶点2没有邻接点，无操作。队列 = [3]。
   • 第四轮循环：
     • 出队：取出顶点3。
     • 结果序列：[0, 1, 2, 3]。
     • 顶点3没有邻接点，无操作。队列为空。
   • 结束检查：
     • 结果序列包含了全部4个顶点，排序成功。
     • 得到的拓扑序列是 [0, 1, 2, 3]。值得注意的是，[0, 1, 3, 2] 也是一个有效的拓扑序列，因为2和3之间没有依赖关系，它们可以互换位置。所以拓扑排序的结果可能不唯一。

通过这个一步步的过程，我们可以看到算法如何巧妙地通过管理顶点的入度，来逐步确定任务的执行顺序，确保所有的前置条件都被满足。