有向无环图

图论 / dag

本地源文件：docs/graph__dag.md

有向无环图

定义

边有向，无环．

英文名叫 Directed Acyclic Graph，缩写是 DAG．

性质

如果有环，那么环上的任意两个节点在任意序列中都不满足条件了．

  • 有向无环图，一定能拓扑排序；

（归纳法）假设节点数不超过 𝑘k 的 有向无环图都能拓扑排序，那么对于节点数等于 𝑘k 的，考虑执行拓扑排序第一步之后的情形即可．

判定

如何判定一个图是否是有向无环图呢？

检验它是否可以进行 拓扑排序 即可．

当然也有另外的方法，可以对图进行一遍 DFS，在得到的 DFS 树上看看有没有连向祖先的非树边（返祖边）．如果有的话，那就有环了．

应用

DP 求最长（短）路

在一般图上，求单源最长（短）路径的最优时间复杂度为 𝑂(𝑛𝑚)O(nm)（Bellman–Ford 算法，适用于有负权图）或 𝑂(𝑚log⁡𝑚)O(mlog⁡m)（Dijkstra 算法，适用于无负权图）．

但在 DAG 上，我们可以使用 DP 求最长（短）路，使时间复杂度优化到 𝑂(𝑛 +𝑚)O(n+m)．状态转移方程为 𝑑𝑖𝑠𝑣 =𝑚𝑖𝑛(𝑑𝑖𝑠𝑣,𝑑𝑖𝑠𝑢 +𝑤𝑢,𝑣)disv=min(disv,disu+wu,v) 或 𝑑𝑖𝑠𝑣 =𝑚𝑎𝑥(𝑑𝑖𝑠𝑣,𝑑𝑖𝑠𝑢 +𝑤𝑢,𝑣)disv=max(disv,disu+wu,v)．

拓扑排序后，按照拓扑序遍历每个节点，用当前节点来更新之后的节点．

---|---

参见：[DAG 上的 DP](../../dp/dag/)．

* * *

>  __本页面最近更新： 2026/1/7 08:56:54，[更新历史](https://github.com/OI-wiki/OI-wiki/commits/master/docs/graph/dag.md)
>  __发现错误？想一起完善？[在 GitHub 上编辑此页！](https://oi-wiki.org/edit-landing/?ref=/graph/dag.md "edit.link.title")
>  __本页面贡献者：[Ir1d](https://github.com/Ir1d), [Enter-tainer](https://github.com/Enter-tainer), [ouuan](https://github.com/ouuan), [Tiphereth-A](https://github.com/Tiphereth-A), [billchenchina](https://github.com/billchenchina), [dong628](https://github.com/dong628), [HeRaNO](https://github.com/HeRaNO)
>  __本页面的全部内容在**[CC BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.zh) 和 [SATA](https://github.com/zTrix/sata-license)** 协议之条款下提供，附加条款亦可能应用