Topological Sort (拓扑排序)

Topological Sort（拓扑排序）是一种图算法，通常用于有向无环图（DAG）中。它的主要目的是将图中的所有节点按顺序排列，使得对于图中的每一条有向边（u → v），节点u都排在节点v之前。

什么是有向无环图（DAG）？

• 有向图：图中的边是有方向的，意味着从一个节点指向另一个节点。
• 无环图：图中没有任何环路，即不存在从某个节点出发，经过多个节点后又回到原节点的路径。

拓扑排序的直观理解：

假设你有一组任务（图中的节点），并且这些任务之间有依赖关系（图中的有向边）。拓扑排序就是将这些任务排成一个顺序，确保每个任务在它依赖的任务完成之后执行。

举个例子：

假设你有三个任务：

• 任务A → 任务B（意思是任务A必须先于任务B完成）
• 任务B → 任务C（意思是任务B必须先于任务C完成）

这些任务的依赖关系可以表示为一个有向图：

A → B → C

拓扑排序的结果就是：A → B → C，因为任务A必须先于任务B，任务B必须先于任务C。

拓扑排序的基本规则：

1. 每次选择一个没有依赖的节点（即没有前驱的节点），将它加入排序结果。
2. 从图中移除这个节点和所有与之相关的边。
3. 重复上面的过程，直到所有节点都被排入排序结果。

如何实现拓扑排序？

拓扑排序常用的两种方法是：

1. Kahn算法：基于入度（指向某个节点的边的数量）来实现。
2. 深度优先搜索（DFS）：通过递归来实现，先访问所有依赖的节点，再将当前节点加入排序。

Kahn算法的步骤：

1. 计算每个节点的入度（即有多少条边指向该节点）。
2. 将所有入度为0的节点加入队列（这些节点没有依赖，可以立即处理）。
3. 从队列中取出一个节点，将其加入结果排序中。
4. 对于该节点的所有邻接节点（指向该节点的节点），减少它们的入度。
5. 如果某个邻接节点的入度变为0，将其加入队列。
6. 重复这个过程，直到队列为空。

举个例子：

假设我们有如下的任务依赖关系：

A → B
A → C
B → D
C → D

1. 初始化入度：
   • A的入度为0。
   • B的入度为1（由A指向B）。
   • C的入度为1（由A指向C）。
   • D的入度为2（由B和C指向D）。
2. 将入度为0的节点加入队列：A。
3. 处理A：A没有依赖，加入排序结果，然后减少B和C的入度。
4. 新的入度：
   • B的入度变为0。
   • C的入度变为0。
5. 将入度为0的节点加入队列：B、C。
6. 处理B：B没有其他依赖，加入排序结果，然后减少D的入度。
7. 处理C：C没有其他依赖，加入排序结果，然后减少D的入度。
8. 处理D：D的入度为0，加入排序结果。

最终排序结果是：A → B → C → D。

DFS方法：

DFS方法通过递归来实现：

1. 从任意一个节点开始，递归访问它的所有邻接节点。
2. 每当一个节点的所有邻接节点都被访问过之后，才把它加入到排序结果中。
3. 反向添加节点（即递归结束时将节点加入栈，最后逆序输出）。

拓扑排序的应用场景：

1. 任务调度：比如你要按照某些依赖关系执行一系列任务，拓扑排序可以帮助你找出执行的顺序。
2. 编译顺序：在编译程序时，需要按照模块的依赖关系编译代码。
3. 课程安排：在学习课程时，某些课程可能依赖于前面的课程，拓扑排序可以帮助你规划学习顺序。

总结：

拓扑排序是一个重要的图算法，适用于有向无环图。它通过将节点按照依赖关系排列，确保每个节点的依赖节点在它之前完成。拓扑排序在很多实际问题中都有广泛应用，比如任务调度、编译顺序和课程安排等。

LeetCode 相关题目:

LeetCode 拓扑排序问题列表

已完成题目: