OI-wiki 图论专题有向无环图DAG的定义、判定与 DP 最长短路求解【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki有向无环图Directed Acyclic Graph简称 DAG是图论与算法竞赛OI/ICPC中最基础也最高频的模型之一凡涉及「依赖关系」「先后顺序」的问题几乎都能抽象为 DAG。本篇文章以 OI-wiki 的 DAG 专题 为主线系统讲解 DAG 的定义与核心性质、两种判环方法拓扑排序与 DFS 返祖边并重点展开 DAG 上的 DP 求单源最长短路技术给出可直接运行的最短路/最长路代码以及 UVa 437 巴比伦塔的完整建模与测试样例。读完本文你将掌握「判定一个有向图是否为 DAG」「在 DAG 上用 O(nm) 的 DP 替代 Bellman–Ford / Dijkstra」两类核心实战能力。定义边有向无环有向无环图DAG是满足以下两个条件的图边有向图中每一条边都有明确的方向即 $u \to v$ 与 $v \to u$ 是两条不同的边无环图中不存在任何一条从某个顶点出发、经过若干条有向边后回到该顶点的回路环。英文全称为Directed Acyclic Graph缩写为DAG。在 拓扑排序 中DAG 用于刻画带有先后依赖关系的一类模型例如大学排课中「学习『数据结构』前必须先学『离散数学』」把每门课看作顶点、把「先修关系」看作有向边得到的正是一张 DAG。任何一个 AOV 网Activity On Vertex Network顶点表示活动的网络都必定是有向无环图。性质与拓扑排序等价DAG 最核心的性质是它与拓扑排序互为充要条件能拓扑排序的图一定是有向无环图如果图中有环那么环上的任意两个节点在任意线性序列中都互为先后、无法同时满足「$u$ 排在 $v$ 前」与「$v$ 排在 $u$ 前」两个条件因此不存在合法的拓扑序列。有向无环图一定能拓扑排序可以用归纳法证明。假设节点数不超过 $k$ 的有向无环图都能拓扑排序那么对于节点数恰好等于 $k$ 的 DAG由于无环图中必然存在入度为 $0$ 的节点否则沿入边逆推会形成环将该节点删除后剩余部分仍是节点数更少的 DAG按归纳假设可完成排序再把删除的节点放在最前面即可。考虑执行拓扑排序第一步之后的情形即可完成归纳。正是这两条性质使「能否拓扑排序」成为判定 DAG 的黄金标准一个图是有向无环图当且仅当它可以被完整地拓扑排序。判定方法方法一检验是否可拓扑排序由于「可拓扑排序 $\Leftrightarrow$ 有向无环」最直接的判定方式就是对图执行一次 拓扑排序若拓扑序列包含了全部 $n$ 个节点则图无环是 DAG若中途找不到入度为 $0$ 的节点而提前终止说明图中存在环。以 Kahn 算法为例在 拓扑排序 的实现中当L.size() n时返回true否则返回false正是用「是否排完所有节点」来判环。检测 AOV 网中是否带环的方式同样是构造拓扑序列并检查序列是否包含所有顶点。方法二DFS 检查返祖边除了拓扑排序还可以对图进行一遍 DFS即docs/search/dfs.md中介绍的深度优先搜索在得到的 DFS 树上检查是否存在连向祖先的非树边返祖边若 DFS 过程中发现某条边指向当前搜索栈中尚未回溯的祖先节点说明存在返祖边图中必有环若整轮 DFS 遍历结束都没有出现返祖边则图是 DAG。实现上通常给每个节点标记三种状态to_visit/visiting/visitedDFS 进入节点时置为visiting若某条出边指向一个仍处于visiting状态的节点即为返祖边、直接判环拓扑排序 的 DFS 版实现TopoSort::dfs正是借助这一机制在返回false时判定图中存在环。两种判定方法各有适用场景拓扑排序法同时给出了合法的节点顺序适合后续继续做 DP 的场合DFS 法只需线性遍历一遍图适合仅需「快速判断是否有环」的场合两者时间复杂度均为 $O(nm)$。应用DAG 上的 DP 求单源最长短路为什么 DAG 上可以用 DP在一般图上求单源最短路常见做法有时间复杂度 $O(nm)$ 的 Bellman–Ford 算法适用于带负权边的图以及 $O(m \log m)$ 的 Dijkstra 算法适用于无负权边的图。但在DAG上由于不存在环每个节点的最短路最长路只依赖于它的前驱天然满足无后效性动态规划的最优子结构 无后效性要求因此可以用 DP 在 $O(nm)$ 时间内求出单源最长短路显著优于上述通用算法。状态转移方程为$$ dis_v \min(dis_v, dis_u w_{u,v}) \quad \text{求最短路} $$$$ dis_v \max(dis_v, dis_u w_{u,v}) \quad \text{求最长路} $$具体做法是先做拓扑排序然后按照拓扑序遍历每个节点用当前节点去更新其所有后继节点。由于拓扑序保证了处理节点 $u$ 时所有能到达 $u$ 的前驱都已被处理完毕因此每轮更新的 $dis_u$ 都是最终值一趟线性扫描即可完成全部松弛。完整实现以下为 dag.md 中给出的完整代码toposort()基于 Kahn 算法队列维护入度为 $0$ 的节点得到拓扑序列Ldp(s)以s为源点按拓扑序依次松弛每条边同时维护最长路max_dis与最短路min_dis。struct edge { int v, w; }; int n, m; vectoredge e[MAXN]; vectorint L; // 存储拓扑排序结果 int max_dis[MAXN], min_dis[MAXN], in[MAXN]; // in 存储每个节点的入度 void toposort() { // 拓扑排序 queueint S; memset(in, 0, sizeof(in)); for (int i 1; i n; i) { for (int j 0; j e[i].size(); j) { in[e[i][j].v]; } } for (int i 1; i n; i) if (in[i] 0) S.push(i); while (!S.empty()) { int u S.front(); S.pop(); L.push_back(u); for (int i 0; i e[u].size(); i) { if (--in[e[u][i].v] 0) { S.push(e[u][i].v); } } } } void dp(int s) { // 以 s 为起点求单源最长短路 toposort(); // 先进行拓扑排序 memset(min_dis, 0x3f, sizeof(min_dis)); memset(max_dis, 0, sizeof(max_dis)); min_dis[s] 0; for (int i 0; i L.size(); i) { int u L[i]; for (int j 0; j e[u].size(); j) { min_dis[e[u][j].v] min(min_dis[e[u][j].v], min_dis[u] e[u][j].w); max_dis[e[u][j].v] max(max_dis[e[u][j].v], max_dis[u] e[u][j].w); } } }代码要点入度统计in[]数组记录每个节点的入度初始入度为 $0$ 的节点全部入队S拓扑排序每次取出队首u加入L并将u的所有出边「删除」等价于对其后继的入度减一一旦某后继入度降为 $0$ 就入队DP 松弛按拓扑序L处理节点u对每条出边 $u \to v$ 用dis[u] w更新dis[v]因为拓扑序保证 $u$ 的dis已是最终值所以最终所有可达节点的dis均为最优解初始化约定min_dis用0x3f初始化表示无穷大max_dis初始化为 $0$源点s的最短路置为 $0$。扩展DAG 上的 DP 建模实战UVa 437 巴比伦塔DAG 上 DP 的价值不止于最短路/最长路本身——很多实际问题都可以建模成 DAG从而转化为 DAG 上的最长路问题。OI-wiki 的 DAG 上的 DP 以 UVa 437「巴比伦塔 The Tower of Babylon」为例给出了完整建模过程这是 DAG 建模的经典范式。问题描述有 $n\ (n \leqslant 30)$ 种砖块已知三种边长每种砖块有无限多个。要求选出一些长方体摞成尽量高的柱子每个砖块可以自行选择一条边作为高并且要求每个砖块的底面长宽分别严格小于其下方砖块的底面长宽求塔的最大高度。建模为 DAG 的要点依赖关系建图若砖块 $j$ 能放在砖块 $i$ 上则建立有向边 $(i, j)$边权为砖块 $j$ 所选取的高。由于「底面严格小于」构成偏序关系图中不会出现环整张图是一张 DAG问题随之转化为最长路问题。每种砖拆成三种堆叠方式一个砖块有三种选高的方式底面由另两条边构成因此把一个砖块拆解为三个「砖块」每个拆解出的砖块选取不同的高。如下图所示蓝色实线框表示同一个原始砖块拆出的一组砖块由于一旦选定了高底面边长就是无序的用集合 ${}$ 表示底面边长。起点与终点起点是「大地」其底面可视为无穷大因此大地可达任意砖块编程时不必显式写出无穷大终点自然落在「不能再往上搭砖块」的某个砖块上。转移方程设 $d(i,r)$ 表示第 $i$ 块砖在最下面、且采取第 $r$ 种堆叠方式时的最大高度则$$ d(i, r) \max\left{d(j, r) h\right} $$其中 $j$ 是所有能放在「以 $r$ 方式堆叠的砖块 $i$」上方的砖块$r$ 是 $j$ 对应的摆放方式$h$ 是砖块 $i$ 采用第 $r$ 种堆叠方式时的高度。下图来自 DAG 上的 DP展示了两个砖块三边分别为 $31,41,59$ 与 $33,83,27$建模得到的 DAG其中黄色虚线框标出了重复计算的子问题可以用记忆化搜索避免重复计算完整实现dag_1.cpp使用记忆化搜索递归求解rot表示三种摆放方向0、1、2 分别对应三种「底面组合 高」的选择转移时枚举所有能放上去的砖块及其三种方向#include cmath #include cstring #include iostream using namespace std; constexpr int MAXN 30 5; constexpr int MAXV 500 5; int d[MAXN][3]; int x[MAXN], y[MAXN], z[MAXN]; int babylon_sub(int c, int rot, int n) { if (d[c][rot] ! -1) { return d[c][rot]; } d[c][rot] 0; int base1, base2; if (rot 0) { // 处理三个方向 base1 x[c]; base2 y[c]; } if (rot 1) { base1 y[c]; base2 z[c]; } if (rot 2) { base1 x[c]; base2 z[c]; } for (int i 0; i n; i) { // 根据不同条件分别调用不同的递归 if ((x[i] base1 y[i] base2) || (y[i] base1 x[i] base2)) d[c][rot] max(d[c][rot], babylon_sub(i, 0, n) z[i]); if ((y[i] base1 z[i] base2) || (z[i] base1 y[i] base2)) d[c][rot] max(d[c][rot], babylon_sub(i, 1, n) x[i]); if ((x[i] base1 z[i] base2) || (z[i] base1 x[i] base2)) d[c][rot] max(d[c][rot], babylon_sub(i, 2, n) y[i]); } return d[c][rot]; } int babylon(int n) { for (int i 0; i n; i) { d[i][0] -1; d[i][1] -1; d[i][2] -1; } int r 0; for (int i 0; i n; i) { // 三种建法 r max(r, babylon_sub(i, 0, n) z[i]); r max(r, babylon_sub(i, 1, n) x[i]); r max(r, babylon_sub(i, 2, n) y[i]); } return r; } int main() { int t 0; while (true) { // 死循环求答案 int n; cin n; if (n 0) break; // 没有砖头了就停止 t; for (int i 0; i n; i) { cin x[i] y[i] z[i]; } cout Case t : maximum height babylon(n); // 递归 cout endl; } return 0; }仓库的测试目录 docs/dp/examples/dag 中提供了该程序的输入与标准输出输入 dag_1.in 包含多组数据例如第一组只有一块 $10 \times 20 \times 30$ 的砖答案为 $40$即取最长边 $30$ 为高并选一种堆叠配合旋转使底面满足严格小于关系最后一组包含 $31,41,59$ 与 $33,83,27$ 等砖块以0结束输入标准答案 dag_1.ans 依次给出Case 1: maximum height 40 Case 2: maximum height 21 Case 3: maximum height 28 Case 4: maximum height 342对照运行你的实现可以快速验证 DAG 建模与记忆化搜索的正确性。这种「把偏序依赖关系建成 DAG → 求最长路」的思路还可推广到嵌套矩形、任务调度等大量题目中。总结回顾本文核心脉络DAG 有向 无环它刻画了所有「依赖 / 先后」关系的本质判定 DAG 有两条等价路径拓扑排序排完全部节点则无环DFS 中发现返祖边则有环DAG 的最大红利是 DP拓扑序消除后效性使单源最长短路从 $O(nm)$Bellman–Ford或 $O(m\log m)$Dijkstra降至 $O(nm)$建模范式把实际问题中的偏序关系转化为有向边即可套用「建 DAG DP/记忆化搜索」的通用解法巴比伦塔即为经典模板。如需深入可继续阅读 OI-wiki 中的 拓扑排序Kahn 算法与 DFS 算法的完整实现、字典序最大/最小拓扑序、DAG 上的 DP更多建模案例以及 最短路Bellman–Ford 与 Dijkstra 的适用场景对比。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考