关于java:拓扑排序就这么回事

前言

大家好，这里是《齐姐聊算法》系列之拓扑排序问题。

Topological sort 又称 Topological order，这个名字有点迷惑性，因为拓扑排序并不是一个纯正的排序算法，它只是针对 某一类图，找到一个能够执行的线性程序。

这个算法听起来高大上，现在的面试也很爱考，比方过后我在面我司时有整整一轮是基于拓扑排序的设计。

但它其实是一个很好了解的算法，跟着我的思路，让你再也不会遗记她。

有向无环图

刚刚咱们提到，拓扑排序只是针对特定的一类图，那么是针对哪类图的呢？

答：Directed acyclic graph (DAG)，有向无环图。即：

1. 这个图的边必须是有方向的；
2. 图内无环。

那么什么是方向呢？

比方微信好友就是有向的，你加了他好友他可能把你删了你却不晓得。。。那这个敌人关系就是单向的。。

什么是环？环是和方向无关的，从一个点登程能回到本人，这是环。

所以下图右边不是环，左边是。

那么如果一个图里有环，比方右图，想执行 1 就要先执行 3，想执行 3 就要先执行 2，想执行 2 就要先执行 1，这成了个死循环，无奈找到正确的打开方式，所以找不到它的一个拓扑序。

总结：

• 如果这个图不是 DAG，那么它是没有拓扑序的；
• 如果是 DAG，那么它至多有一个拓扑序；
• 反之，如果它存在一个拓扑序，那么这个图必然是 DGA.

所以这是一个 充沛必要条件。

拓扑排序

那么这么一个图的 「拓扑序」 是什么意思呢？

咱们借用百度百科的这个课程表来阐明。

这里有 9 门课程，有些课程是有先修课程的要求的，就是你要先学了「最右侧这一栏要求的这个课」能力再去选「高阶」的课程。

那么这个例子中拓扑排序的意思就是：
就是求解一种可行的程序，可能让我把所有课都学了。

那怎么做呢？

首先咱们能够用 图来形容它，
图的两个因素是 顶点和边 ，
那么在这里：

• 顶点：每门课
• 边：终点的课程是起点的课程的先修课

画进去长这个样：

这种图叫 AOV (Activity On Vertex) 网络，在这种图里：

• 顶点：示意流动；
• 边：示意流动间的先后关系

** 所以一个 AOV 网应该是一个 DAG，即有向无环图，否则某些流动会无奈进行。
<span style=”display:block;color:orangered;”> 那么所有流动能够排成一个可行线性序列，这个序列就是 拓扑序列。**

那么这个序列的 实际意义 是：
依照这个程序，在每个我的项目开始时，可能保障它的前驱流动都已实现，从而使整个工程顺利进行。

回到咱们这个例子中：

1. 咱们一眼能够看进去要先学 C1, C2，因为这两门课没有任何要求嘛，大一的时候就学呗；
2. 大二就能够学第二行的 C3, C5, C8 了，因为这三门课的先修课程就是 C1, C2，咱们都学完了；
3. 大三能够学第三行的 C4, C9；
4. 最初一年选剩下的 C6, C7。

这样，咱们就把所有课程学完了，也就失去了这个图的 一个 拓扑排序。

留神，有时候拓扑序并不是惟一的，比方在这个例子中，先学 C1 再学 C2，和先 C2 后 C1 都行，都是这个图的正确的拓扑序，但这是两个程序了。

所以面试的时候要问下面试官，是要求解任意解，还是列出所有解。

咱们总结一下，

在这个图里的 边示意的是一种 依赖关系，如果要修下一门课，就要先把前一门课修了。

这和打游戏里一样一样的嘛，要拿到一个道具，就要先做 A 工作，再实现 B 工作，最终终于能达到目的地了。

算法详解

在下面的图里，大家很容易就看进去了它的拓扑序，但当工程越来越宏大时，依赖关系也会变得盘根错节，那就须要用一种系统性的形式办法来求解了。

那么咱们回忆一下刚刚本人找拓扑序的过程，为什么咱们先看上了 C1, C2?

因为它们没有依赖他人啊，
也就是它的 入度为 0.

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

所以咱们先执行入度为 0 的那些点，
那也就是要记录每个顶点的入度。
因为 只有当它的 入度 = 0 的时候，咱们能力执行它。

在方才的例子里，最开始 C1, C2 的入度就是 0，所以咱们能够先执行这两个。

那在这个算法里第一步就是失去每个顶点的入度。

Step0: 预处理失去每个点的入度

咱们能够用一个 HashMap 来寄存这个信息，或者用一个 数组 会更精美。

在文中为了不便展现，我就用表格了：

Step1

拿到了这个之后，就能够执行入度为 0 的这些点了，也就是 C1, C2.

那咱们把能够被执行的这些点，放入一个 待执行的容器 里，这样之后咱们一个个的从这个容器里取顶点就好了。

至于这个 容器 到底选哪种 数据结构 ，这取决于咱们须要做哪些 操作，再看哪种数据结构能够为之服务。

那么首先能够把 [C1, C2] 放入 容器 中，

而后想想咱们须要哪些操作吧！

咱们最常做的操作无非就是 把点放进来 ， 把点拿出去 执行了，也就是须要一个 offer 和 poll 操作比拟高效的数据结构，那么 queue 就够用了。

（其余的也行，放进来这个容器里的顶点的位置都是一样的，都是能够执行的，和进来的程序无关，但何必非得给本人找麻烦呢？一个惯例程序的简简单单的 queue 就够用了。）

而后就须要把某些点拿出去执行了。

【划重点】当咱们把 C1 拿进去执行，那这象征这什么？

<span style=”display:block;color:blue;”> 答：意味着「以 C1 为顶点」的「指向其余点」的「边」都隐没了，也就是 C1 的出度变成了 0.

如下图，也就是这两条边能够隐没了。

那么此时咱们就能够更新 C1 所指向的那些点 也就是 C3 和 C8 的 入度 了，更新后的数组如下：

<span style=”display:block;color:blue;”> 那咱们这里看到很要害的一步，C8 的入度变成了 0！

也就意味着 C8 此时没有了任何依赖，能够放到咱们的 queue 里期待执行了。

此时咱们的 queue 里就是：[C2, C8].

Step2

下一个咱们再执行 C2，

那么 C2 所指向的 C3, C5 的 入度 -1，

更新表格：

也就是 C3 和 C5 都没有了任何解放，能够放进 queue 里执行了。

queue 此时变成：[C8, C3, C5]

Step3

那么下一步咱们执行 C8，

相应的 C8 所指的 C9 的入度 -1.
更新表格：

那么 C9 没有了任何要求，能够放进 queue 里执行了。

queue 此时变成：[C3, C5, C9]

Step4

接下来执行 C3，

相应的 C3 所指的 C4 的入度 -1.
更新表格：

<span style=”display:block;color:blue;”> 然而 C4 的入度并没有变成 0，所以这一步没有任何点能够退出 queue.

queue 此时变成 [C5, C9]

Step5

再执行 C5，

那么 C5 所指的 C4 和 C6 的入度 - 1.
更新表格：

这里 C4 的依赖全都隐没啦，那么能够把 C4 放进 queue 里了：

queue = [C9, C4]

Step6

而后执行 C9，

那么 C9 所指的 C7 的入度 - 1.

这里 C7 的入度并不为 0，还不能退出 queue，

此时 queue = [C4]

Step7

接着执行 C4，

所以 C4 所指向的 C6 和 C7 的入度 -1，
更新表格：

C6 和 C7 的入度都变成 0 啦！！把它们放入 queue，继续执行到直到 queue 为空即可。

总结

好了，那咱们梳理一下这个算法：

<span style=”display:block;color:blue;”> 数据结构
这里咱们的入度表格能够用 map 来寄存，对于 map 还有不分明的同学能够看之前我写的 HashMap 的文章哦～

Map: <key = Vertex, value = 入度 >

但理论代码中，咱们用一个 int array 来存储也就够了，graph node 能够用数组的 index 来示意，value 就用数组里的数值来示意，这样比 Map 更精美。

而后用了一个一般的 queue，用来寄存能够被执行的那些 node.

<span style=”display:block;color:blue;”> 过程
咱们把入度为 0 的那些顶点放入 queue 中，而后通过每次执行 queue 中的顶点，就能够让依赖这个被执行的顶点的那些点的 入度 -1，如果有顶点的入度变成了 0，就能够放入 queue 了，直到 queue 为空。

<span style=”display:block;color:blue;”> 细节
这里有几点实现上的细节：

当咱们 check 是否有新的顶点的 入度 == 0 时，没必要过一遍整个 map 或者数组，只须要 check 刚刚改变过的就好了。

另一个是如果题目没有给这个图是 DAG 的条件的话，那么有可能是不存在可行解的，那怎么判断呢？很简略的一个办法就是比拟一下最初后果中的顶点的个数和图中所有顶点的个数是否相等，或者加个计数器，如果不相等，阐明就不存在无效解。所以这个算法也能够用来 判断一个图是不是有向无环图。

很多题目给的条件可能是给这个图的 edge list，也是示意图的一种罕用的形式。那么给的这个 list 就是示意图中的 边。这里要留神审题哦，看清楚是谁 depends on 谁。其实图的题个别都不会间接给你这个图，而是给一个场景，须要你把它变回一个图。

<span style=”display:block;color:blue;”> 工夫复杂度

留神 ⚠️：对于图的工夫复杂度剖析肯定是两个参数，面试的时候很多同学张口就是 O(n)…

对于有 v 个顶点和 e 条边的图来说，

第一步，预处理失去 map 或者 array，须要过一遍所有的边才行，所以是 O(e)；

第二步，把 入度 == 0 的点入队出队的操作是 O(v)，如果是一个 DAG，那所有的点都须要入队出队一次；

第三步，每次执行一个顶点的时候，要把它指向的那条边打消了，这个总共执行 e 次；

总：O(v + e)

<span style=”display:block;color:blue;”> 空间复杂度

用了一个数组来存所有点的 indegree，之后的 queue 也是最多把所有的点放进去，所以是 O(v).

<span style=”display:block;color:blue;”> 代码

对于这课程排序的问题，Leetcode 上有两道题，一道是 207，问你是否实现所有课程，也就是问拓扑排序是否存在；另一道是 210 题，是让你返回任意一个拓扑程序，如果不能实现，那就返回一个空 array。

这里咱们以 210 这道题来写，更残缺也更常考一些。

这里给的 input 就是咱们刚刚说到的 edge list.

Example 1.

Input: 2, [[1,0]]
Output: [0,1]
Explanation: 这里一共 2 门课，1 的先修课程是 0. 所以正确的选课程序是[0, 1].

Example 2.

Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation: 这里这个例子画进去如下图

Example 3.

Input: 2, [[1,0],[0,1]]
Output: null
Explanation: 这课没法上了

class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {int[] res = new int[numCourses];
        int[] indegree = new int[numCourses];

        // get the indegree for each course
        for(int[] pre : prerequisites) {indegree

] ++;

        }
        // put courses with indegree == 0 to queue

        Queue<Integer> queue = new ArrayDeque<>();

        for(int i = 0; i < numCourses; i++) {

            if(indegree[i] == 0) {

                queue.offer(i);

            }

        }
        // execute the course

        int i = 0;

        while(!queue.isEmpty()) {

            Integer curr = queue.poll();

            res[i++] = curr;
            // remove the pre = curr

            for(int[] pre : prerequisites) {

                if(pre[1] == curr) {

                    indegree

] --;

                    if(indegree

] == 0) {

                        queue.offer(pre[0]);

                    }

                }

            }

        }
        return i == numCourses ? res : new int[]{};

    }

}


另外，拓扑排序还能够用 DFS - 深度优先搜寻 来实现，限于篇幅就不在这里开展了，大家能够参考 GeeksforGeeks 的这个材料。
理论利用
咱们上文曾经提到了它的一个 use case，就是选课零碎，这也是最常考的题目。
而拓扑排序最重要的利用就是  要害门路问题，这个问题对应的是 AOE (Activity on Edge) 网络。
AOE 网络：顶点示意事件，边示意流动，边上的权重来示意流动所须要的工夫。
AOV 网络：顶点示意流动，边示意流动之间的依赖关系。
在 AOE 网中，从终点到起点具备最大长度的门路称为要害门路，在要害门路上的流动称为要害流动。AOE 网络个别用来剖析一个大我的项目的工序，剖析至多须要花多少工夫实现，以及每个流动能有多少机动工夫。
具体是怎么利用剖析的，大家能够参考这个视频 的 14 分 46 秒，这个例子还是讲的很好的。
其实对于任何一个工作之间有依赖关系的图，都是实用的。
比方 pom 依赖引入 jar 包时，大家有没有想过它是怎么导进来一些你并没有间接引入的 jar 包的？比方你并没有引入 aop 的 jar 包，但它主动呈现了，这就是因为你导入的一些包是依赖于 aop 这个 jar 包的，那么 maven 就主动帮你导入了。
其余的理论利用，比如说：


语音识别系统的预处理；
治理指标文件之间的依赖关系，就像我刚刚说的 jar 包导入；
深度学习中的网络结构解决。


如有其余补充，欢送大家在评论区不吝赐教。
以上就是本文的全部内容了，拓扑排序是十分重要也是十分爱考的一类算法，面试大厂前肯定要熟练掌握。
如果你喜爱这篇文章，记得给我点赞留言哦～你们的反对和认可，就是我创作的最大能源，咱们下篇文章见！
我是小齐，纽约程序媛，终生学习者，每天晚上 9 点，云自习室里不见不散！
更多干货文章见我的 Github: https://github.com/xiaoqi6666…