有向无环图 · aiwiki.page

有向无环图（DAG）是不含有向环的有向图：沿着边所指示的方向前进，永远不会回到起始顶点。有向无环图是图论的研究对象，也广泛用于计算机科学，以表示先决条件、计算依赖等可以按一致的先后顺序排列的关系。每个有限有向无环图都存在拓扑序，因此可以依次处理其顶点，而不会遇到循环依赖。(algs4.cs.princeton.edu)

定义与基本性质

有向图通常记为 $G=(V,E)$ ，其中 $V$ 是顶点集合， $E\subseteq V\times V$ 是由表示边的有序对组成的集合。边 $(u,v)$ 记作 $u\to v$ ，表示从 $u$ 指向 $v$ 。有向路径沿各条边指定的方向依次前进；有向环则会回到起始顶点。有向无环图排除了所有这类环，包括自环 $v\to v$ 。除非另有说明，关于算法的讨论均针对有限图。(algs4.cs.princeton.edu)

顶点的入度是指向该顶点的边数，出度则是从该顶点出发的边数。入度为零的顶点称为源点，出度为零的顶点称为汇点。每个非空的有限有向无环图都至少有一个源点和一个汇点。从某个顶点可达的顶点称为它的后代，而能够到达该顶点的顶点称为它的祖先。这些术语所指的是路径关系，而不只是直接相连的边。(networkx.org)

无环性取决于边的方向，而不是图画出来的外观。例如，边 $A\to B$ 、 $B\to C$ 和 $A\to C$ 构成一个有向无环图，尽管忽略方向后，它们形成了一个无向三角形。有向无环图不一定连通，也不一定只有一个源点。(networkx.org)

拓扑序

拓扑序是一种顶点排列，使每条边都从排列中较靠前的顶点指向较靠后的顶点。有限有向图存在这种排列，当且仅当它是无环的。拓扑序不一定唯一：依赖关系未限定相对次序的顶点，可以出现在不同位置。因此，有向无环图规定的是先后约束，而不一定规定唯一的执行顺序。(algs4.cs.princeton.edu)

一种算法反复选择一个源点，将其追加到排列中，并删除它的所有出边。由此产生的新源点也可供后续选择。如果已无源点可选，但仍有顶点尚未处理，那么剩余图中就包含有向环。另一种方法使用深度优先搜索：检查并确认不存在环后，按搜索完成时间的逆序排列顶点。(algs4.cs.princeton.edu)

采用邻接表时，两种方法的时间复杂度均为 $O(|V|+|E|)$ ，这里使用了大O记号。逐个移除源点也为拓扑序定理提供了构造性的解释：当且仅当没有有向环阻碍这一过程时，才能不断选择源点，直到所有顶点都被处理。(networkx.org)

可达性与偏序

有向无环图将图结构与偏序联系起来。定义 $u\preceq v$ 表示 $u=v$ ，或存在一条从 $u$ 到 $v$ 的有向路径。这个二元关系具有自反性和传递性；它也具有反对称性，因为如果两个不同顶点之间在两个方向上都存在路径，就会形成环。若两个顶点之间在任一方向上都不存在路径，则它们不可比。拓扑序将这一偏序扩展为线性序。(courses.csail.mit.edu)

传递闭包记录可达性所蕴含的全部关系：只要存在从 $u$ 到 $v$ 的正长度路径，就加入边 $u\to v$ 。传递约简则删除冗余边，同时保持可达性不变。有限有向无环图的传递约简是唯一的。在前述三角形示例中， $A\to C$ 是冗余边，因为 $A\to B\to C$ 已经确立了相同的先后关系。传递约简保留可达性，但不一定保留边权或直接依赖信息。(networkx.org)

路径算法与依赖调度

拓扑序可用于动态规划，因为处理某个顶点之前，其前驱顶点的计算结果已经可用。对于单源最短路径问题，先将起点的距离初始化为零，其他顶点的距离初始化为无穷大。然后按拓扑序处理顶点，并对每条出边进行松弛：

d(v)\leftarrow\min\{d(v),\,d(u)+w(u,v)\}.

每条边只需检查一次，因此包括计算拓扑序在内，总运行时间为 $O(|V|+|E|)$ 。边权可以为负，因为图中不存在有向环，因而也不存在负权环。(cs.princeton.edu)

同样，将最小化改为最大化，并将不可达顶点的距离初始化为负无穷大，就可以计算最长路径。这为关键路径法提供了支持，该方法用于调度具有持续时间和先后约束的任务。在处理器数量不受限制且没有其他资源约束的模型下，最长的依赖路径决定了最短完成时间。当资源有限而引入额外约束时，仅凭拓扑序并不能确定最优调度方案。(algs4.cs.princeton.edu)

概率模型与计算模型

在贝叶斯网络中，有向无环图的顶点代表随机变量，图结构则编码了条件独立假设。结合各变量的局部条件分布，它通过下式表示一个联合概率分布：

P(X_1,\ldots,X_n) =\prod_{i=1}^{n}P\!\left(X_i\mid\operatorname{Pa}(X_i)\right),

其中， $\operatorname{Pa}(X_i)$ 表示 $X_i$ 的父节点。d分离这一图判据可识别该分解所蕴含的独立性关系。图中的箭头并不意味着在所有可能的参数取值下都存在统计依赖。(cs.cmu.edu)

有向无环图也用于表示自动微分中的计算图。前向计算时，各项运算依赖先前得到的值；反向传播则沿这些依赖关系反向遍历，运用链式法则累积导数。共享中间结果使同一个计算值能够用于多个后续运算，而无需重复计算。这里的无环性针对的是实际执行的计算所记录的依赖关系，即使生成这次计算的程序本身包含循环，也不受影响。(docs.pytorch.org)