浅谈什么是图拓扑排序

ゝ一纸荒年。 2022-02-05 06:34 278阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

### 1 引言 ###

在工程实践中,一个工程项目往往由若干个子项目组成。这些子项目间往往有两种关系:  
  （1） 先后关系，即必须在某个项完成后才能开始实施另一个子项目。  
  （2） 子项目间无关系，即两个子项目可以同时进行,互不影响。

例如：在工厂里产品的生产线上，一个产品由若干个零部件组成。零部件生产时，也存在这两种关系:  
  （1）先后关系，即一个部件必须在完成后才能生产另一个部件;  
  （2）部件间无先后关系，即这两个部件可以同时生产。  
  那么如何合理的分配资源才能保证工程能够按时完成呢？将任务作为图的顶点，将任务之间的依赖关系作为图的边，这样就可以将实际问题抽象为数据结构图论中的典型问题——图的拓扑排序。

### 2 重要概念 ###

**有向无环图（Directed Acyclic Graph, DAG）**是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。  
  **AOV网：**在每一个工程中，可以将工程分为若干个子工程，这些子工程称为活动。如果用图中的顶点表示活动，以有向图的弧表示活动之间的优先关系，这样的有向图称为AOV网，即顶点表示活动的网。在AOV网中，如果从顶点vi到顶点j之间存在一条路径，则顶点vi是顶点vj的前驱，顶点vj是顶点vi的后继。活动中的制约关系可以通过AOV网中的表示。 在AOV网中，不允许出现环，如果出现环就表示某个活动是自己的先决条件。因此需要对AOV网判断是否存在环，可以利用有向图的拓扑排序进行判断。  
  **拓扑序列：**设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,…,vn,满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在vj之前，则我们称这样的顶点序列为一个拓扑序列。  
  **拓扑排序：**拓扑排序是对一个有向图构造拓扑序列的过程。

### 3 拓扑排序 ###

**拓扑排序（Topological Sorting）**是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：  
  （1）每个顶点出现且只出现一次。  
  （2）若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。  
  注：有向无环图（DAG）才有拓扑排序，非DAG图没有拓扑排序一说。

### 4 入度表法 ###

入度表法是根据顶点的入度来判断是否存在依赖关系。若顶点入度不为0。则必然此顶点的事件有前驱依赖事件，因此每次选取入度为0的顶点输出，则符合拓扑排序的性质。

#### 4.1 算法流程 ####

（1）从图中选择一个入度为0的顶点，输出该顶点。  
（2）从图中删除该节点及其所有出边（即与之邻接的所有顶点入度-1）  
（3）反复执行这两个步骤，直至所有节点都输出，即整个拓扑排序完成；或者直至剩下的图中再没有入度为0的节点，这就说明此图中有回路，不可能进行拓扑排序。

#### 4.2 实例图解 ####

例如：图4.2.1所示的有向无环图，采用入度表的方法获取拓扑排序过程。

![640?wx\_fmt=png][640_wx_fmt_png] 4.2.1  
（1）选择图中入度为0的顶点1，输出顶点1。删除顶点1，并删除以顶点1为尾的边。删除后图为：  
![640?wx\_fmt=png][640_wx_fmt_png 1]  
  
（2）继续选择入度为0的顶点。现在，图中入度为0的顶点有2和4，这里我们选择顶点2，输出顶点2。删除顶点2，并删除以顶点2为尾的边。删除后图为：  
![640?wx\_fmt=png][640_wx_fmt_png 2]  
  
（3）选择入度为0的顶点4，输出顶点4.删除顶点4，并删除以顶点4为尾的边。删除后图为：  
![640?wx\_fmt=png][640_wx_fmt_png 3]  
  
（4）选择入度为0的顶点3，输出顶点3.删除顶点3，并删除以顶点3为尾的边。删除后图为：  
![640?wx\_fmt=png][640_wx_fmt_png 4]  
  
（5）最后剩余顶点5，输出顶点5，拓扑排序过程结束。最终的输出结果为：  
![640?wx\_fmt=png][640_wx_fmt_png 5]

#### 4.3 性能分析 ####

算法时间复杂度分析：统计所有节点入度的时间复杂性为（VE）；接下来删边花费的时间也是（VE），总花费时间为O（VE）。若使用队列保存入度为0的顶点，则可以将这个算法复杂度将为O（V+E）。

### 5 DFS方法 ###

深度优先搜索过程中，当到达出度为0的顶点时，需要进行回退。在执行回退时记录出度为0的顶点，将其入栈。则最终出栈顺序的逆序即为拓扑排序序列。

#### 5.1 算法流程 ####

（1）对图执行深度优先搜索。  
（2）在执行深度优先搜索时，若某个顶点不能继续前进，即顶点的出度为0，则将此顶点入栈。  
（3）最后得到栈中顺序的逆序即为拓扑排序顺序。

#### 5.2 实例图解 ####

例如图5.2.1所示的有向无环图，采用DFS的方法获取拓扑排序过程。

![640?wx\_fmt=png][640_wx_fmt_png 6] 5.2.1  
（1）选择起点为顶点1,，开始执行深度优先搜索。顺序为1->2->3->5。  
![640?wx\_fmt=png][640_wx_fmt_png 7]  
  
（2）深度优先搜索到达顶点5时，顶点5出度为0。将顶点5入栈。  
![640?wx\_fmt=png][640_wx_fmt_png 8]  
  
（3）深度优先搜索执行回退，回退至顶点3。此时顶点3的出度为0，将顶点3入栈。  
![640?wx\_fmt=png][640_wx_fmt_png 9]  
  
（4）回退至顶点2，顶点2出度为0，顶点2入栈。  
![640?wx\_fmt=png][640_wx_fmt_png 10]  
  
（5）回退至顶点1，顶点1可以前进位置为顶点4，顺序为1->4。  
![640?wx\_fmt=png][640_wx_fmt_png 11]  
  
（6）顶点4出度为0，顶点4入栈。  
![640?wx\_fmt=png][640_wx_fmt_png 12]  
  
（7）回退至顶点1，顶点1出度为0，顶点1入栈。  
![640?wx\_fmt=png][640_wx_fmt_png 13]  
  
（8）栈的逆序为1->4->2->3->5。此顺序为拓扑排序结果。

#### 5.3 性能分析 ####

时间复杂度分析：首先深度优先搜索的时间复杂度为O(V+E)，而每次只需将完成访问的顶点存入数组中，需要O(1)，因而总复杂度为O(V+E)。

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[有点难度，几道和「滑动窗口」有关的算法面试题][Link 2]

[数据结构与算法：三十张图弄懂「图的两种遍历方式」][Link 3]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 4]

[几道和散列（哈希）表有关的面试题][Link 5]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 6]

[几道和「堆栈、队列」有关的面试算法题][Link 7]

[链表算法面试问题？看我就够了！][Link 8]

我就知道你在看！

[640_wx_fmt_jpeg]: /images/20220205/b4e985c560e7456496263088cdfc2b88.png
[640_wx_fmt_png]: /images/20220205/c1f4ed4e7b4b4d3db79c509d5a4bf182.png
[640_wx_fmt_png 1]: /images/20220205/0658b6a234264368b36c46d56f762797.png
[640_wx_fmt_png 2]: /images/20220205/9130ab5fbc804912b61f2e380c964970.png
[640_wx_fmt_png 3]: /images/20220205/fc408732d2ad477c8ee929a950f6c83b.png
[640_wx_fmt_png 4]: /images/20220205/767e73cf0d854535970793a87710e073.png
[640_wx_fmt_png 5]: /images/20220205/03842dd61ad0433aaeca755b67639a99.png
[640_wx_fmt_png 6]: /images/20220205/af895b5a87f14b108d3aa4e421423e93.png
[640_wx_fmt_png 7]: /images/20220205/4729994b6f5a4fb4a226d94f4a0abe6d.png
[640_wx_fmt_png 8]: /images/20220205/08e554e6dfbb4383befb3ba8484a02d2.png
[640_wx_fmt_png 9]: /images/20220205/482fe2f22b7a4a80a7e2cc7fd3e7cdc9.png
[640_wx_fmt_png 10]: /images/20220205/01719601691a4b819588df6fd20cb7fc.png
[640_wx_fmt_png 11]: /images/20220205/8e2514a4f733481d94c4e02ff45006f2.png
[640_wx_fmt_png 12]: /images/20220205/2c73c95c5d7e47c699ee933e65db401d.png
[640_wx_fmt_png 13]: /images/20220205/2ae4534b769f42d6a9768d5f5f87ed0c.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485197&idx=1&sn=1bbd40d49adb09875fd324664bd5bc8b&chksm=fa0e688ccd79e19a36599b53e4a8acf9a725ace3f6df28925075ff25778238471a283f0f8e1f&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 8]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect