【拓扑排序】有向无环图、定点活动图、拓扑排序简介

【拓扑排序】有向无环图、定点活动图、拓扑排序简介

Ⅰ. 有向无环图（DAG图）

DAG图全称为Directed Acyclic Graph，就是一个有向 + 无环的图。DAG图是相较于有向树的更特殊的图。它的作用挺重要的，比如：检查一个图是否有环，可以通过遍历+标记的方式进行检查，若某个顶点的弧指向了另一个已经遍历过的顶点，则该图必定含有环。

Ⅱ. AOV网 – 顶点活动图

定义：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网（Activity On Vertex Network），AOV网中的弧表示活动之间的某种约束关系。此外AOV网中不存在回路（即有向无环图），如下图所示：

Ⅲ. 拓扑排序

其实拓扑排序非常的简单，一些书上的概念说的比较复杂，我们只需要记住，拓扑排序就是找到AOV网中活动的先后执行顺序，所以拓扑排序的结果不是唯一的，因为一些活动是可以并行的。比如将上面途中的炒肉顺序，按照先后次序可以得到下面的一种情况：

并且拓扑排序不能出现环，因为其实现原理中如果出现了环的话，就无法得出一个序列了，所以拓扑排序的应用之一就是用来判断图中是否存在环！

Ⅳ. 实现拓扑排序

可以看到其实拓扑排序并不难，无非就是借助队列和BFS来完成！下面是实现的步骤：

1. 初始化：

• 把所有入度为0的节点加入到队列中

2. 当队列不为空的时候：
3. 拿出队头节点，加入到最终结果中。
4. 删除与该元素相连的边。
5. 进行判断：

• 判断与删除边相连的点，是否入度变成了0，如果为0的话则将其加入到队列中。

但此时有一个问题，就是我们需要建图，并且需要知道每个节点的入度，所以我们有两种方式来建图：

1. 看稠密度（即看数据量大小）

• 邻接矩阵
• 邻接表

2. 根据算法流程，灵活建图

一般来说邻接矩阵比较简单，我们这里主要来讲一下邻接表的建图方式！邻接表的建图方式不一定就要用链表结构来实现，也是可以使用 STL 中一些容器比如说vector或者unordered_map来实现，如下所示：

• vector<vector>
• unordered_map<T, vector>

可以看到这两种方式其实和链表结构的思想是差不多的，并且使用哈希表来作为邻接表的建图方式是更加灵活的，因为它两个参数的类型是可以不同的！所以后面我们大多都是采用哈希表来建立邻接表！

而至于节点的入度的话，我们可以单独用一个vector存放入度，然后只需要在建图的过程中将指向当前节点的次数累加一下即可！

具体如何建图以及求入度，可以看后面具体的ti’mu