最小生成树

一句话算法

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

问题模型

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

要求选出若干条边，使得：

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

满足前两条的边集是一棵生成树。权值和最小的生成树就是最小生成树，简称 MST。

核心直觉

生成树不能有环。Kruskal 的做法是：

从最短的边开始尝试，能连接两个不同连通块就选，已经在同一个连通块里就跳过。

这背后的直觉是：如果一条小边能把两个原本不连通的部分接起来，它就是当前最便宜的连接方式，没有理由先选更贵的边。

核心性质

切分性质

把点集分成两个非空部分 $S$ 和 $V-S$。所有跨过这个切分的边中，权值最小的边一定存在于某棵 MST 中。

如果这条最小边唯一，那么它一定出现在所有 MST 中。

两个区域必须靠某条边连起来。既然迟早要连，那么选跨区边里最便宜的那条不会吃亏。

环路性质

在任意一个环中，权值最大的边一定可以不选。

如果最大边唯一，那么它一定不在任何 MST 中。

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

算法步骤

Kruskal 算法按下面的步骤构造最小生成树：

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

算法证明

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

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

现在考虑 Kruskal 准备选择的一条边 $e=(u,v)$。此时 $u$ 和 $v$ 属于两个不同连通块。把当前连通块看成一个切分，$e$ 是所有可连接这两个不同连通块的边中，当前最先被扫描到的最小边。

根据切分性质，选择 $e$ 不会破坏“可以扩展成 MST”的可能性。

如果一条边连接同一连通块，选它会形成环。根据生成树不能有环，它不可能是当前必须选择的边，跳过它不会丢掉最优解。

不断重复这个过程，最终得到 $n-1$ 条边。它们连通且无环，是一棵生成树；又因为每一步都保持可以扩展成 MST，所以最终得到的就是 MST。

复杂度分析

Kruskal 的主要开销是排序。

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

代码实现

        
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;
}
    

测试用例

输入：

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)，总权值为 6。

应用分类详解

MST 的本质是在保证全图连通的前提下，选择最便宜的一组连接关系。只要题目要求“连接所有点，总代价最小”，就应该优先考虑最小生成树。

一、基础连通建设

典型模式： 修路、铺网线、建管道、连接村庄，要求所有点连通且成本最低。

识别信号： “使所有点连通”“总花费最小”“无向图边权”。

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

二、瓶颈路问题

典型模式： 两点之间路径的代价由路径上最大边权决定，要求这个最大值尽量小。

识别信号： “最大边最小”“最小化路径上的最大限制”“承重/噪音/风险上限”。

核心建模： MST 上任意两点路径的最大边权，等于原图中这两点所有路径里“最大边权最小”的值。

三、MST 变种与进阶

典型模式： 不只求一棵 MST，还要计数、判断边是否可在某棵 MST 中、或动态加入边。

识别信号： “有多少棵 MST”“某些边能否同时出现”“加入边后重新求 MST”。

核心建模： 仍围绕切分性质、环路性质和同权边分组讨论。

经典例题

1. luogu-P3366

最小生成树模板题。用于练习 Kruskal 和并查集。

2. luogu-P2820

给出所有道路维护费用，要求删去不必要道路后仍连通。答案是总费用减去 MST 费用。

3. luogu-P1967

货车运输。它是最大生成树上的瓶颈路问题，和 MST 的瓶颈性质是同一类思想。

参考

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