有向无环图

DAG 用“没有有向环”表示纯依赖关系：沿箭头只能向前，不能经过若干依赖又回到自己，因此依赖可以从前到后展开。每条路径都有限，因而至少存在入度为零的源和出度为零的汇；拓扑序把偏序补成某个兼容全序，却不抹掉哪些任务原本可并行。很多一般图上的循环依赖困难，在 DAG 上都转化为一次线性扫描。

边 $A\to C,B\to C,C\to D$ 的图有拓扑序 $A,B,C,D$ 或 $B,A,C,D$，说明拓扑序不必唯一。沿拓扑序可计算最长路：到 $C$ 的值在处理 $C$ 前已由所有前驱确定。

课程先修图和构建系统依赖应形成 DAG；若 A 依赖 B、B 又依赖 A，就不存在可执行顺序。若所用有向图变体允许自环，一条自环也已经构成有向圈。树定向后是 DAG，但 DAG 可有共享后继和多个父节点。无向图“无环”得到森林，与 DAG 概念不同；有向图即使底层无向图有环，例如把三角形边统一朝同一拓扑方向，也可能仍是 DAG。若 Kahn 算法提前没有入度零点且仍有未删顶点，剩余部分必含有向圈。DAG 上的最短路即使有负边也可按拓扑序松弛。

拓扑排序公理库拓扑排序Topological sort给有向无环图顶点排列线性次序，使每条边从前指向后。是识别和利用 DAG 的基本算法。把每个顶点看成任务时，拓扑序只给出一个合法串行次序；工作—深度模型公理库Work–Depth 模型work-depth model · work-span model · computation DAG model把并行计算表示为依赖 DAG，以总工作 W 和关键路径深度 D 分离工作量与并行性。进一步区分总工作与最长依赖链，使互不依赖的顶点可以并行执行。两项指标不能由“有拓扑序”自动推出。

DAG 动态规划、构建系统、版本与课程依赖、任务调度、数据流和因果图都利用这一结构。若控制流图公理库控制流图Control-flow graph · Program control-flow graph以基本块或程序点为节点、以可能的执行转移为边表示过程内控制流的有向图。无环，数据流事实可沿拓扑序一次传播；出现回边后，同一方程组通常要由单调数据流分析公理库单调数据流分析Monotone dataflow analysis · Monotone framework · Data-flow equations在控制流图上以单调 transfer 和合流方程求解前向或后向程序事实。迭代到不动点。DAG 在这里描述依赖形状，抽象域与转移函数给出语义，worklist 才是求解算法。

支配树公理库支配树与 Lengauer–Tarjan 算法Dominator tree · Lengauer–Tarjan algorithm · 支配树在单入口流图中用 DFS 半支配点、延迟桶处理和带路径压缩的祖先查询计算立即支配点与支配树。研究的是单入口有向图中所有入口路径的必经关系，即使图本身有环也可定义；树宽动态规划公理库树宽上的动态规划treewidth dynamic programming · DP on tree decompositions在 nice tree decomposition 的小 bag 边界上记录状态，以 f(k)n 时间求解近树图问题。则沿树分解处理一般图，不要求原图是 DAG。压缩强连通分量公理库强连通分量算法Strongly connected components algorithm在线性时间内把有向图划分为互相可达的极大顶点集合。后得到的凝聚图必为 DAG，正是把有环输入接到这些 DAG 方法之前必须完成的结构化步骤。