DAG图（有向无环图）

在图论中，如果一个有向图无法从任意顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。
因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。
DAG可用于对数学和 计算机科学中得一些不同种类的结构进行建模。
由于受制于某些任务必须比另一些任务较早执行的限制，必须排序为一个队 列的任务集合可以由一个DAG图来呈现，其中每个顶点表示一个任务，每条边表示一种限制约束，拓扑排序算法可以用来生成一个有效的序列。
DAG也可以用来模拟信息沿着一个一 致性的方向通过处理器网络的过程。
DAG中得可达性关系构成了一个局 部顺序，任何有限的局部顺序可以由DAG使用可达性来呈现。
此外，DAG的可作为一个序列集合的高效利用空间的重叠的子序列的代表性。
相对应的概念，无向图是一个森林，无环的无向图。 
选择森林的一个方向，产生了一种特殊的有向无环图称为polytree 。
不过，也有其他种类的向无环图，它们不是由面向无向无环图的边构成的。
出于这个原因，称其为有向无环图比无环有向图或者无环图更确切。