拓扑排序与 DAG 上的动态规划

发表于 2026-10-16 分类于算法竞赛

用入度为零的队列理解拓扑序的存在性判据，并在拓扑序上做DAG动态规划，附最短时间戳依赖调度的完整实现。

有一类问题，图建出来之后一眼就能看出方向：任务 A 必须在任务 B 之前完成、课程必须先修前置、文件必须先装依赖。这种”有向无环”的结构本身就是解题的关键信息——它不仅告诉你”可以做”，还直接告诉你”按什么顺序做”。这就是拓扑排序，以及它在 DAG 上做动态规划中的应用。

DAG 上的拓扑顺序与 DP 转移方向示意

一、问题背景：为什么”顺序”能被拿来算答案

先看一个典型问题：有 n 个任务，任务 i 需要 t_i 时间，且依赖若干前置任务（前置全部完成才能开始）。问全部任务完成的最早时间。

如果只是”拓扑排序出一个顺序”就够了，问题很简单。但真正有用的观察是：

在拓扑序里，每个点的所有前置邻居都已经处理完了。

这一句话直接支撑了 DAG 上最短路/最长路的转移。为什么普通图上的最短路要跑 Dijkstra/SPFA 反复迭代？因为图可能有环，某个点的答案可能被后来才确定的信息改进。而 DAG 没有环——一个点的所有前驱位置都比它靠前，所以”轮到它的时候，它的答案是最终答案”，一次扫描即可。

这才是 DAG 上 DP 的本质：拓扑序帮我们消除了”答案需要反复修正”的不确定性。

二、思路

2.1 拓扑序的定义与存在性判据

拓扑序是一个顶点排列 v₁, v₂, ..., vₙ，使得对任意边 u → v，u 在排列中一定排在 v 前面。

存在拓扑序的充要条件是：有向图无环。

判据很朴素：把入度为 0 的点挑出来。这些点没有任何前置，可以直接开工。删掉它之后，它的后继的入度减 1，可能又出现新的入度为 0 的点。

2.2 Kahn 算法（入度为零的队列）

把所有入度为 0 的点放入队列 q，计数 cnt = 0
while q 非空:
    u = q.front(); q.pop(); cnt++
    拓扑序.push(u)
    for (u 的每条出边 u->v):
        indeg[v]--
        if indeg[v] == 0: q.push(v)

判环的关键就是最后那句：cnt == n 则无环（存在拓扑序），cnt < n 则有环。

为什么？有环时，环上每个点都有一个来自环内的入边，它的入度永远减不到 0，所以永远进不了队列。环外的点会被全部取出，环上的点一个都出不去，cnt < n。反之，无环时按上面的归纳，每一轮只要还有剩余的点，总能找到至少一个入度为 0 的点（否则沿入边回溯必然成环），所以一定能取完 n 个点。

这条判据极其实用：与其另外写一套 DFS 判环，不如直接跑一次拓扑排序看计数。

2.3 Kahn 算法 vs DFS 版

DFS 版（递归）也能求拓扑序，思路完全不同：访问每个点，对出边递归，回溯时把点压入结果栈，最后把整个栈反转。它靠”递归栈”来模拟后序。

维度	Kahn（拓扑 BFS）	DFS 版
原理	逐层剥离入度为 0 的点	回溯顺序 + 反转
判环方式	`cnt == n`	三色标记（白/灰/黑），撞到灰色即有环
栈溢出风险	无（用队列迭代），`n` 可到 `10⁵~10⁶`	有，`n` 大时容易爆栈（`10⁵` 量级就危险）
输出唯一性	天然给出某一种合法序	同上，但顺序可能与 Kahn 不同
适合场景	还需要入度信息、判环、下游 DP	只是要一个序，且图小

竞赛建议：能用 Kahn 就用 Kahn。 它是迭代的，不会爆栈，还顺手给了入度数组供后续 DP 使用（比如求”最长路径长度”时的层数信息）。DFS 版唯一真正的优势是可以在递归过程中同时做深搜 DP（如树形 DP），这是 Kahn 做不到的。

2.4 在拓扑序上做 DP

以最长路为例：dist[v] = max(dist[u] + w)，对每条边 u → v。

代码上只要在 Kahn 的 while 循环内部加一行转移即可，因为弹出 u 的那一刻，dist[u] 已经是最终答案：

while q 非空:
    u = q.front(); q.pop(); cnt++
    for (u -> v, w):
        dist[v] = max(dist[v], dist[u] + w)   // 此时 dist[u] 已定型
        if --indeg[v] == 0: q.push(v)

注意：转移要在 indeg[v]-- 判定入队之前做，否则顺序反了会导致用旧值转移。

同时需要把 u 记入 order 数组，这样如果你的 DP 写法不适配”边遍历边转移”（比如需要”上一个节点是谁”来还原路径），也可以离线按 order 顺序再扫一遍。

最短路同理，只是把 max 换成 min：DAG 上的最短路不要求边权非负，这正是它比 Dijkstra 更通用的地方。

2.5 多源 BFS 与拓扑 DP 的边界

这两个都常被拿来”求最短距离”，但适用条件完全不同：

	多源 BFS	拓扑 DP
边权	必须全部为 1（或全相同）	任意（可负）
图结构	一般有环也可以	必须是 DAG
源点	多个源点同时出发，取最近的那个	通常单源；多源可建超级源点 0 连向所有源点
本质	求”最少跳数”	求”最小代价路径”
复杂度	`O(n+m)`	`O(n+m)`

判断方法：从题目描述里找线索。 出现”最少经过几条边””最少切换几次””最少几步”→ 多源 BFS；出现”最小代价””最短距离””最长时间”且边权不同 → 拓扑 DP（若有环）或 Dijkstra/SPFA（若无环）。

如果题目要求”所有源点都能到达的最短距离”（即取所有源点起点的最小值），那就是超级源点 + 单源最短路的组合。

2.6 经典应用

工程建造顺序：项目有前置依赖，输出合法的施工顺序；顺序不唯一，用字典序最小化或按 Kahn 出队顺序即可。
课程先修：A 课程是 B 的先修，选修课之间的等价关系（两门互为先修）意味着必须同时修，这是”拓扑排序判环”的变形——等价关系建双向边，有环则无法毕业。
依赖打包 / 构建系统：Make、Ant、包管理器的依赖解析，本质都是拓扑排序；有环时报”循环依赖”。
电子表格求值：单元格 A3 = A1 + A2，反向建边求计算顺序。
任务调度：本题最后一节给出的完整实现。

三、正确性：在拓扑序上做 DP 为什么对

分两层论证。

第一层：Kahn 产出的序列是合法拓扑序。

算法始终只把”当前入度为 0”的点入队并输出。当 v 被输出时，它的入度已减为 0，说明它的所有前驱都已经被输出过（每个前驱被输出时都会把 v 的入度减 1，减到 0 意味着一个不剩）。因此任何边 u → v 都满足 u 先于 v，序列合法。

第二层：拓扑序上的 DP 转移正确。

用归纳法。设拓扑序为 v₁, ..., vₙ。

基础：dist[v₁] = 起点值。v₁ 入度为 0，无前驱，初始值即最终值。
归纳步骤：假设处理到 vᵢ 时，所有 v₁..v_{i-1} 的 dist 均为正确最终值。任何一条到达 vᵢ 的路径，其最后一条边必然是某条 u → vᵢ，而 u 必然在 vᵢ 之前（拓扑序性质），所以 u ∈ {v₁..v_{i-1}}，其 dist[u] 已正确。枚举所有入边取 max（或 min）：
$\text{dist}[v_i] = \max_{(u,v_i,w)} \left( \text{dist}[u] + w \right)$
由于 DAG 中任何到达 vᵢ 的路径都必然来自某个入边（无环 ⇒ 路径不会绕回 vᵢ），这个 max 恰好覆盖了所有可能路径，故结果正确。

核心在于：拓扑序保证了 vᵢ 的所有依赖信息在处理它之前就已定型，无需回溯修正。 对比一下有环的情况——如果存在从 vᵢ 出发又回到 vᵢ 的路径，那么 dist[vᵢ] 会被后续信息改进，单次扫描就不够了，这时才需要 Bellman-Ford 的多轮松弛甚至 Dijkstra 的贪心。

四、复杂度

设点数 n、边数 m：

Kahn 拓扑排序：O(n + m)。每个点入队出队各一次，每条边被遍历一次。
在 Kahn 中融合 DP：仍为 O(n + m)，DP 的常数被”顺手”省掉了——不需要单独再扫一遍图。
空间：O(n + m)，邻接表加 indeg/dist/order 数组。
Floyd 对 DAG 是浪费（O(n³)），Dijkstra 在 DAG 上通常也不必要（虽然正确，非负权时可用）。

DAG 上做 DP 永远只要一遍，复杂度与图规模成正比。

五、参考代码（C++17）

题目：最短时间戳依赖调度。

有 n 个任务，编号 1..n。任务 i 耗时 tᵢ 时间，且有若干前置任务（编号小于 i，因此输入天然无环）。任务 i 必须在它所有前置任务全部完成后才能开始，且可在 t = 0 时刻立即开工。求每个任务的最早开始时间与最早完成时间，并按开始时间从小到大输出全部任务。

这个模型直接覆盖了”流水线依赖调度””最短时间戳”两类题：把时间戳理解成节点的最早可达时刻，转移就是 max；若求”总耗时最短的串行化顺序”，则是求拓扑序上相邻依赖的最优排列。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<long long> cost(n + 1);        // cost[i]：任务 i 的耗时
    for (int i = 1; i <= n; ++i) cin >> cost[i];

    // 邻接表 g[u] 存 u 的后继任务；同时统计每个任务的前置数量
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;                          // 任务 i 依赖的前置任务个数
        indeg[i] = k;
        for (int j = 0; j < k; ++j) {
            int p;
            cin >> p;                      // 前置任务编号
            g[p].push_back(i);             // 边 p -> i
        }
    }

    // Kahn 拓扑排序 + 在拓扑序上做 DP
    // start[i]：任务 i 的最早开始时间
    // finish[i]：任务 i 的最早完成时间
    vector<long long> start(n + 1, 0), finish(n + 1, 0);
    queue<int> q;

    // 所有入度为 0 的任务在 t = 0 即可开工
    for (int i = 1; i <= n; ++i) {
        if (indeg[i] == 0) q.push(i);
    }

    vector<int> order;                     // 记录拓扑序，便于后续离线处理
    order.reserve(n);
    int cnt = 0;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ++cnt;
        order.push_back(u);

        // 此刻 start[u] 已经是最终值：所有前驱都已完成处理
        finish[u] = start[u] + cost[u];

        for (int v : g[u]) {
            // 关键：v 必须等所有前驱都完成，因此取 max 而非直接赋值
            start[v] = max(start[v], finish[u]);

            // 转移完成后再判入队
            if (--indeg[v] == 0) {
                q.push(v);
            }
        }
    }

    if (cnt < n) {
        // 存在环，任务无法被完全调度（本题编号有序时不会出现，保留防御性判断）
        cout << "CYCLE DETECTED\n";
        return 0;
    }

    // 按最早开始时间升序输出；开始时间相同时按编号，保证输出稳定
    vector<int> answer = order;
    sort(answer.begin(), answer.end(), [&](int a, int b) {
        if (start[a] != start[b]) return start[a] < start[b];
        return a < b;
    });

    long long total = 0;
    for (int u : answer) {
        cout << "task " << u
             << " start=" << start[u]
             << " finish=" << finish[u] << '\n';
        total = max(total, finish[u]);    // 全部任务完成的最早时刻
    }
    cout << "total=" << total << '\n';

    return 0;
}

输入格式：

5
5 3 4 2 1        // 任务 1..5 的耗时
0               // 任务 1 无前置
1
1              // 任务 2 依赖任务 1
2
2 4            // 任务 3 依赖任务 2 和任务 4（注意：不是连续编号，且顺序可乱）
1
1              // 任务 4 依赖任务 1
1
3              // 任务 5 依赖任务 3

（第一行是 n 个耗时，第二行起依次是任务 1..n 的前置任务列表。）

输出（按最早开始时间升序）：

task 1 start=0 finish=5
task 2 start=5 finish=8
task 4 start=5 finish=7
task 3 start=8 finish=12
task 5 start=12 finish=13
total=13

验证一下 max 的作用：任务 3 有两个前驱，任务 2 完成于 8、任务 4 完成于 7，所以 start[3] = max(8, 7) = 8。若错写成 start[3] = finish[4]，会得到 7，比真实值早 1 分钟，后续所有任务的时间戳全部偏移——这正是易错点第 2 条。另外注意任务 2 和任务 4 都能在 t=5 开始，说明它们是并行的，这也是”依赖调度”与”串行排序”的本质区别。

六、易错点清单

在拓扑 DP 里写成直接赋值而非取 max：start[v] = finish[u] 只对”每个点恰好一个前驱”成立。多前驱时必须 start[v] = max(start[v], finish[u])。这是本题最常见的 20 分变 0 分点。
转移与入队判定顺序颠倒：必须先转移再 --indeg[v]，否则可能用一个未包含所有前驱贡献的旧值传播出去。
忘记判环：cnt != n 必须单独处理，否则后继的 dist 会停留在残缺状态，答案看着”有数值”但全错。
把 DP 写在出队之前但用了未初始化的数组：多组数据时注意清空。
DFS 版在大图上爆栈：n 到 10⁵ 量级请改用 Kahn。
拓扑序当成唯一确定：拓扑序往往不唯一，题目若要求”字典序最小”，Kahn 需要把队列换成小根堆；若只要求任意合法序，普通队列即可。
混淆”最少步数”与”最小代价”：无边权用多源 BFS，边权不同用拓扑 DP，别用 BFS 处理带权 DAG。
认为 DAG 也需要 SPFA：DAG 上一遍拓扑 DP 就是最优复杂度，SPFA 在 DAG 上的表现只是”恰好也对”，慢且没必要。
输出格式漏掉换行或末尾空格：评测机对格式的容忍度是零。