在带权图上，有一个经典问题把"贪心"落到实处：最小生成树（Minimum Spanning Tree，MST）用最小的边权总和连通全部顶点。它依靠"每一步做局部最优选择"的贪心方法，背后的理论支撑是切分定理与环性质。理解"为什么贪心在这里是对的"，比单纯硬背代码更重要。
学习目标
- 说出生成树与最小生成树的定义，理解
个顶点的树恰有 条边； - 陈述并论证切分定理与环性质；
- 实现 Prim 与 Kruskal 算法，分析各自复杂度；
- 说明两种算法的适用与不适用场景，并据此选型。
最小生成树的概念
生成树（Spanning Tree）：设
最小生成树（MST）：在所有生成树中，边权总和最小的一棵。这里的“最小”指边权和，不是边数或最大单边权值。边权可以为负，因此 MST 的总权值也可能为负。
理解生成树，先记住三条由"树"的定义直接推出的性质：
个顶点的树恰有 条边； - 树中任意两顶点之间有且仅有一条简单路径；
- 给树加任意一条边，会形成唯一一个环；删去树上任意一条边，图不再连通。
下面这张带权无向图会贯穿后面的 Kruskal 范例。粗体无法稳定跨主题表达，因此图中用 MST 标注最终选中的三条边；它们的权值和为
最小生成树可能不唯一
当图中存在权值相等的边时，MST 可能不止一棵，但等权边并不必然导致多解；无论有多少棵 MST，最小边权和都是唯一确定的。若所有边权两两不同，则 MST 一定唯一（见下文定理）。存在多棵 MST 时，算法返回哪一棵取决于具体的选边顺序，但总权值相同。
生成最小生成树：贪心框架
生成 MST 的通用做法是一个贪心框架：维护一个边集
Prim 与 Kruskal 的区别，只在于"如何找安全边"：Prim 维护一棵连通的树，每次选跨越"树内/树外"的最小边；Kruskal 维护一片森林，每次选不形成环的最小边。它们共享同一个正确性来源——下面两条定理。
两条核心定理
切分定理（Cut Property）
把顶点集
切分定理：对任意切分
，若 是跨越该切分的最小权边，则 一定属于某棵 MST。
证明（交换法）：设
切分定理说明，跨越某个切分的最小权边至少能出现在一棵 MST 中。Prim 使用的切分是“当前树的顶点集合
环性质（Cycle Property）
环性质：无向图中，任意一个环上权值最大的边（若最大边唯一）不属于任何 MST。
证明（反证）：设
环性质解释了为什么环上的唯一最重边可以直接排除。Kruskal 遇到会使当前森林成环的候选边时，这条边不轻于环中此前已选的边；即使存在并列权值，也可以跳过当前候选边，因为当前森林已经用不更重的边连通了它的两个端点。这里不能把“并列最重”误写成“不属于任何 MST”：只有唯一最重时才有这个强结论。
切分定理与环性质从两个方向约束选边：前者说明某条边可以安全加入某棵 MST，后者说明唯一最重边不可能出现在任何 MST 中。“属于某棵”不等于“属于所有”，使用时要保留量词。
由定理得到的两个推论
- 唯一性：若所有边权两两不同，则 MST 唯一。反证如下：若存在不同的 MST
，考察只属于其中一棵树的边（即二者的对称差），并从中取权值最小的边 ；不妨设 。把 加入 会形成一个环，其中必有边 ；边权互异且 是对称差中的最轻边，所以 。用 替换 会得到权值更小的生成树，与 最小矛盾。 - 贪心安全：算法应维护“当前森林包含于某棵 MST”这一不变量。若某个切分不被当前森林中的边跨越，那么选取该切分上的最小权边，交换论证可保证加入后仍存在一棵包含新森林的 MST。Prim 与 Kruskal 选择的切分都满足这个条件；不能把规则简化为“任取某个切分的最小边”。
Prim 算法
Prim 从任意一个起点出发，把已选顶点看作集合
朴素实现维护一个距离数组 dist[v]（dist，共
由于合法 MST 的总权值可能恰好为 -1，不能用 -1 同时表示“不连通”。下面用 std::optional<long long> 区分失败与合法的负权结果，并用 64 位整数保存边权和。
// 邻接矩阵 g[u][v] = 边权；INF 表示无边；nullopt 表示图不连通
std::vector<std::vector<long long>> graph;
int n;
std::optional<long long> prim() {
if (n == 0) return 0LL;
std::vector<long long> dist(n, INF); // dist[v]：v 到当前树的最小边权
std::vector<bool> inTree(n, false);
long long total = 0;
dist[0] = 0; // 从顶点 0 开始
for (int i = 0; i < n; ++i) {
int u = -1;
for (int v = 0; v < n; ++v) // 选 dist 最小且不在树内的顶点
if (!inTree[v] && (u == -1 || dist[v] < dist[u])) u = v;
if (u == -1 || dist[u] == INF) return std::nullopt;
inTree[u] = true;
total += dist[u];
for (int v = 0; v < n; ++v) // 用 u 更新邻居
if (!inTree[v] && graph[u][v] < dist[v]) dist[v] = graph[u][v];
}
return total;
}若用邻接表 + 二叉堆维护"当前到树的最小边权"，每轮取堆顶
稠密图别急着上堆
堆优化 Prim 通常更适合稀疏图；稠密图中
Kruskal 算法
Kruskal 把所有边按权值升序排序，从最小边开始逐条考虑：若这条边的两个端点当前不在同一连通分量（加入后不成环），就选中它并合并两个分量。连通性用并查集维护。
正确性分两步：当候选边
排序占主导，总复杂度：
struct Edge {
int u, v;
long long w;
bool operator<(const Edge& o) const { return w < o.w; }
};
struct DSU {
std::vector<int> p; // 根节点保存负的分量大小
DSU(int n) : p(n, -1) {}
int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); }
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (p[a] > p[b]) std::swap(a, b); // 让较大的分量作为新根
p[a] += p[b];
p[b] = a;
}
};
// 返回 nullopt 表示图不连通；负数总权值仍是合法结果
std::vector<Edge> edges;
std::optional<long long> kruskal() {
if (n == 0) return 0LL;
std::sort(edges.begin(), edges.end()); // 按权值升序
DSU dsu(n);
long long total = 0;
int cnt = 0;
for (auto [u, v, w] : edges) {
if (dsu.find(u) != dsu.find(v)) { // 不成环才加入
dsu.unite(u, v);
total += w;
if (++cnt == n - 1) break; // 已选满 n-1 条边
}
}
if (cnt != n - 1) return std::nullopt;
return total;
}完整解题范例
范例一：Kruskal 求最小生成树权值
题目解读
给定一个连通无向图，可能含自环、平行边和负权边，求最小生成树的总权值。输入规模允许
自环永远不能连接两个不同分量；平行边无需预处理，排序后较轻边会先被考虑；负权边不破坏 MST 的切分定理，可以正常参与排序和选边。
算法分析
将全部边按权值升序排序，用并查集维护当前森林的连通分量。若边 (u,v) 的两个端点属于不同分量，就选中该边并合并分量；否则加入它会成环，直接跳过。选满 n-1 条边后得到 MST。
排序为
伪代码
按权值升序排序 edges
初始化 n 个单点分量
total = 0, used = 0
for edge in edges:
if find(edge.u) == find(edge.v): continue
合并 edge.u 与 edge.v
total += edge.w
used++
if used == n - 1: break
输出 total最终代码
可编译 C++17 实现
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
struct Edge {
int u;
int v;
long long w;
};
class DSU {
public:
explicit DSU(int n) : parent_(n), rank_(n, 0) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int find(int x) {
if (parent_[x] != x) parent_[x] = find(parent_[x]);
return parent_[x];
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (rank_[a] < rank_[b]) std::swap(a, b);
parent_[b] = a;
if (rank_[a] == rank_[b]) ++rank_[a];
return true;
}
private:
std::vector<int> parent_;
std::vector<int> rank_;
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0, m = 0;
if (!(std::cin >> n >> m)) return 0;
std::vector<Edge> edges(m);
for (Edge& edge : edges) {
std::cin >> edge.u >> edge.v >> edge.w;
}
std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.w < b.w;
});
DSU dsu(n);
long long total = 0;
int used = 0;
for (const Edge& edge : edges) {
if (!dsu.unite(edge.u, edge.v)) continue;
total += edge.w;
if (++used == n - 1) break;
}
std::cout << total << '\n';
}拓展、思考与变式
- 若输入不保证连通，应在结束时检查
used == n-1；否则得到的只是最小生成森林； - 若还要输出树边，只需在
unite成功时保存当前边； - 若边已经有序，可省去排序，时间接近
； - 对应练习：T12 · 07E12 · 最小生成树；再迁移到 T13 · 07E13 · 最低成本连通所有城市。
范例二：Prim 连接平面上的所有点
题目解读
平面上有 n 个点，任意两点都能连接，费用为曼哈顿距离
求把全部点连成一棵树的最小费用。因为任意两点间都有边，显式生成完全图需要
算法分析
维护 best[v]：顶点 v 到当前树的最小连接费用。每轮选择 best 最小的未选顶点 u，把 best[u] 累加到答案，再用 u 到其他未选点的曼哈顿距离更新它们的 best。
完全图天然连通，因此每轮一定能选到新点。共进行 n 轮，每轮扫描和更新
伪代码
best = 全 INF, best[0] = 0
used = 全 false
total = 0
重复 n 次:
u = best 最小的未选点
used[u] = true
total += best[u]
for 每个未选点 v:
w = |x[u]-x[v]| + |y[u]-y[v]|
best[v] = min(best[v], w)
输出 total最终代码
可编译 C++17 实现
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n = 0;
if (!(std::cin >> n)) return 0;
std::vector<std::pair<long long, long long>> points(n);
for (auto& [x, y] : points) std::cin >> x >> y;
const long long INF = std::numeric_limits<long long>::max() / 4;
std::vector<long long> best(n, INF);
std::vector<bool> used(n, false);
best[0] = 0;
long long total = 0;
for (int step = 0; step < n; ++step) {
int u = -1;
for (int v = 0; v < n; ++v) {
if (!used[v] && (u == -1 || best[v] < best[u])) u = v;
}
used[u] = true;
total += best[u];
for (int v = 0; v < n; ++v) {
if (used[v]) continue;
long long weight = std::llabs(points[u].first - points[v].first)
+ std::llabs(points[u].second - points[v].second);
best[v] = std::min(best[v], weight);
}
}
std::cout << total << '\n';
}拓展、思考与变式
- 若费用改为欧几里得距离，MST 框架不变，但边权计算和数值类型会变化；
- 若输入只提供部分可用边，就不能假设图天然连通，必须检测无法选出新顶点的情况；
- 若
n很大，需要利用几何结构减少候选边，而不能继续扫描完全图； - 对应练习：T14 · 07E14 · 连接所有点的最小费用。
算法的适用范围与选择
Prim 与 Kruskal 都能正确求出 MST，选谁取决于图的稠密程度和存储表示：
| 场景 | 推荐算法 | 复杂度 | 说明 |
|---|---|---|---|
| 稠密图（ | Prim 朴素版 | 邻接矩阵扫描，常数小 | |
| 稀疏图（ | Kruskal | 排序 + 并查集，实现简单 | |
| 稀疏图，边已按权排序 | Kruskal | 省去排序，几乎线性 | |
| 稀疏图，需堆优化 | Prim + 堆 | 邻接表 + 优先队列 |
各自的"不适用"部分：
- Prim 朴素版在稀疏图上浪费：
中大量时间花在扫描无边连接的顶点上。 - Prim 堆优化在稠密图上退化：松弛次数
接近 ，堆操作反而拖慢。 - Kruskal 需要先把边排序；若图是动态的、边频繁变化，反复排序不划算。
- 求覆盖全图的 MST 要求图连通：图不连通时，Kruskal 得到的是最小生成森林，Prim 则只能得到起点所在连通分量的最小生成树。
选型口诀
先看稠密还是稀疏，再看有无排序/堆的现成条件。稠密图选 Prim（矩阵），稀疏图选 Kruskal，是竞赛与工程里最常用的两条默认规则；需要精确到常数时再考虑堆优化 Prim。
做题流程与边界检查
易错点 · 把生成森林当成最小生成树
图不连通时不存在覆盖全部顶点的生成树。Kruskal 必须检查是否选满 n-1 条边；Prim 必须检查每轮是否还能找到有限候选。若题目要求森林，应明确改称“最小生成森林”。
易错点 · 等权边不等于 MST 一定不唯一
等权边只意味着可能存在多种安全选择。判断唯一性需要分析是否存在可互换的同权边；无论结构是否唯一，所有 MST 的总权值都相同。
手算或编程实现 MST 时，可以固定使用下面的检查顺序：
- 先确认图是否连通；不连通时输出约定的失败结果，不能把生成森林误当成生成树。
- 对 Kruskal，先按权值排序，再逐边判断并查集根是否相同；相同代表成环，必须跳过。
- 对 Prim，维护“每个未加入顶点连接当前树的最小边”，加入顶点后只更新它的邻居。
- 最后检查选边数量：连通的
n个顶点必须恰好选出n-1条边。
重点边界包括单顶点图、平行边、相同权值、自环、负权边和稠密图。自环不能进入生成树；同一对端点之间存在多条平行边时，较重的边不会优于较轻的边，可以全部交给算法处理，也可以预处理后只保留最小权值；相同权值可能产生多棵结构不同但总权值相同的 MST。实现中不要把“存在等权边”直接当作 MST 不唯一的判定条件。
配套 Lab 建议先完成 Kruskal 的并查集版本，再用 Quiz 复核切分定理、环性质和算法选型，最后通过边界测试验证“不成环”和“恰好 n-1 条边”两个不变量。
参考资料
- 《洛谷深入浅出程序设计竞赛》图论部分（最小生成树）
- 王道《数据结构》考研复习指导：图的应用（最小生成树）
- 严蔚敏《数据结构》（C 语言版）：图的生成树
彩蛋
- 希望大家能在看完这章后能有所体悟，如果真的有所体悟，可能就会有下图表情（狗头）
- 哦耶~
代码题练习
按本节下方的 Lab 入口练习。下列入口使用稳定 Lab 编号。