形式陈述

有向无环图（DAG）是不含有向环的有向图。有限有向图是 DAG 当且仅当存在拓扑序，即顶点全序使每条边 $u\to v$$u\to v$ 都满足 $u$$u$ 在 $v$$v$ 前；也等价于每个非空诱导子图都有入度零顶点。Kahn 算法反复删除入度零点，DFS 按完成时间逆序输出，均可在 $O(|V|+|E|)$$O(|V|+|E|)$ 时间求拓扑序或发现环。拓扑序可能不唯一。

直觉

DAG 表示纯依赖关系：沿箭头只能向前，不能经过若干依赖又回到自己。拓扑序把偏序兼容地排成一条线。

例子与边界

课程先修图和构建系统依赖应形成 DAG；若 A 依赖 B、B 依赖 A，就不存在可执行顺序。树定向后是 DAG，但 DAG 可有共享后继和多个父节点。无向图无环与有向图无有向环不同：把三角形边统一朝同一拓扑方向仍是 DAG。Kahn 算法若提前无入度零点且仍有未删顶点，就证明剩余子图含环。DAG 上最短路允许负边，只需按拓扑序松弛。

推论与应用

DAG 支撑任务调度、版本依赖、数据流、因果图和动态规划；缩点后的凝聚图也使一般有向图问题转化为 DAG 问题。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Chs. 1–13。