查看完整目录 –>《搞定算法与数据结构》

给定问题

来自：Letcode (210) – 课程表 2

假设给定一个数组，数组的每个元素都是一个长度为2的子数组，表示课堂的依赖关系，比如要学习课程3，比如得先学习课程1，而要学习课程 4，也得先学习课程2，要学习课程5，得先学习课程3和课程4。如下图所示

则数组为：[[3,1], [4,2], [5,3], [5,4]]

那么问题来了，如何找到一条学习路径，可以学习完所有的课程。

上例是为了方便我理解问题，所以课程数比较少，依赖关系也比较简单，所以从图中可以一眼看出来：1,2,3,4,5

而在实际问题中，课程数会非常多，依赖关系也会更加复杂，此时你就很难画图直观说出一条准确的学习路径了。

排序逻辑

虽然没法画图了，但可以从上图中总结出一些规律，来方便我们编码实现查找过程。

我们回想一下，为什么最开始我们会盯上 1 和 2 ，先学他们呢？

还不是他们的入度为 0，入度为0 的节点，我暂且将他们称之为可执行节点

入度：顶点的入度是指「指向该顶点的边」的数量；
出度：顶点的出度是指该顶点指向其他点的边的数量。

预处理

准备一个 map，遍历一遍数组，记录下每个入度的课程信息。

{
  0: [1, 2],
  1: [3, 4],
  2: [5]
}

我们只需要准备一个队列，把那些入度为0 的节点先放入队列中。

第一轮

把这些可执行节点（课程1 和课程2）放入队列中后，那依赖这些可执行节点的节点（课程3 和课程4）的入度要相应的减掉 1。

第二轮

检查上一轮入度有更新的节点（课程3 和课程4）的入度是否为 0 ，若为 0，则也将其放入队列中，放入完成后，依赖本轮的可执行节点的节点（课程5）入度减去1。

第三轮

检查上一轮入度有更新的节点（课程5）的入度是否为 0 ，由于5最初的入度为2，经过第二轮后，入度减掉了2，目前的入度为0，因此将其最后放入队列中。

最终结果

从队列中分别取出，即是可行的一条学习路径。

这种排序方法，就是大名鼎鼎的 拓扑排序 （Topological Order）。

拓扑排序的基础是给定的数组，能够描绘出 有向无环图 （Directed Acyclic Graph，简称DAG），不是 DAG 的都是无解的，都不能使用拓扑排序。

有向：有方向的

无环：不能出现死循环

时间复杂度

拓扑排序 的时间复杂度，是有两个参数的：

1. 节点数（m）：有多少门课程
2. 边（k）：依赖关系数，也即给定数组的长度

从头回顾一下，我们的查找过程

1. 预处理：需要遍历 k 次，时间复杂度为 O(k)
2. x轮处理：不管x是多少，反正都是将 m 个课程，依次放次队列中，因此时间复杂度为 O(m)
3. 整理结果：有了队列后，还是从队列中取出每个节点来，总共有 m 门课程，时间复杂度还为 O(m)

由于时间复杂度是可以直接想加的，因此总的时间复杂度为 O(k+2m)，时间复杂度中系数没有意义，因此最终的时间复杂度为：O(k+m)

空间复杂度

在上面的排序中，总共用到了两个数组结构：map 和 queue。

但不管是哪种，他们存放的数据量是固定的 m 个节点，所以空间复杂度是 O(2m)，系数同样可以直接去除，最终的空间复杂度是O(m)

参考文章：

• 图文详解面试常考算法 —— 拓扑排序