Java 中的 Kahn 拓扑排序算法

Kahn 算法是一种用于对有向无环图（DAG）进行拓扑排序的流行方法。拓扑排序是对 DAG 中的顶点进行排序，使得对于每条有向边（u，v），顶点 u 在排序中出现在顶点 v 之前。换句话说，排序后的图中没有环。

一个图可能存在多个拓扑排序。例如，下面的图可以有两种有效的拓扑排序：“5 4 2 3 1 0”和“4 5 2 0 3 1”。在任何有效的拓扑排序中，第一个顶点始终是入度为 0 的顶点，表示它没有来自图中其他顶点的传入边。

示例

输入

输出

5 4 2 3 1 0

解释：有向无环图（DAG）的拓扑排序是其顶点的线性排序。对于每条有向边 uv，顶点 u 在排序中出现在 v 之前。这意味着对于任何顶点 v，其所有依赖项（指向 v 的边所连接的顶点）必须在排序中出现在 v 之前。

在给定的示例中，顶点 5 和 4 没有传入边，因此它们可以在拓扑排序中以任意顺序排列。顶点 2 和 0 分别有来自 4 和 5 的传入边，因此它们在拓扑排序中必须出现在 4 和 5 之后。最后，顶点 1 没有依赖项，因此它必须排在最后。

示例

输入

输出

0 3 4 1 2

解释：在有向无环图（DAG）中，0 和 3 没有传入边，4 和 1 有来自 0 和 3 的传入边，而 2 放在最后。

直观理解

拓扑排序的直观理解是，我们可以从没有依赖项的顶点开始，然后添加依赖于它们的顶点。这可以确保我们永远不会在依赖项之前添加顶点，否则会导致图中出现环。

• 出度为 0 的节点将始终是我们首选执行的任务。
• 然后，在完成了所有出度为 0 的任务后，我们将转向处理依赖于已完成任务的任务（这些任务的出度现在将为 0），以此类推处理所有其他任务。

拓扑排序算法类似于广度优先搜索（BFS），但仅当顶点入度为 0 时才将其添加到队列中。这确保了顶点按照依赖关系顺序添加到拓扑排序中。

算法

1. 初始化一个入度列表，其中 indegrees[i] 表示指向顶点 i 的边的数量。
2. 对于图中的每个顶点 i
   • 增加所有与 i 相邻的顶点的入度。
3. 创建一个队列，并将所有入度为 0 的顶点添加到队列中。
4. 当队列不为空时
   • 从队列中移除第一个顶点，并将其添加到拓扑排序列表中。
   • 对于与移除的顶点 i 相邻的每个顶点 j
     • 减少 j 的入度。
     • 如果 j 的入度变为 0，则将 j 添加到队列中。
5. 如果拓扑排序列表的大小不等于图中顶点的数量，则图包含一个环，拓扑排序算法返回一个空列表。

如何找到每个节点的入度？

顶点的入度是指指向该顶点的边的数量。在您提供的代码中，每个顶点的入度是在以下 for 循环中计算的。

for 循环遍历图中的所有邻接列表。对于每个邻接列表，它会遍历邻接列表中所有边的目标节点。对于每个目标节点，它会增加目标顶点的入度。它确保在遍历完所有邻接列表后，每个顶点的入度都是正确的。

实施

文件名：TopologicalSort.java

输出

Topological Sorting:
4 5 2 0 3 1

时间复杂度：代码的时间复杂度为 O(V + E)，其中 V 是顶点的数量，E 是图中的边的数量。

辅助空间：辅助空间复杂度为 O(V)，这来自于算法中使用的额外数据结构。

Kahn 算法拓扑排序的应用

1. 课程排序：在教育机构中，学生通常需要遵循特定的课程顺序，其中某些课程是其他课程的先修课程。Kahn 算法可以确定应如何安排课程，以确保在注册特定课程之前已完成所有先修课程。
2. 软件依赖管理：在软件开发中，应用程序通常依赖于外部库或模块。Kahn 算法可以通过确定正确的链接顺序或加载库来管理这些软件依赖项，确保在执行依赖代码之前满足每个依赖项。
3. 任务调度：Kahn 算法可应用于项目管理、作业调度或制造过程等各种领域的任务调度。该算法有助于确定应以何种最优顺序执行任务，以满足依赖关系并提高效率。
4. 数据处理：在数据处理管道中，各种数据处理步骤相互依赖，Kahn 算法可以建立应按何种顺序执行这些步骤，以避免错误并确保数据一致性。
5. 电路设计：在数字电路设计中，某些逻辑门或组件可能依赖于其他门的输出。Kahn 算法可以帮助设计人员确定正确的门连接顺序，确保信号在电路中正确传播。