Lesson 0413 · 最小生成树：Kruskal / Prim

④ 数据结构与算法 — 第 13 课

上节课：最短路 —— 从一个点出发，到别的点「最近要多远」。负权会把 Dijkstra 弄坏，于是有了 Bellman-Ford / SPFA / Floyd。
这节课：换一个问题 —— 要把所有点连起来，最少花多少。这不需要方向、不怕负权，只需要两样你已经学过的东西：排序（0407）和并查集（0410）。如果说最短路是「一张地图上怎么走最省」，那最小生成树就是「怎么修路最省」。

三句话速览

生成树 = 用 n−1 条边把所有点连通的方案；最小生成树 = 这些方案里总权最小的。
Kruskal：把所有边按权从小到大试，能连就连（并查集判环），凑够 n−1 条就停。
Prim：从任意点出发，每次把「离已选集合最近的点」拉进来 —— 和 Dijkstra 只差一行。

1. 先把问题说清楚

给一张无向连通图，每条边有个权（修路造价）。要选出若干条边，使得：

所有点都连通（任意两点之间都能走通）
选出的边尽可能少（多选一条就多花钱）

满足第一条时，最少需要 n-1 条边（少一条就至少有两点断开；多一条就会形成环）。这 n-1 条边构成的图形就叫生成树。在所有生成树里，总权最小的那个就是最小生成树（MST, Minimum Spanning Tree）。

一个与你直觉相反的事实：MST 不怕负权边。
最短路遇到负权会崩，但 MST 遇到负权只会更愿意选它 —— 因为「负的造价」意味着修这段路还倒赚。原因很简单：MST 的两种算法本质都是「按权排序，从小到大试」，权是正是负都不影响这套逻辑。
同样地，MST 也不怕环（最短路怕负环）。因为生成树本身就不能有环，算法会在成环时自动跳过。

2. Kruskal：把边排个序，能连就连

思路只有三步：

把所有边按权从小到大排序。
依次看每条边：如果它的两个端点**还不连通**，就选它（并查集判断）；否则跳过（会成环）。
选够 n-1 条就停，加起来就是答案。

为什么「不连通就选」是对的？直观解释：每次选的都是「当前能把两块连起来的最便宜的边」。如果不用它，就必须用一条更贵（或同样贵）的边来代替，所以用了不会更差。这条论述的正式版本叫割性质，下面第 3 节会写。

用样例走一遍

样例就是这个图（4 个点、5 条边）：

按权排序后依次处理：

顺序	边	权	两端连通吗	动作	累计
1	1–2	2	不连通	选它，{1,2}	2
2	1–3	2	不连通	选它，{1,2,3}	4
3	1–4	3	不连通	选它，{1,2,3,4}	7
已经选满 n−1 = 3 条边，停止					7

注意第 4、5 条边（3–4 权 3、2–3 权 4）根本没看 —— 因为已经凑够 3 条边了。

代码

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

struct DSU {                       // 0410 那套并查集
    vector<int> fa;
    DSU(int n) : fa(n + 1) { iota(fa.begin(), fa.end(), 0); }
    int find(int x) {
        while (fa[x] != x) { fa[x] = fa[fa[x]]; x = fa[x]; }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;  // 已经同根 → 这条边会成环
        fa[a] = b;
        return true;
    }
};

struct Edge { int u, v, w; };

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<Edge> es(m);
    for (auto& e : es) cin >> e.u >> e.v >> e.w;
    sort(es.begin(), es.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });

    DSU d(n);
    long long sum = 0; int used = 0;
    for (auto& e : es) {
        if (d.unite(e.u, e.v)) {
            sum += e.w;
            if (++used == n - 1) break;   // 选满就走
        }
    }
    if (used == n - 1) cout << sum << '\n';
    else cout << "orz\n";                 // 不连通
}

复杂度：排序 O(m log m) + 并查集 O(m α(n)) → O(m log m)，瓶颈在排序。

3. 为什么「能连就连」一定得到最小值

只讲一句核心，用反证：

割性质：把点任意分成两堆（A 和 B），横跨这两堆的所有边里最便宜的那条，一定属于某棵最小生成树。

证明：假设最便宜的那条边 e 不在某棵 MST 里。把 e 加进去，树上就出现一个环；这个环必然还有另一条边 f 也横跨 A、B（要成环就得从 A 出去再回 A）。把 f 换成 e，总权不会变大（因为 e 是最便宜的），所以仍然是最小生成树。

Kruskal 每次选边时，「已选点集」和「未选点集」就构成一个割，而它挑的正是这个割上当前最便宜的边 —— 所以每一步都安全。

Prim 用同一个道理：它的割是「已选集合」和「其余」，每次把跨这个割最便宜的边拉进来，所以也对。两个算法共享同一个正确性来源，只是组织方式不同。

4. Prim：和 Dijkstra 只差一行

把 0411 的 Dijkstra 拿来，改两个地方：

	Dijkstra（0411）	Prim（本节）
`dis[v]` 表示	起点到 v 的最短距离	已选集合到 v 的最短边权
什么时候更新 `dis[v]`	`dis[u] + w < dis[v]`	`w < dis[v]`（不加 `dis[u]`）
答案怎么算	输出每个点的 `dis`	把每次拉进来的点的 `dis` 累加
能不能有负权	不能	能

就这一处差别（dis[u] + w 变成 w），整个算法的行为就从「求最短路径」变成了「求最小生成树」。

long long prim(int n, const vector<vector<pair<int,int>>>& g) {
    vector<int> dis(n + 1, INT_MAX);
    vector<bool> used(n + 1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    dis[1] = 0; pq.push({0, 1});
    long long sum = 0; int cnt = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (used[u]) continue;            // 懒删除，同 0411
        used[u] = true;
        sum += d; cnt++;                  // 这条边就是把它连进来的那条
        for (auto [v, w] : g[u])
            if (!used[v] && w < dis[v]) { dis[v] = w; pq.push({w, v}); }
    }
    return cnt == n ? sum : -1;           // -1 = 不连通
}

最容易写错的一行：dis[v] = w 而不是 dis[v] = d + w。
两者的区别就是「到起点的距离」和「到已选集合的距离」。写成 d + w 就变成 Dijkstra 了，样例上可能还能过（因为样例里恰好一样），但换个图立刻就错。

Prim 不用堆的版本（稠密图更快）

如果图很稠密（边数接近 n²），堆里的元素会非常多，这时朴素版 O(n²) 反而更快：

long long prim_dense(int n, const vector<vector<int>>& w) {
    vector<int> dis(n + 1, INT_MAX);
    vector<bool> used(n + 1, false);
    dis[1] = 0;
    long long sum = 0;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int i = 1; i <= n; i++)
            if (!used[i] && dis[i] != INT_MAX && (u == -1 || dis[i] < dis[u])) u = i;
        if (u == -1) return -1;
        used[u] = true; sum += dis[u];
        for (int v = 1; v <= n; v++)
            if (!used[v] && w[u][v] < dis[v]) dis[v] = w[u][v];
    }
    return sum;
}

结构和 0411 的朴素 Dijkstra 一模一样，只把 dis[u] + w[u][v] 换成 w[u][v]。

5. 实测：两种算法各快在哪

下面都是本机实跑（g++ 16.2.0 -O2 -std=c++17），两边答案一致才算数。

图	Kruskal	Prim（堆）	Prim（O(n²)）	MST 总权
稀疏：n = 5000、m = 200 000（P3366 上限）	10.5 ms	4.1 ms	—	762963
稠密：n = 500 完全图（m = 124 750）	7.0 ms	0.7 ms	0.7 ms	13633

结论：稀疏图 Prim（堆）略快，稠密图两种 Prim 都明显快。但差距在毫秒级，P3366 的时限下两个都能过（Kruskal 十几毫秒，离 1 秒很远）。所以选哪个更多看「写起来顺不顺手」：

Kruskal：代码短、思路直白、不用管图怎么存（只要边表）。稀疏图首选，配 0410 的并查集就是模板。
Prim：要邻接表/邻接矩阵，但天然适合稠密图，而且能顺便处理「从某个点出发」的变体。

6. P3366 专项

题面要点
N ≤ 5000、M ≤ 2×10⁵、1 ≤ Z ≤ 10⁴，无向边。如果图不连通，输出 orz（三个小写字母，不是 Impossible）—— 这是本题唯一的额外要求，也是最多人踩的坑。

完整的 Kruskal 解法就是上面第 2 节那份代码（它本来就是按 P3366 写的）。实测结果：

输入	输出	说明
样例（4 个点、5 条边）	`7`	2 + 2 + 3
`4 2 / 1 2 5 / 3 4 4`	`orz`	两个连通块，不连通
`1 0`	`0`	n = 1 时不需要任何边，答案是 0
满规模 n = 5000、m = 200 000	`745493`	耗时 94.1 ms（含读入 20 万行）

另外我用 200 组随机小图（n ≤ 7、m ≤ 10，含重边和自环）与一份「枚举所有 n−1 条边组合」的暴力对拍：Kruskal 和 Prim 都与暴力一致，0 组不一致。

卡住时的自查顺序
① 输出的是 orz 还是数值？大部分 WA 是「图不连通但没判」（used != n-1 时要输出 orz）；
② 自环（u == v）处理了吗？并查集里 find(u) == find(v) 会直接返回 false，天然跳过 —— 但如果你自己写「是否成环」的判断，容易漏；
③ 边数组开够了吗？M ≤ 2×10^5，无向边要存一条（不是两条），Kruskal 只需要边表；
④ 答案类型：n-1 条边、每条最多 10^4 → 最大约 5×10^7，int 够，但养成 long long 的习惯；
⑤ Prim 卡住：先检查你写的是 dis[v] = w 还是 dis[v] = d + w。

7. 坑点清单

不连通 → orz：Kruskal 看「选了几条边」，Prim 看「进了几个点」，都要判
n = 1：答案是 0，不是 orz（此时 n-1 = 0 条边）
Prim 的 dis 不是到起点的距离：是到「已选集合」的最短边权，写错就变 Dijkstra
Prim 的 sum += d 要在 used[u] = true 时加：加的是「把它连进来的那条边」，不是它所有出边
Kruskal 的边表只存一条（无向边不需要存两次，因为并查集是对称的）
自环会浪费一次判断，但不影响正确性（并查集直接判同根）
重边不用去重：排序后小的那条会先被选中，大的那条因为同根被跳过
MST 允许负权，不用像最短路那样筛负边

8. 小测

Q1. Kruskal 用什么判断「加这条边会不会成环」？

Q2. Prim 里 dis[v] 表示什么？

Q3. 图里有权值为负的边，最小生成树还能求吗？

Q4. P3366 里图不连通应该输出什么？

Q5. 稠密图（边数接近 n²）上，哪种写法通常更快？

9. 动手练习

P3366 【模板】最小生成树 —— 主战场。N ≤ 5000、M ≤ 2×10⁵，不连通输出 orz。建议先用 Kruskal 交一次（代码你已经有骨架了：0410 的并查集 + 0407 的排序），再用 Prim 交一次，两边的答案应该完全一样。
选做：把 Kruskal 换成 Prim —— 同一份输入跑两遍，对比答案与耗时。这一步能让你真正记住「Prim 的 dis 是到已选集合的距离」。
选做：最小生成森林 —— 如果图不连通，把每个连通块各自求一棵 MST 再加起来。这时就不输出 orz 了，改输出总和。

卡住时的自查顺序：先对一遍第 6 节那 5 条；还不行就把代码贴过来，我按行给你看 —— 按规矩，我会先让你猜「这组输入应该输出什么」。

本课小结

生成树 = n-1 条边连通所有点；最小生成树 = 总权最小的那个
Kruskal：排序 + 并查集，O(m log m)，稀疏图首选，代码最短
Prim：从任意点出发，每次拉进「离已选集合最近」的点；dis[v] = w（不是 dis[u] + w）
正确性同一个来源：割性质 —— 横跨任意割的最便宜边一定属于某棵 MST
不怕负权、不怕负环，与最短路正好相反
不连通要判：Kruskal 数边数、Prim 数点数，P3366 输出 orz
实测：稀疏 n=5000/m=2×10⁵ → Kruskal 10.5 ms、Prim 4.1 ms；稠密 n=500 → 都是 0.7 ms 级

下一课预告
0414 二分 —— 在单调的答案空间里「砍一半」。三个经典套路：二分查找（P2249）、二分答案（P1182 数列分段、P2678 跳石头），以及最关键的「怎么判断这个答案可行」。今天学的 MST 会在 P2678 那类题里变成「可行性检查」的一部分。

这一课的代码都真的编译跑过了：样例输出 7、不连通输出 orz、n=1 输出 0、满规模 94.1 ms；两种算法在 200 组随机小图上与暴力枚举一致（0 组不一致）；第 5 节的耗时是同一台机器上的实测值。哪一句看不懂 —— 比如割性质那几句、Prim 的 sum += d 为什么在那一刻加 —— 直接问我，我从零再讲一遍。

← 上一课：最短路 II：Bellman-Ford / SPFA / Floyd · 课程对照表 · 算法总结

书籍《算法 (第4版)》第 4.3 节（最小生成树）· 《算法导论》第 23 章

在线 OI-Wiki · 最小生成树 · 洛谷 P3366