【数据结构（邓俊辉）学习笔记】图03——拓扑排序

0. 概述

学习下拓扑排序

1. 零入度算法

1. 1 拓扑排序

首先理解下拓扑排序

其实老师经常干这事，如编讲义，将已经知道的知识点串起来变成讲课序列。那怎么串起来呢？将知识点列出，将它们之间的相互关系描述下。要讲priority queue那上一讲需要讲什么内容，要讲hashing需要讲哪些内容，需要罗列出来。但是讲课不可能像分支一样平行一分为二裂开，最终都会变成下面这样平坦的线性序列。

（续）一个好的安排是什么呢？每当讲到一个知识点时，它所依赖的知识点都应该在此前依然讲过，这样就会变成一个线性序列。将原来图中所有的点整理成这样一个线性次序，前面点与后面点的边次序都是前指向后，没有后指向前，这就是对原图的拓扑排序。

1. 2 算法

• 如果真有这么一个图，怎么排呢？
  
  因为这个图有依赖关系，所以是不折不扣的有向图，但有意思的是这里不能有环，如果有环路就有问题。

首先需要找到零入度的点——无任何依赖，在dag图中必然有这么一个点，由于DAG子图亦为DAG，于是可以利用减而治之思想，将这个零入度的点抹掉，接着找下一个零入度点。

• 那么这个算法如何实现？

图中已经有零入度的点A或B，任取一个，这里取A，放入队列中，等价将A点及其边从图中删除。由于DAG的子图亦是DAG，所以还会有零入度的点，将B点放入队列中，然后依次类推，当所有的点都放入队列后，队列中的节点顺序就是拓扑排序。

但这个方法并不好，实现起来比较麻烦，需要每次去找那个零入度的点，而且删除点及其边的时候还要更新相应信息，可能会对图产生伤害，那怎么做呢？看下下面的零出度算法

2. 零出度算法

2.1 算法

说服下自己，DAG既有零入度点也有零出度点，这个很重要，为什么这么讲，因为之前的DFS（深度优先搜索）可以帮我们实现这个方法。

这样要做的事就比较简单，不需要零入度算法那这样改改度数等等。之前已经造出DFS算法，这样就可以搭DFS便车实现零出度算法。

如何实现呢？

2.2 实现

这里引入一个栈，排序结果将以逆序打印出来。随便找一个点，这里首先访问顶点V，将顶点V状态初始值设置为DISCOVERED，接着枚举V的所有邻居，视u的状态，分别处理，后续会做分析。访问所有邻居后，将顶点V的状态设置为VISITED，然后顶点V入栈。

接着还有顶点V的邻居处理方法还未做交代，怎么处理呢？

1. 若顶点U的状态为UNDISCOVERED，更新顶点U的父亲为V，边的状态为TREE，作递归调用，从顶点u处深入。
2. 顶点U的状态为DISCOVERED，一旦发现后向边，即图非DAG图，无拓扑排序，则退出而不再深入。
3. 顶点U的状态为VISITED，更新下顶点状态。

2.3. 复杂度

这里仅额外引入的栈，规模不超过顶点总数O(n)。总体而言，空间复杂度与基本的深度优先搜索算法同样，仍为O(n + e)。该算法的递归跟踪过程与标准DFS搜索完全一致，且各递归实例自身的执行时间依然保持为O(1)，故总体运行时间仍为O(n + e)。