算法: 拓扑排序与后序遍历

简介

拓扑排序在我们生活中有很多的应用，最简单的就是任务的安排表，使用拓扑排序可以帮助你更容易分清哪个任务应该先做，哪个后做，以及它们之间的依赖关系。如下图有 5 个任务

凭我们肉眼很容易知道第 5 个任务先做，再后再做 3 ，以此类推下去，这就是拓扑排序。

定理

在图论里有这样一个定理，在有向图里只有两种情况出现：

1. 要么有环的结构
2. 要么存在拓扑排序

好像很废话是不是，定理其实都挺废话的，像什么两点间直线最短之类的，但是这些定理将是算法的基础，例如推理，证明的基础。

根据上面的这个定理我们可以知道，如果要求一个有向图的拓扑排序，返回结果就只有两种：有环抛出错误，或者返回拓扑排序结果。

DFS 求拓扑排序

我知道你们肯定都听说过先找入度为 0 的 BFS 方法，这里我就说一下用 DFS 来求拓扑排序的方法。

首先我们对这个算法的期望应该是如果有环就说有环抛出错误，如果可以拓扑排序那么就把排序打印出来，同时要说明每个节点的父节点是谁。

考虑如下图

对于这个图是可以拓扑排序的，顺序为 [s, a, x, b, z, c]，节点的的父节点是：

当前节点	父节点
a	a
b	a
c	b
z	b
x	a

这里再给出图的后序遍历的顺序 [c, z, b, x, a, s]。哎，这反转一下不就是拓扑排序的结果了么？没错，DFS 方法就是使用这个来得到拓扑排序的。下面给出思路。

1. 首先因为我们处理的不是树，所以对每个节点都要做 DFS 搜索
2. 在搜索每个节点时，先当前节点推到 Stack 中
   1. 如果发现要搜索的下一个节点在 Stack 里，那么说明有一条向上的路，这就有环了，抛出错误
   2. 否则就继续搜索下一个节点，同时设置当前节点为下一个节点的父节点
3. 完成当前节点的搜索后就从 Stack 中弹出，将当前节点加入到 PostOrder 结果里
4. 最后将 PostOrder 结果反转一下就是拓扑排序结果了

伪代码如下

const parents = {}
const postOrder = []
const stack = new Stack()

function dfs(vertex) {
    // 将当前节点推到 stack 中
    stack.push(vertex)
    // 找下一个节点
    for (let child in vertex.children) {
        if (stack.includes(child)) {
            // 有环，抛出错误
            throw new Error('有环')
        }
        if (!parents.includes(child)) {
            parents[child] = vertex
            dfs(child)
        }
    }

    postOrder.push(vertex)
    stack.remove(vertex)
}

function topOrder(graph) {
    // 每个节点都 DFS 一次
    for (let vertex in graph.vertices) {
        parents[vertex] = vertex
        dfs(vertex)
    }
}