06 拓扑排序与 DAG DP

userId_undefined
吴老师
7月全勤卷王8月全勤卷王10月全勤卷王倔强青铜时间刺客空间掌握者

2026-06-30 18:55:39

发布于：广东

4阅读
0回复
0点赞

06 拓扑排序与 DAG DP

一、本阶段目标

学完本阶段，学生要能做到：

1. 理解有向无环图 DAG。
2. 理解入度和拓扑序。
3. 会用拓扑排序处理依赖关系。
4. 会判断有向图是否存在环。
5. 会在拓扑序上做简单 DP。

二、什么是拓扑排序

拓扑排序用于有向图。

如果有一条边：

u -> v

表示：

u 必须在 v 前面

拓扑排序就是找一个排列，使得每条边的起点都在终点前面。

常见题面：

课程先修
任务依赖
工程流程
家族辈分
食物链关系
生产顺序

三、入度

入度表示有多少条边指向这个点。

indeg[v] = 指向 v 的边数

如果一个点入度为 0，说明：

没有任何前置条件，可以先做。

四、拓扑排序思想

1. 把所有入度为 0 的点加入队列。
2. 每次取出一个点 u，加入拓扑序。
3. 删除 u 发出的所有边，也就是让相邻点入度减 1。
4. 如果某个点入度变成 0，加入队列。
5. 最后如果取出的点数等于 n，说明无环；否则有环。

五、拓扑排序模板

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

const int N = 100005;
vector<int> g[N];
int indeg[N];
vector<int> topo;

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        indeg[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);

        for (int v : g[u]) {
            indeg[v]--;
            if (indeg[v] == 0) q.push(v);
        }
    }

    if ((int)topo.size() == n) {
        for (int x : topo) cout << x << ' ';
    } else {
        cout << "There is a cycle\n";
    }

    return 0;
}

六、为什么可以判断有环

如果图中有环：

A -> B -> C -> A

那么 A、B、C 每个点都至少有一个前驱在环里。

它们的入度不可能被完全删成 0。

所以拓扑排序最后取不完所有点。

反过来，如果能取完所有点，说明不存在这样的循环依赖。

七、拓扑序不一定唯一

如果同时有多个入度为 0 的点，可以任选一个。

所以拓扑序可能有很多种。

如果题目要求字典序最小，可以把 queue 换成 priority_queue：

priority_queue<int, vector<int>, greater<int>> q;

八、DAG 上 DP

DAG 是有向无环图。

因为没有环，所以可以按拓扑序做 DP。

例如：求从起点到每个点的最长路径。

for (int u : topo) {
    for (int v : g[u]) {
        dp[v] = max(dp[v], dp[u] + 1);
    }
}

拓扑序保证：

处理 v 之前，所有可能影响 v 的前驱都已经处理完。

九、任务完成时间模型

题意：有 n 个任务，每个任务有耗时。有些任务必须在另一些任务之前完成。问最早什么时候全部完成。

建模：

点：任务
边：u -> v 表示 u 完成后才能做 v
点权：任务耗时
DP：finish[v] = max(finish[v], finish[u] + time[v])

初始化：

如果任务没有前置任务，则 finish[i] = time[i]

转移：

for (int u : topo) {
    for (int v : g[u]) {
        finish[v] = max(finish[v], finish[u] + cost[v]);
    }
}

答案：

max(finish[i])

十、食物链计数模型

有向边表示“被吃 → 吃它的生物”或“生产者 → 消费者”。

如果要统计从源点到汇点的路径条数，可以在拓扑序上 DP。

for (int u : topo) {
    for (int v : g[u]) {
        dp[v] += dp[u];
        dp[v] %= MOD;
    }
}

关键是先确定边的方向。

十一、拓扑排序常见错误

错误 后果 修正
边方向建反 顺序完全错误 明确 u 是前置还是后置
忘记统计入度 队列初始化错误 加边时 indeg[v]++
多组数据不清空 入度残留 清空 g、indeg、topo
用拓扑处理无向图 没有意义 拓扑排序只用于有向图
有环还做 DAG DP 答案无定义 先判断拓扑序长度

十二、课堂例题

例题 1：课程安排

有些课程必须先修，问能否学完全部课程。

点：课程
边：先修课 -> 后续课
算法：拓扑排序
判断：能否取出 n 个点

例题 2：家谱排序

长辈必须排在晚辈前面。

点：人
边：长辈 -> 晚辈
答案：任意拓扑序

例题 3：任务最早完成时间

点：任务
边：前置任务 -> 后置任务
DP：最早完成时间

十三、练习题

题号 题名 训练点 建议
B3644 拓扑排序 / 家谱树 拓扑排序模板 必做
P4017 最大食物链计数 拓扑 + 路径计数 必做
P1113 杂务 拓扑 + 最早完成时间 必做
P1137 旅行计划 DAG 最长路 提高
P1347 排序 拓扑三种情况 提高
P1038 神经网络 拓扑建模 提高

链接：

https://www.luogu.com.cn/problem/B3644
https://www.luogu.com.cn/problem/P4017
https://www.luogu.com.cn/problem/P1113
https://www.luogu.com.cn/problem/P1137
https://www.luogu.com.cn/problem/P1347
https://www.luogu.com.cn/problem/P1038

十四、本阶段作业

  1. 手写拓扑排序模板。
  2. 解释入度为 0 的含义。
  3. 完成 B3644。
  4. 完成 P4017，并写出 DP 数组含义。
  5. 完成 P1113，训练“点权 + 拓扑 DP”。

十五、本阶段小结

拓扑排序关键词：

有向图
先后关系
入度
无环
依赖
任务顺序
DAG DP

看到“必须先……才能……”就要想到拓扑排序。

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论