算法讲解061 必备 最小生成树

来源：算法讲解061【必备】最小生成树　·　2026-10-26

依据：视频字幕 2000 字

一句话概括

最小生成树（Minimum Spanning Tree, MST）是在连通无向带权图中选出 N−1 条边使所有点连通且总权值最小的树；Kruskal 算法按边权从小到大加边、用并查集判环，Prim 算法从一点出发用小根堆不断扩展。

它解决什么问题

给一张连通的无向带权图（N 个点、M 条边），要求选出一个边集：

• 所有点连通；
• 恰好 N−1 条边（无环）；
• 边权总和最小。

输出通常只要这个最小总权值；有时也要求输出选了哪些边。典型场景：修路/铺网线/建电网，要求花最少钱把所有城市连起来。

基础知识（前置概念，用大白话解释）

• 无向带权图（undirected weighted graph）：边没有方向，每条边有一个代价。MST 只对无向图定义；有向图对应的是「最小树形图（arborescence）」，是另一个问题。
• 连通（connected）：任意两点之间都有路径。图不连通时不存在生成树，MST 也无从谈起（此时只能求「最小生成森林」）。
• 树（tree）：连通且无环的图。N 个点的树恰好有 N−1 条边；少一条必不连通，多一条必有环。
• 生成树（spanning tree）：包含全部 N 个点、由原图若干边组成的一棵树。
• 环（cycle）：一条首尾相同的路径。在无向图里，往一棵树里加一条两端已连通的边，就会形成环。
• 并查集（Disjoint Set Union, DSU）：维护「哪些点已经属于同一个连通块」。支持两个操作：find(x) 查 x 所在集合的代表元；union(a,b) 合并两个集合。加边前查两端是否同集合，同集合就说明加这条边会成环。
• 小根堆（min-heap / priority_queue）：每次能 O(log n) 取出当前最小元素。Prim 用它维护「从已选点集连出去的最小边」。

原理（为什么这么做是对的，尽量给直觉）

Kruskal 的直觉（贪心 + 割性质）：把边按权值从小到大看。当前这条边 (u,v,w)，如果 u、v 已经连通，加它必然成环，扔掉；如果不连通，就加它。

为什么加它不会亏？设当前 u 在一个连通块 A 里、v 在另一个连通块 B 里。任何一棵生成树都必须至少有一条边跨过 A 和 B 之间（否则 A、B 不连通）。而 w 是所有还没考虑的边里最小的，也就是所有跨 A、B 的边里最小的（更小的边要么已经加过、要么会成环被扔，都不跨 A、B）。所以一定存在一棵 MST 包含这条边——这就是「割性质（cut property）」。每次加边都保持「存在一棵 MST 包含已选边集」这个不变式，加满 N−1 条就得到 MST。

Prim 的直觉：从任意点出发，维护「已选点集 S」和「S 到外部的最小边」。每次取这条最小边把外部点拉进 S。同样由割性质保证正确：S 与外部之间的最小边一定属于某棵 MST。

两者关系：都是贪心 + 割性质，只是「扩展方式」不同——Kruskal 按全局边权扩展（需要并查集判环），Prim 按点集边界扩展（需要堆取最小边）。

步骤（编号，可照着写）

Kruskal

1. 读入 N、M 和所有边 (u, v, w)，存进数组（不用建邻接表）。
2. 把所有边按 w 升序排序。
3. 初始化并查集，每个点自成一个集合；计数器 cnt = 0，答案 ans = 0。
4. 依次遍历排序后的边：

- 若 find(u) != find(v)：union(u,v)，ans += w，cnt++；

- 若 cnt == N-1：提前结束。

1. 若结束时 cnt < N-1，说明图不连通，无 MST；否则 ans 就是最小总权值。

Prim（堆优化）

1. 建邻接表 vector<vector<pair<int,int>>> g(N+1)，存 (邻点, 边权)。
2. dist[] 全部初始化为 INF，vis[] 全 false；dist[1] = 0。
3. 小根堆放 (0, 1)（(距离, 点)）。
4. 循环直到堆空或已选 N 个点：

- 弹出 (d, u)；若 vis[u] 跳过（懒删除）；

- vis[u] = true，ans += d，cnt++；

- 遍历 u 的邻边 (v, w)：若 !vis[v] && w < dist[v]，更新 dist[v] = w，push (w, v)。

1. cnt == N 则有 MST，否则不连通。

样例（一个具体小例子，带每步变化）

N = 5，边（按权值已排好序）：

(1,2,1)  (3,4,1)  (2,3,3)  (1,3,4)  (2,4,6)  (4,5,7)

Kruskal 过程：

| 步 | 边 | 两端是否已连通 | 动作 | 已选边数 | ans |

|---|---|---|---|---|---|

| 1 | (1,2,1) | 否 | 加 | 1 | 1 |

| 2 | (3,4,1) | 否 | 加 | 2 | 2 |

| 3 | (2,3,3) | 否（{1,2} 与 {3,4}） | 加 | 3 | 5 |

| 4 | (1,3,4) | 是（1、3 已同块） | 跳过 | 3 | 5 |

| 5 | (2,4,6) | 是 | 跳过 | 3 | 5 |

| 6 | (4,5,7) | 否 | 加 | 4 = N−1 | 12 |

结束，MST 总权值 = 12，选边 {(1,2),(3,4),(2,3),(4,5)}。

注意：若把 (2,3,3) 换成 (1,3,3)，同样得到权值 12 的另一棵 MST——MST 不唯一，但最小总权值唯一。

代码

Python（好读，用于理解）

import sys

def solve():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    edges = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        edges.append((w, u, v))
    edges.sort()                       # 按权值升序

    parent = list(range(n + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]   # 路径压缩
            x = parent[x]
        return x

    ans, cnt = 0, 0
    for w, u, v in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            ans += w
            cnt += 1
            if cnt == n - 1:
                break
    print(ans if cnt == n - 1 else "orz")   # 不连通时按题目要求输出

solve()

C++（竞赛风，可直接抄）

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

struct DSU {
    vector<int> fa, sz;
    DSU(int n) : fa(n + 1), sz(n + 1, 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;
        if (sz[a] < sz[b]) swap(a, b);
        fa[b] = a; sz[a] += sz[b];
        return true;
    }
};

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

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

    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (auto &e : edges) cin >> e.u >> e.v >> e.w;

    sort(edges.begin(), edges.end(),
         [](const Edge &a, const Edge &b) { return a.w < b.w; });

    DSU dsu(n);
    long long ans = 0;
    int cnt = 0;
    for (auto &e : edges) {
        if (dsu.unite(e.u, e.v)) {
            ans += e.w;
            if (++cnt == n - 1) break;
        }
    }
    if (cnt == n - 1) cout << ans << '\n';
    else cout << "orz\n";   // 图不连通，按题目要求输出
    return 0;
}

复杂度（时间/空间，最好/平均/最坏，顺带说常数大不大）

Kruskal

• 时间：排序 O(M log M) 是瓶颈；并查集部分 O(M α(N))，α 近似常数。总 O(M log M)，最好/最坏一样。
• 空间：O(M + N)（存边 + 并查集）。
• 常数：很小。不建图、只存边数组，1e6 条边轻松过。稀疏图首选。

Prim（堆优化）

• 时间：O((N + M) log M)，每条边最多进堆一次。稠密图 M ≈ N² 时退化到 O(N² log N)，不如朴素 O(N²) Prim。
• 空间：O(N + M)（邻接表 + 堆）。
• 常数：比 Kruskal 大（堆操作多）。稠密图或必须建图时用。

竞赛里什么时候用（看到什么题面特征就该想到它）

• 「用最少花费把所有城市/点连通」「铺路/架线/建站，要求总代价最小」——直接 MST。
• 「N 个点 M 条边，删掉一些边使总权值最小且仍连通」——等价于求 MST 的补集。
• 「求最小生成森林」——图不连通时对每个连通块各跑一次 Kruskal（不用判 cnt == N−1）。
• 「次小生成树」「最小瓶颈生成树」「最大边最小的生成树」——MST 的变形（见「同类题」）。
• 「边权是两点距离（曼哈顿/欧氏）」——可能是最小生成树 + 特殊建图（如 Manhattan MST）。
• 看到 N ≤ 1e5、M ≤ 2e5 的连通性 + 最小代价，先想 Kruskal。

竞赛模板（C++，可直接背下来的写法；变量名清楚）

// Kruskal + 并查集，适用于 N ≤ 2e6, M ≤ 2e6
struct DSU {
    vector<int> fa, sz;
    DSU(int n) : fa(n + 1), sz(n + 1, 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;
        if (sz[a] < sz[b]) swap(a, b);
        fa[b] = a; sz[a] += sz[b];
        return true;
    }
};

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

long long kruskal(int n, vector<Edge> &edges) {   // 返回 -1 表示不连通
    sort(edges.begin(), edges.end(),
         [](const Edge &a, const Edge &b) { return a.w < b.w; });
    DSU dsu(n);
    long long ans = 0;
    int cnt = 0;
    for (auto &e : edges) {
        if (dsu.unite(e.u, e.v)) {
            ans += e.w;
            if (++cnt == n - 1) return ans;
        }
    }
    return -1;
}

// Prim 堆优化，适用于稠密图 / 需要邻接表的场景
long long prim(int n, vector<vector<pair<int,long long>>> &g) {  // 1-indexed
    const long long INF = LLONG_MAX / 2;
    vector<long long> dist(n + 1, INF);
    vector<char> vis(n + 1, 0);
    priority_queue<pair<long long,int>, vector<pair<long long,int>>,
                   greater<pair<long long,int>>> pq;
    dist[1] = 0; pq.push({0, 1});
    long long ans = 0; int cnt = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = 1; ans += d; cnt++;
        for (auto [v, w] : g[u])
            if (!vis[v] && w < dist[v]) { dist[v] = w; pq.push({w, v}); }
    }
    return cnt == n ? ans : -1;
}

边界与易错点（WA 的常见原因，越具体越好）

1. 图不连通：Kruskal 结束时 cnt < N-1，不能直接输出 ans，要按题目要求输出 orz / -1 / impossible。多测时尤其容易忘。
2. 多测清空：edges、并查集、vis、dist 每轮都要重置。用局部变量 + 重新构造最省心。
3. long long：边权总和可能爆 int（M 条边 × 每条 1e9 ≈ 1e15）。ans 用 long long，边权也建议 long long。
4. 下标从 0 还是 1：并查集 fa 大小开 n+1 且 iota 从 0 开始，1-indexed 输入直接用；0-indexed 输入要保证 fa 大小 ≥ n。
5. 重边/自环：自环 u == v 在 Kruskal 里 find 相等自动跳过，没问题；重边排序后正常处理，不影响正确性。
6. N = 1：MST 是空集，权值 0。Kruskal 里 cnt == 0 == N-1 直接返回 0，注意别写成 cnt == N-1 之前就 break 出错。
7. 排序比较器：用 <= 当比较器会 UB（严格弱序要求），必须用 <。
8. Prim 的懒删除：弹出时 vis[u] 为真必须 continue，否则重复加点。
9. Prim 的 dist 初值：INF 别用 INT_MAX，加法会溢出；用 LLONG_MAX/2 或 0x3f3f3f3f3f3f3f3f。
10. 提前 break 的条件：cnt == N-1 要在加边之后判断，别在加边前判断。

同类题 / 变形（说清楚怎么改）

• 最小生成森林：图不连通时，去掉 cnt == N-1 的 break 和最终判连通，直接跑完所有边，答案就是各连通块 MST 之和。
• 最大生成树：边权取负，或排序改成降序，其余不变。
• 次小生成树（严格/非严格）：先求 MST，再枚举每条非树边 (u,v,w)，用它替换 MST 上 u→v 路径上的最大边（严格次小要替换严格小于 w 的最大边）。需要 LCA + 倍增维护路径最大/次大边。
• 最小瓶颈生成树：使最大边权最小。MST 就是最小瓶颈生成树，直接求 MST 后输出最大边即可。
• 最小树形图（有向图）：不是 MST，用朱刘算法（Chu-Liu/Edmonds）。
• MST 计数：相同权值的边分组，每组内用矩阵树定理或并查集缩点后计数，再乘起来。
• 带必选边/禁选边：必选边先 union 并计入答案，再跑 Kruskal；禁选边直接跳过。
• 动态 MST：加边/删边，用 Link-Cut Tree 维护，属于高级内容。

常见坑

• 把 MST 当成「最短路树」——两者完全不同，MST 不保证任意两点路径最短。
• 以为 MST 唯一——只有所有边权互不相同时才唯一；权值相同时可能有多棵，但最小总权值唯一。
• Kruskal 里用 map 或 set 存边——常数爆炸，1e6 规模必 TLE，用 vector + sort。
• Prim 用 priority_queue 但忘了 greater，默认是大根堆，结果全错。
• 多测时 edges.clear() 但没 shrink_to_fit，内存反复分配；更好的做法是每轮重新声明局部 vector。
• 边权读入用 int，累加用 int——1e5 条边 × 1e9 直接溢出。

拓展（变体、实际用途、面试常问）

• 实际用途：网络布线、电路设计、聚类（单链接聚类）、图像分割、近似旅行商问题（TSP 的 2-近似基于 MST）。
• Boruvka 算法：每轮每个连通块找最小出边合并，O(M log N)，适合并行/分布式，也是某些特殊图（如 Manhattan MST）的基础。
• 面试常问：Kruskal 和 Prim 的区别与适用场景；为什么贪心是对的（割性质）；如何判断 MST 唯一；如何求次小生成树。
• MST 与拟阵（matroid）：MST 是拟阵上贪心的一个特例，这是贪心正确性的更抽象解释。

自测 3 题（题目 + 折叠答案）

题 1：N=4，边 (1,2,1)、(2,3,2)、(3,4,3)、(1,4,10)、(1,3,5)。求 MST 总权值。