拓扑排序简单带图例题

拓扑排序是一种思想简单、应用广泛的拓扑学方法，被广泛应用于计算机科学、工程学、管理学等领域。它是图论中一种重要的算法，主要用于解决有向无环图中算法的执行顺序问题。

拓扑排序有两种方法：Kahn 算法和 DFS 算法。其中，Kahn 算法是比较常用的方法，DFS 算法通常用于竞赛中。

Kahn 算法的思想是：

1. 找到所有入度为 0 的点加入队列；

2. 对于队列中的每个点，遍历它的出边，将相应点的入度减 1；

3. 如果相应点的入度为 0，将该点加入队列。

通过以上步骤不断循环，直到队列为空，即可得到拓扑排序的结果。

下面是一个简单的例子：

在下图所示的有向无环图中，求其中节点的拓扑排序：


我们可以按照 Kahn 算法的步骤进行计算。首先，在图中找到所有入度为 0 的点 1，3 和 4，将它们加入队列 [1, 3, 4]：


接下来，遍历队列中的点，将相应点的入度减 1，并将入度变为 0 的点加入队列。注意，在遍历点 3 时，虽然点 1 的入度已经为 0，但不能加入队列，因为它已经被加入过了：


重复这个过程，直到队列为空。最终得到的拓扑排序结果为 [6, 5, 2, 1, 3, 4]：


通过这个例子，我们可以看到，拓扑排序可以很方便地解决一些问题。比如，在任务调度中，我们需要根据任务之间的依赖关系确定它们的执行顺序，就可以使用拓扑排序来解决。

除了 Kahn 算法，还有一个常用的算法是 DFS 算法。它的思路是将所有点视为未被访问，从任意一个点开始遍历，将已经遍历过的点标记为已访问，在遍历完该点的所有出边后，将该点加入结果集。最终得到的结果集就是拓扑排序的结果。

综上所述，拓扑排序是一种非常实用的算法，可以帮助我们解决一些问题。在实际应用中，需要根据不同的需求选择合适的算法来进行计算，以获得最优的效果。