拓扑排序的基本算法

拓扑排序是一种重要的图论算法，常被用于对有向无环图进行排序和检测环的存在性。它可以帮助我们理解和解决实际问题中的任务调度和依赖关系等问题。

基本算法

拓扑排序的基本思想是从一个 DAG（有向无环图）中选择一个没有前驱的顶点，并输出该顶点。接着，从 DAG 中删除该顶点和所有以它为起点的边。这样不断重复上述过程，并输出到达的每个顶点，知道所有顶点输出完毕。

举个例子，假设我们有以下这样一个 DAG：


我们可以按照以下步骤进行拓扑排序：

1. 如果 DAG 中有多个入度为 0 的顶点，任选其中一个输出。

2. 从 DAG 中删除该顶点和所有以它为起点的边。

3. 重复 1~2 步骤，直到 DAG 中所有顶点均已输出。

按照上述思路，我们可以得到如下的拓扑排序结果：

C -> A -> B -> E -> D

这个结果表示，对于这个 DAG，我们可以先执行任务 C，然后执行任务 A，再执行任务 B，再执行任务 E，最后执行任务 D。

正确性证明

拓扑排序的正确性来源于有向无环图这个假设。由于 DAG 中不存在环，每次选择入度为 0 的顶点进行删除后，新的 DAG 一定不再有原 DAG 中的环。因此，最终 DAG 一定是一个空图，且排序结果一定是合法的。

时间复杂度

对于一个包含 n 个顶点和 e 条边的 DAG，拓扑排序的时间复杂度为 O(n+e)。这个时间复杂度可以通过遍历整张图来得到，因此需要使用 DFS 或 BFS 算法。

应用场景

拓扑排序在实际应用中有广泛的应用，例如：

1. 任务调度：将 DAG 中的顶点视为任务，边表示任务之间的依赖关系，拓扑排序可以帮助我们确定任务的执行顺序。

2. 编译顺序：编程语言中的类和函数也可以被视为 DAG 中的顶点，依赖关系则表示函数之间的调用关系。拓扑排序可以帮助我们确定函数的编译顺序。

3. 路由协议：在路由器中，通过学习邻居路由器的路由表，可以得到一个网络的拓扑结构。通过拓扑排序，可以对路由器之间进行路由协议的计算。