有向无环图 (DAG)

在计算机科学和数学中，有向无环图 (DAG) 是一种有向且没有环连接其他边的图。这意味着不可能从一条边开始遍历整个图。有向图的边只有一种方式。该图是一种拓扑排序，其中每个节点都按一定的顺序排列。

在图论中，图是由边连接的一系列顶点。在有向图中，边是相连的，所以每条边只能走一条路。有向无环图意味着该图不是循环的，或者不可能从图中的一个点开始并遍历整个图。每条边都从较早的边指向较​​晚的边。这也称为图的拓扑排序。

电子表格可以表示为有向无环图，当公式引用另一个单元格时，每个单元格都有一个顶点和一条边连接一个单元格。其他应用包括调度、电路设计和贝叶斯网络。