拓扑排序为什么不用队列

拓扑排序是一种非常重要的图论算法，可以对有向无环图进行排序，它被广泛应用于编译、任务调度、依赖关系分析等领域。但是，我们会发现在常见的拓扑排序算法中，队列并不是必需的数据结构，那么为什么拓扑排序不用队列呢？下面从多个角度进行分析。

一、拓扑排序算法原理

拓扑排序算法的原理很简单：首先找到图中所有没有前驱节点的点，将它们加入到拓扑序列中，并去掉它们的出边，之后重复上述步骤，直到所有节点都加入到拓扑序列中。整个过程与剥洋葱相似，每剥一层都会去掉一些节点和它们的出边。最终，生成的拓扑序列就是一种合法的拓扑排序结果。

二、算法实现

我们可以采用两种方式来实现拓扑排序算法，一种是类似于BFS（广度优先搜索）的方式，即从没有前驱节点的节点开始，遍历所有节点，将它们添加到拓扑序列中。这种方式需要使用队列来存储当前所有没有前驱节点的节点。

另一种方式是基于DFS（深度优先搜索）的算法，我们提前定义一个栈用来存储当前搜索路径上的所有节点，每次访问到一个节点时，我们会将这个节点的后继节点递归的加入到栈中，直到没有后继节点可加入为止。然后从栈中弹出最后一个节点，加入到拓扑序列中。这种实现方式不需要使用队列。

三、基于队列和栈的拓扑排序算法比较

虽然基于队列和基于栈的拓扑排序算法都可以正确的排序有向无环图，但是它们有着不同的适用场景和性能表现。

1.空间复杂度

基于队列的拓扑排序算法需要使用一个队列来存储当前所有没有前驱节点的节点，因此它的空间复杂度为 O(n)，其中n为节点数量。

基于栈的拓扑排序算法需要使用一个栈来存储当前搜索路径上的所有节点，其中可能包含了已经加入到拓扑序列中的节点，因此它的空间复杂度为O(h)，其中h为DFS搜索树的高度。

可以看到，当图中的节点数量比较少，而搜索树深度比较大的时候，基于栈的拓扑排序算法会更加节省空间。

2.时间复杂度

基于队列的拓扑排序算法需要不断的将没有前驱节点的节点插入到队列中，这是一个O(1)的操作，但是每次插入可能会导致其他节点的前驱节点数量减少，需要重新判断是否也成为了没有前驱节点的节点，因此时间复杂度为O(n+m)，其中n为节点数量，m为边数量。

基于栈的拓扑排序算法在访问到一个节点的时候，会递归的访问它的所有后继节点，因此每个节点只会被访问一次，时间复杂度为O(n+m)，其中n为节点数量，m为边数量。

可以看到，基于栈的拓扑排序算法在时间复杂度上优于基于队列的实现方式。

四、为什么拓扑排序不用队列

经过上面的分析，我们可以看到，虽然基于队列的拓扑排序算法是一种可行的实现方式，但是基于栈的实现方式不仅更加节省空间，而且时间复杂度也更优秀。而且，在实际应用中，大多数情况下我们并不需要得到所有节点的拓扑序列，而只需要得到一条拓扑序列即可，因此栈更适合这样的需求。

综上所述，拓扑排序不用队列的原因是基于栈的实现方式更加高效和节省空间。