最小生成树

一句话算法

边从小到大看，能连两块就选，块内的边跳过；选够 $n-1$ 条，就是最小生成树。

问题模型

给定一个 $n$ 个点、$m$ 条边的无向图，每条边有一个权值，$n\geqslant 1$。本文用 Kruskal 算法求最小生成树。

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

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

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

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

边权可以为负，可以有重边和自环。重边作为不同候选边处理，自环永远不能选进生成树。只有一个点时，空边集就是生成树，权值和为 $0$。

这里要求选出一棵树。若题目只要求连通、允许保留环，负权边可能使保留更多边更划算，此时不能直接用 MST 代替题目目标。

核心直觉

Kruskal 算法的直觉很简单：

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

为什么可以这么贪心？

假设当前已经连成了几块。每块内部的点可以互相到达，要把整个图连通，迟早还得选边走出这块。当前扫描到的最轻跨块边，正是这样一次连接的候选。

但“便宜”本身还不是证明：会不会现在选了它，反而妨碍后面的安排？我们需要证明，总能找到一棵最优树，同时保留之前选的边和现在这条边。后面的交换论证会补上这一环。

可以把过程想成修路：

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

基本事实

最小生成树一定存在

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

这就是最小生成树。

最小生成树可能不唯一

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

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

全局最小边

以下只考虑非自环边。如果图中权值最小的非自环边是唯一的，那么它一定出现在所有 MST 中。

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

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

核心性质

以下性质都以无向连通图为前提。切分性质解释何时可以选边，环路性质解释何时可以舍边。

切分性质

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

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

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

换边理由： 任取一棵 MST。若它没有 $e$，加入 $e$ 后形成的环中，必有另一条跨切边 $f$。以 $e$ 换掉 $f$ 仍然是一棵树，且 $w(e)\leqslant w(f)$，总权值不增。若 $e$ 是唯一最轻跨切边，则 $w(e)<w(f)$，原树就不可能最优。

环路性质

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

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

换边理由： 若一棵 MST 包含 $e$，删掉 $e$ 后分成两块。原环去掉 $e$ 的那条路仍连接 $e$ 的两端，因此路上有一条边 $f$ 跨过这两块。用 $f$ 接回去，由 $w(f)\leqslant w(e)$ 可知总权值不增；若 $e$ 唯一最重，权值会严格下降，产生矛盾。

同权时要区分“存在一棵”和“每一棵”：某条边可以舍弃，不代表它不属于任何 MST。例如等权三角形中，每条边都能出现在某棵 MST 中，也都能被另一棵 MST 舍弃。

算法步骤

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

手动走一遍

四个点的边按权值排好后如下。每次成功合并，连通块数恰好减一。

并查集维护的是什么

并查集维护的是已选边形成的连通块。merge(u, v) 先判断两端是否属于同一块，只有真正合并两块才返回 true，此时累加权值并增加选边数。

并查集里的父子指针只是集合的内部表示，并不是 MST 的边。如果后续要在 MST 上查询路径，应在成功合并时另外保存原边 (u,v,w)，再用这些边建树。

算法证明

记住一个动作：把想选的边放进最优树，成环后换掉一条不更便宜、且不属于已选集合的边。

关键不变量： Kruskal 已经选出的边，总能被扩展成某棵 MST。

初始时没有选边，显然可以扩展成 MST。

设当前已选边集为 $F$，根据不变量，存在一棵包含 $F$ 的 MST，记为 $T$。现在准备选择边 $e=(u,v)$，其中 $u$ 和 $v$ 属于不同连通块。

令 $S$ 为 $F$ 中包含 $u$ 的连通块。$e$ 跨过切分 $(S,V-S)$，而且是跨过这个切分的最小权边：如果有更轻的跨区边，它早已被扫描并合并两端，两个端点就不可能到现在仍分处切分两侧。

如果 $e$ 已在 $T$ 中，直接选择它即可。否则，在 $T$ 中加入 $e$ 会形成一个环。环上原有的 $u$ 到 $v$ 路径必然有一条边 $f$ 跨过这个切分；由于 $F$ 没有边跨过自己的连通块，$f$ 不属于 $F$。

删去 $f$，得到新的生成树 $T'=T-f+e$。由 $w(e)\leqslant w(f)$，有：

$T$ 已经是 MST，所以 $T'$ 也只能是 MST；它保留了 $F$ 的全部边，又包含 $e$。因此，选择 $e$ 后，不变量仍然成立。

如果扫描到一条连接同一连通块的边，跳过它不改变 $F$，不变量也保持成立。

原图连通时，扫描结束后不可能还剩两个连通块，否则原图中连接这些块的边在被扫描时就会将它们合并。因此最终选出 $n-1$ 条边，构成一棵生成树；又因为它能被扩展成 MST，它自身就是 MST。

复杂度分析

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

• 初始化并查集：$O(n)$。
• 排序所有边：$O(m \log(m+1))$，这样也覆盖无边图。
• 并查集查询和合并：$O(m \alpha(n))$，近似线性。
• 总时间复杂度：$O(n+m\log(m+1)+m\alpha(n))$。连通且 $n\geqslant 2$ 时，通常简写为 $O(m\log m)$。
• 空间复杂度：$O(n+m)$。

上述并查集复杂度使用了路径压缩与按大小合并两种优化，下面的两份模板都包含它们。

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

代码模板

点编号为 1..n。C++ 版 kruskal(n, edges, answer) 用返回值表示图是否连通：返回 true 时 answer 是 MST 总权值，返回 false 表示没有生成树；Python 版 kruskal(n, edges) 不连通时返回 None。两份模板都不会打乱调用者原来的边表顺序：C++ 按值接收边表，Python 用 sorted 生成新列表。

        
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

        #include <algorithm>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;

// 一条无向边：从 u 连到 v，边权 w。点编号 1..n，n >= 1。
// 点编号要当数组下标用，写成 int；边权和可能很大，用 ll。
struct Edge {
    int u;  // 起点
    int v;  // 终点
    ll w;   // 边权
};

// 边权小的排在前面，Kruskal 每次都先试当前最小的边。
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(vector<int> &dsu_parent, int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent, dsu_parent[x]);
    return dsu_parent[x];
}

// 合并 a、b 所在的两个集合；两端本来就连通时返回 false。
// dsu_size[x] 是 x 当根时该集合的点数，用来按大小合并。
bool dsu_merge(vector<int> &dsu_parent, vector<int> &dsu_size, int a, int b) {
    int root_a = dsu_find(dsu_parent, a);
    int root_b = dsu_find(dsu_parent, b);
    if (root_a == root_b) return false;
    // 小集合接到大集合下面，配合路径压缩，单次操作接近常数。
    if (dsu_size[root_a] < dsu_size[root_b]) swap(root_a, root_b);
    dsu_parent[root_b] = root_a;
    dsu_size[root_a] += dsu_size[root_b];
    return true;
}

// 求最小生成树，按值接收边表，排序不会打乱调用者的边表顺序。
// 返回 true：图连通，answer 存 MST 的总权值；
// 返回 false：图不连通，没有生成树，answer 无意义。
bool kruskal(int n, vector<Edge> edges, ll &answer) {
    sort(edges.begin(), edges.end(), cmp_edge);

    // 并查集要跟着 n 开，放在函数里比固定大小的全局数组安全。
    vector<int> dsu_parent(n + 1);   // dsu_parent[x]：x 的父节点，x 是根时等于 x
    vector<int> dsu_size(n + 1, 1);  // dsu_size[x]：x 是根时集合的大小
    for (int i = 1; i <= n; i++) dsu_parent[i] = i;

    answer = 0;
    int selected = 0;  // 已选边数，一棵生成树正好要 n - 1 条

    for (const Edge &edge : edges) {
        // 自环、两端已经连通的边都会成环，不能选。
        if (!dsu_merge(dsu_parent, dsu_size, edge.u, edge.v)) continue;
        answer += edge.w;
        selected++;
        if (selected == n - 1) break;
    }

    return selected == n - 1;  // 单点图选 0 条边：连通，答案为 0
}
    

        
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

        # Kruskal 最小生成树：点编号 1..n（单点图也成立），边表是 (u, v, w) 三元组。
# kruskal 返回 MST 总权值；图不连通时返回 None。
# 并查集用路径压缩 + 按大小合并，复杂度 O(m log m + m α(n))。

type Edge = tuple[int, int, int]  # (起点 u, 终点 v, 边权 w)


def find(parent: list[int], x: int) -> int:
    """找 x 所在集合的根，顺路把路径上的点挂到根上（迭代压缩，不受递归深度限制）。"""
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root


def kruskal(n: int, edges: list[Edge]) -> int | None:
    """返回 MST 总权值，图不连通时返回 None；sorted 生成新列表，不打乱调用者的边表。"""
    parent = list(range(n + 1))  # parent[x]：x 的父节点，x 是根时等于 x
    size = [1] * (n + 1)         # size[x]：x 是根时该集合的点数

    total = selected = 0
    for u, v, w in sorted(edges, key=lambda edge: edge[2]):  # 边权小的先试
        root_u, root_v = find(parent, u), find(parent, v)
        if root_u == root_v:  # 两端已经连通，选它就会成环
            continue
        if size[root_u] < size[root_v]:  # 小集合接到大集合下面
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        total += w
        selected += 1
        if selected == n - 1:  # 生成树正好 n - 1 条边，选满就停
            break
    return total if selected == n - 1 else None
    

代码实现

下面是可直接运行的完整程序。C++ 使用 C++17，边权和用 long long 保存；Python 使用 Python 3.12 或更新版本（模板里的 type Edge = ... 是 3.12 起才有的类型别名语句）。

        
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
76
77
78
79
80
81
82
83
84
85
86
87

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

typedef long long ll;

// 一条无向边：从 u 连到 v，边权 w。点编号 1..n。
// 点编号要当数组下标用，写成 int；边权和可能很大，用 ll。
struct Edge {
    int u;  // 起点
    int v;  // 终点
    ll w;   // 边权
};

vector<Edge> edge_list;  // 边表，读入后按边权升序排序再扫描
vector<int> dsu_parent;  // dsu_parent[x]：x 的父节点，x 是根时等于 x
vector<int> dsu_size;    // dsu_size[x]：x 是根时集合的大小，用来按大小合并
int n;                   // 点数
int m;                   // 边数

// 边权小的排在前面，Kruskal 每次都先试当前最小的边。
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

void dsu_init(int n) {
    dsu_parent.resize(n + 1);
    dsu_size.assign(n + 1, 1);
    for (int i = 1; i <= n; i++) dsu_parent[i] = i;
}

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent[x]);
    return dsu_parent[x];
}

// 合并 a、b 所在的两个集合；两端本来就连通时返回 false。
bool dsu_merge(int a, int b) {
    int root_a = dsu_find(a);
    int root_b = dsu_find(b);
    if (root_a == root_b) return false;
    // 小集合接到大集合下面，配合路径压缩，单次操作接近常数。
    if (dsu_size[root_a] < dsu_size[root_b]) swap(root_a, root_b);
    dsu_parent[root_b] = root_a;
    dsu_size[root_a] += dsu_size[root_b];
    return true;
}

void read_input() {
    cin >> n >> m;
    edge_list.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> edge_list[i].u >> edge_list[i].v >> edge_list[i].w;
    }
}

void solve() {
    sort(edge_list.begin(), edge_list.end(), cmp_edge);
    dsu_init(n);

    ll answer = 0;     // 已选边的边权和
    int selected = 0;  // 已选边数，一棵生成树正好要 n - 1 条

    for (int i = 0; i < m && selected < n - 1; i++) {
        // 自环、两端已经连通的边都会成环，不能选。
        if (!dsu_merge(edge_list[i].u, edge_list[i].v)) continue;
        answer += edge_list[i].w;
        selected++;
    }

    // 选不满 n - 1 条边说明图不连通，没有生成树。
    if (selected != n - 1) cout << "orz" << '\n';
    else cout << answer << '\n';  // 单点图选 0 条边：答案为 0
}

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

    read_input();
    solve();

    return 0;
}
    

        
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

        # 完整程序：读入 n、m 和 m 条无向边，输出 MST 总权值；图不连通时输出 orz。
import sys

type Edge = tuple[int, int, int]  # (起点 u, 终点 v, 边权 w)


def find(parent: list[int], x: int) -> int:
    """找 x 所在集合的根，顺路把路径上的点挂到根上（迭代压缩，不受递归深度限制）。"""
    root = x
    while parent[root] != root:
        root = parent[root]
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root


def kruskal(n: int, edges: list[Edge]) -> int | None:
    """返回 MST 总权值，图不连通时返回 None；sorted 生成新列表，不打乱调用者的边表。"""
    parent = list(range(n + 1))  # parent[x]：x 的父节点，x 是根时等于 x
    size = [1] * (n + 1)         # size[x]：x 是根时该集合的点数

    total = selected = 0
    for u, v, w in sorted(edges, key=lambda edge: edge[2]):  # 边权小的先试
        root_u, root_v = find(parent, u), find(parent, v)
        if root_u == root_v:  # 两端已经连通，选它就会成环
            continue
        if size[root_u] < size[root_v]:  # 小集合接到大集合下面
            root_u, root_v = root_v, root_u
        parent[root_v] = root_u
        size[root_u] += size[root_v]
        total += w
        selected += 1
        if selected == n - 1:  # 生成树正好 n - 1 条边，选满就停
            break
    return total if selected == n - 1 else None


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    edges: list[Edge] = [(next(data), next(data), next(data)) for _ in range(m)]

    answer = kruskal(n, edges)
    # 0 也是合法答案，不能写成 if not answer。
    print("orz" if answer is None else answer)


if __name__ == "__main__":
    solve()
    

输入格式：

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$ 个点的生成树。

同权、负权、重边和自环

输入：

3 5
1 1 -100
1 2 -2
1 2 -2
2 3 0
1 3 0

输出：

-2

自环即使很便宜也不能选。两条重边至多选一条，再任选一条权值为 $0$ 的边连接点 $3$，总权值为 $-2$。

单点无边的输入 1 0 应输出 0；零权答案也是合法答案，不能把 0 当作“不存在生成树”。

常见错误

忘记判断不连通

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

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

把有向图拿来求 MST

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

认为 MST 一定唯一

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

认为负边不能用

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

应用分类详解

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

一、基础连通建设

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

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

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

二、最小瓶颈生成树

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

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

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

三、两点瓶颈路

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

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

核心建模： 在无向连通带权图中，任取一棵 MST，对于任意两个不同顶点 $u,v$，树上连接它们的路径的最大边权，等于原图中所有 $u$ 到 $v$ 路径的最大边权的最小值。即使 MST 不唯一，这个结论也对每一棵 MST 成立。

为什么成立： 删去这条树路径上的一条最大权边 $e$，树会断成两个连通块，$u,v$ 分属两侧。如果存在一条最大边权更小的替代路径，它一定有一条更轻的边 $e'$ 跨过这两个块。用 $e'$ 替换 $e$，就能得到总权值更小的生成树，与 MST 的最优性矛盾。

详细证明见：瓶颈路证明。

“货车运输”求的是路径最小边权尽量大，是上述性质的对偶形式：建最大生成树，再查询树路径上的最小边权。

四、MST 进阶判定与替换

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

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

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

五、离线连通与 Kruskal 思想

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

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

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

六、只加边时压缩旧图

典型模式： 分批加入新边，每一批之后都要求当前图的 MST。

识别信号： 旧边不会删除或改权，希望不用反复扫描所有历史边。

核心建模： 固定点集，设旧边为 $E$、新边为 $S$，旧图的一棵 MST 为 $T$。求 $E\cup S$ 的 MST 时，可以只保留 $T\cup S$。旧图不连通时，保留每个连通分量的 MST，即最小生成森林。

为什么成立： 对任意被舍弃的旧边 $e=(u,v)$，旧树上 $u$ 到 $v$ 的路径只含权值不大于 $w(e)$ 的边。若新图的最优树用了 $e$，删去它后，可以从这条旧树路径上取一条跨越断口的边接回去，代价不增。反复替换，就能得到只使用旧树和新边的最优解。

每次最多保留 $n-1$ 条旧边。但必须允许新边替换旧树边，不能在旧并查集上简单追加合并；此性质也不保证单次更新达到对数复杂度。

完整证明、同权说明和适用边界见：MST 增量更新：为什么只需保留旧的最小生成森林。

经典例题

1. luogu-P3366

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

2. luogu-P1546

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

3. luogu-P2820

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

4. luogu-P1967

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

参考

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