最小生成树

一句话算法

最小生成树是在无向连通图里选出 $n-1$ 条边，把所有点连起来，并让总边权最小。

问题模型

给定一个 $n$ 个点、$m$ 条边的无向图，每条边有一个权值。

我们要从这些边中选出一个边集 $T$，满足：

1. 所有点连通；
2. 不出现环；
3. 边权和最小。

满足前两条的边集叫生成树。第三条要求最优，所以叫最小生成树，简称 MST。

在一个 $n$ 个点的无向连通图中，如果一个边集让所有点连通，并且恰好有 $n-1$ 条边，那么它是一棵生成树。

如果原图不连通，就不存在生成树，也就不存在最小生成树。

核心直觉

Kruskal 算法的直觉很简单：

从最便宜的边开始看，能连接两个不同连通块就选；如果会形成环，就跳过。

为什么可以这么贪心？

因为生成树只需要把不同连通块连起来。如果一条较小的边已经能完成这次连接，就没有必要先用更贵的边。

可以把过程想成修路：

• 一开始每个城市都是孤岛；
• 每次优先修当前最便宜、且能连接两个孤岛群的路；
• 如果这条路只是同一个城市群内部绕一圈，它不会让连通块变少，修了也浪费。

基本事实

最小生成树一定存在

如果图是连通图，那么至少存在一棵生成树。所有生成树的数量是有限的，每棵生成树都有一个边权和，所以其中一定有边权和最小的一棵。

这就是最小生成树。

最小生成树可能不唯一

如果图中有很多相同权值的边，可能有多棵不同的 MST。

例如一个三角形，三条边权都为 1。任意选两条边都是生成树，总权值都是 2，所以 MST 不唯一。

全局最小边

如果图中权值最小的边是唯一的，那么它一定出现在所有 MST 中。

如果最小边不唯一，那么每条最小边不一定都出现在同一棵 MST 中，但每条最小边都至少存在于某棵 MST 中。

直觉：这条边连接了某个切分的两边，并且是跨过这个切分的最便宜选择。

核心性质

Kruskal 的正确性主要靠两个性质：切分性质和环路性质。

切分性质

把点集分成两个非空部分 $S$ 和 $V-S$。所有一端在 $S$、另一端在 $V-S$ 的边叫跨切边。

如果 $e$ 是某个切分里的最小跨切边，那么存在一棵 MST 包含 $e$。

如果这个最小跨切边唯一，那么每棵 MST 都必须包含 $e$。

两块区域迟早要被某条边连起来。既然都要连，选跨区边里最便宜的那条不会吃亏。

环路性质

在任意一个环中，如果一条边 $e$ 是这个环中权值最大的边，那么存在一棵 MST 不包含 $e$。

如果 $e$ 是唯一最大边，那么任何 MST 都不会包含 $e$。

环上删掉任意一条边，剩下的点仍然连通。删最贵的那条，连通性不变，总权值不会变大。

算法步骤

Kruskal 算法：

1. 把所有边按权值从小到大排序。
2. 初始化并查集，每个点单独是一个连通块。
3. 依次扫描排序后的边 $(u,v,w)$：
   • 如果 u 和 v 已经在同一个连通块，选这条边会成环，跳过；
   • 否则选这条边，把两个连通块合并。
4. 当已经选出 $n-1$ 条边时停止。
5. 如果最后选出的边不足 $n-1$ 条，说明原图不连通。

伪代码：

sort edges by weight
answer = 0
cnt = 0

for edge in edges:
    if find(edge.u) == find(edge.v):
        continue
    merge(edge.u, edge.v)
    answer += edge.w
    cnt += 1

if cnt == n - 1:
    answer is MST cost
else:
    no spanning tree

算法证明

证明 Kruskal，最适合使用交换论证。

关键不变量

设 Kruskal 已经选出的边集为 $A$。

我们维护一个不变量：

$A$ 一定是某棵 MST 的子集。

这个不变量的含义是：当前已经选的边没有选错，后面仍然有机会补成一棵最小生成树。

初始状态

一开始 $A=\varnothing$。

空集当然是任意 MST 的子集，所以不变量成立。

选择一条新边

假设 Kruskal 下一步选择边 $e=(u,v)$。

此时 $u$ 和 $v$ 在当前森林 $A$ 的两个不同连通块中。把其中一个连通块记为 $S$，剩下点记为 $V-S$。

因为 Kruskal 按边权从小到大扫描，且之前所有能连接不同连通块的更小边都已经处理过，所以 $e$ 是当前这个切分上的最小可用跨切边。

由切分性质可知，选择 $e$ 不会破坏最优性。

所以 $A \cup \{e\}$ 仍然是某棵 MST 的子集。

跳过一条成环边

如果边 $e=(u,v)$ 的两个端点已经在同一个连通块里，那么 $A$ 中已经存在一条从 $u$ 到 $v$ 的路径。

此时加入 $e$ 会形成环。

生成树不能有环，所以 Kruskal 跳过它是必要的。

交换视角

也可以这样记：

1. 假设某棵 MST $T$ 不包含 Kruskal 想选的边 $e$。
2. 把 $e$ 加入 $T$，会形成一个环。
3. 这个环里一定有另一条边 $f$ 也跨过同一个切分。
4. 因为 $e$ 是该切分里最便宜的跨切边，所以 $w(e) \leq w(f)$。
5. 用 $e$ 替换 $f$：

替换后仍然是一棵生成树，权值不变大。因此也存在一棵 MST 包含 $e$。

这正是 Kruskal 每次“放心选最小安全边”的原因。

结论

Kruskal 每次选边都保持“不选错”的不变量；最后选出 $n-1$ 条边时，它们连通且无环，是一棵生成树。

因为这棵树仍然是某棵 MST 的子集，而它自己已经是一棵完整生成树，所以它就是 MST。

复杂度分析

设点数为 $n$，边数为 $m$。

• 排序所有边：$O(m \log m)$。
• 并查集查询和合并：$O(m \alpha(n))$，近似线性。
• 总时间复杂度：$O(m \log m)$。
• 空间复杂度：$O(n+m)$。

Kruskal 适合边列表形式的稀疏图。如果图非常稠密，也可以考虑 Prim 算法。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

        #include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

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

    bool operator<(const Edge &other) const {
        return w < other.w;
    }
};

struct DSU {
    vector<int> parent;

    explicit DSU(int n = 0) {
        init(n);
    }

    void init(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    bool merge(int a, int b) {
        int fa = find(a);
        int fb = find(b);
        if (fa == fb) return false;
        parent[fa] = fb;
        return true;
    }
};

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

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

    vector<Edge> edges(m);
    for (auto &edge : edges) {
        cin >> edge.u >> edge.v >> edge.w;
    }

    sort(edges.begin(), edges.end());

    DSU dsu(n);
    long long answer = 0;
    int selected = 0;

    for (const Edge &edge : edges) {
        if (!dsu.merge(edge.u, edge.v)) continue;
        answer += edge.w;
        selected++;
        if (selected == n - 1) break;
    }

    if (selected != n - 1) {
        cout << "orz\n";
    } else {
        cout << answer << '\n';
    }

    return 0;
}
    

这份模板的输入格式是：

n m
u1 v1 w1
u2 v2 w2
...
um vm wm

如果图不连通，输出 orz。否则输出 MST 的总权值。

测试用例

普通连通图

输入：

4 5
1 2 1
1 3 4
2 3 2
2 4 5
3 4 3

输出：

6

解释：

选边 (1,2,1)、(2,3,2)、(3,4,3)，总权值为 1+2+3=6。

不连通图

输入：

4 2
1 2 1
3 4 2

输出：

orz

解释：

图分成两个连通块，无法选出连接全部 $4$ 个点的生成树。

常见错误

忘记判断不连通

Kruskal 结束后必须检查是否选了 $n-1$ 条边。

如果少于 $n-1$ 条，说明没有生成树。

把有向图拿来求 MST

普通 MST 是无向图问题。有向图上对应的是最小树形图，不是 Kruskal 这个模板。

认为 MST 一定唯一

有相同权值边时，MST 可能不唯一。题目问“是否唯一”“方案数”时，要额外处理同权边。

认为负边不能用

MST 可以有负权边。Kruskal 只按边权排序，负边会被更早考虑。

应用分类详解

MST 的本质是：在一堆可选连接中，选出一组最便宜的连接，让所有对象成为一个整体。

一、基础连通建设

典型模式： 修路、铺电缆、建管道、连接村庄、连接网络。

识别信号： 题面出现“把所有点连通”“总费用最小”“无向边有代价”。

核心建模： 点表示对象，边表示可选连接，边权表示建设成本。

二、最小瓶颈生成树

典型模式： 不只关心总费用，还关心“选中边里的最大值尽量小”。

识别信号： “最大边最小”“瓶颈最小”“限制上限尽量小”。

核心建模： 任意一棵 MST 都是最小瓶颈生成树。Kruskal 从小边到大边选，第一次让图连通时，最大选边已经尽量小。

三、两点瓶颈路

典型模式： 查询两点之间一条路径，使路径上的最大边权尽量小。

识别信号： “从 A 到 B 的路径中，最大风险最小”“噪音上限最小”“路上最差的一段尽量好”。

核心建模： MST 上 $u$ 到 $v$ 的路径，其最大边权等于原图所有 $u \to v$ 路径里最大边权的最小可能值。

四、MST 进阶判定与替换

典型模式： 题目不满足于求一棵 MST，而是问边是否必选、能否出现、次优方案或方案数。

识别信号： “严格次小生成树”“MST 是否唯一”“某条边是否在某棵 MST 中”“有多少种 MST”。

核心建模： 围绕切分性质、环路性质和“加一条非树边形成环，再替换环上一条边”讨论。

五、离线连通与 Kruskal 思想

典型模式： 边按权值阈值逐渐开放，查询某些点是否连通。

识别信号： “只允许使用权值不超过 $x$ 的边”“随着阈值增大，连通块合并”“多次询问连通性”。

核心建模： 把边按权值排序，再用并查集从小到大加入边。这不是一定要求出 MST，但使用的是 Kruskal 的扫描思想。

经典例题

1. luogu-P3366

最小生成树模板题。直接练习 Kruskal 排序、并查集合并和不连通判断。

2. luogu-P1546

给出城市之间的连接费用，要求连通所有城市的最小花费。模型完全等价于 MST。

3. luogu-P2820

题目要求删掉多余道路后仍然连通，并让保留费用最小。可以先求总边权，再减去 MST 权值。

4. luogu-P1967

货车运输是最大生成树上的瓶颈路问题。它和 MST 的瓶颈思想同源，只是为了最大化最小承重，需要按边权从大到小建最大生成树。

参考

• Kruskal
• 最小生成树常用性质
• 严格次小生成树
• 瓶颈路