DAG 图全称为 Directed Acyclic Graph，就是一个有向 + 无环的图。

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

Ⅱ. `AOV`网 -- 顶点活动图

定义：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为**AOV网（Activity On Vertex Network），AOV**网中的弧表示活动之间的某种约束关系。

此外 AOV 网中不存在回路（即有向无环图），如下图所示：

Ⅲ. 拓扑排序

其实拓扑排序非常的简单，一些书上的概念说的比较复杂，我们只需要记住，拓扑排序就是找到 AOV 网中活动的先后执行顺序，所以拓扑排序的结果不是唯一的，因为一些活动是可以并行的。

比如将上面途中的炒肉顺序，按照先后次序可以得到下面的一种情况：

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

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

初始化：
- 把所有入度为 0 的节点加入到队列中
当队列不为空的时候：
1. 拿出队头节点，加入到最终结果中。
2. 删除与该元素相连的边。
3. 进行判断：
  - 判断与删除边相连的点，是否入度变成了 0，如果为 0 的话则将其加入到队列中。

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

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

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

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

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