分合之道：最小生成树的 Kruskal 与 Prim 算法

技术分享 12个月前 (02-15) 0 999+

关注

最小生成树问题

想象你是一位城市规划师，面前摊开一张地图，标记着散落的村庄。你的任务是用最经济的成本，在村庄间铺设道路，让所有村庄互通。这个问题看似简单，却隐藏着一个经典的数学命题：如何在一张“带权图”中，找到一棵总权重最小的树，连接所有节点？

数学定义
给定一个连通无向图 (G=(V,E))，其中每条边 (e in E) 有一个权重 (w(e))，最小生成树（MST）的目标是选择一个边集 (T subseteq E)，满足：

连通性：(T) 连接所有顶点，形成一棵树（无环且覆盖全部 (|V|) 个顶点）；
最小总权：边集的总权重最小。

公式化表达为：

[T = argmin_{T' subseteq E} left{ sum_{e in T'} w(e) bigg| text{$T'$ 是树且覆盖所有顶点} right} ]

你可以将 MST 想象成一张“最优化的网”：

节点是村庄，边是可能的道路，权重是修路成本。
MST 要求用最少的“钢筋水泥”铺就一张四通八达的路网，避免环路（否则浪费资源），覆盖所有村庄（否则有人被孤立）。

实际场景
最小生成树渗透在生活方方面面的“无形之网”中：

通信基站：用最低成本铺设光纤，覆盖所有信号塔；
电路设计：用最短导线连接芯片引脚，避免短路；
物流规划：构建仓库间的高效运输链路，减少冗余路径。

Kruskal 算法：条条大路通罗马

假设你面前有一群互不相识的村民（节点），他们需要通过道路（边）连接成一个整体。每条道路的修建成本（边权）不同。Kruskal 算法的策略是贪心选取，既然要总道路最便宜，那么就每次让最便宜的边优先获得修建权，但必须遵守一条铁律：绝不允许形成闭环，不可以连接已经相连的点。

具体来说，Kruskal 算法的步骤如下：

全边排序：将所有边按权重升序排列，形成候选队列。
逐轮选择：从最小的边开始，依次检查每条边：
- 若这条边连接的是两个尚未连通的村庄（即加入后不形成环），则采纳它；
- 若这条边会让两个已连通的村庄形成冗余环路，则淘汰它。
终局条件：树的边数总是比比点数少 1，所以当选中 (|V|-1) 条边时，所有村庄连通，选举结束。

正确性

Kruskal 的贪心策略看似简单，但为何正确？关键在于“安全边定理”：

定理：若边 (e) 是当前未被选中的最小权重边，且连接两个不同的连通分量，则 (e) 必定属于某个最小生成树。

用微扰法的思路反证，假设存在一个不包含 (e) 的 MST (T)。将 (e) 加入 (T) 会形成一个环，此时环中必然存在另一条边 (e') 权重大于等于 (e)（因为 (e) 是当前最小）。用 (e) 替换 (e') 可得到总权更小或相等的树，矛盾。因此 (e) 必须属于某个 MST，我们一定会选择它。

归纳法视角：

初始状态：所有节点独立，属于不同的连通分量。
归纳假设：已选的边集 (T_k) 是某个 MST 的子集。
归纳步骤：选择下一条最小边 (e)，若它连接两个不同分量，则必属于该 MST。

时间复杂度

Kruskal 的效率取决于两大操作：

排序边：(O(|E| log |E|))
并查集操作（查询节点是否已经连接）：
- find 和 union 的单次操作近乎常数时间（(O(alpha(|V|)))，(alpha)为反阿克曼函数）。
- 总操作次数为 (O(|E|))，因此并查集的总成本为 (O(|E| cdot alpha(|V|)))，低于排序开销。

复杂度总结：(O(|E| log |E|))，性能瓶颈在于排序。

实例演示

假设有 4 个村庄（A, B, C, D），边权如下：

AB: 1, AC: 3, AD: 4
BC: 2, BD: 5, CD: 6

执行流程：

排序边：AB(1) → BC(2) → AC(3) → AD(4) → BD(5) → CD(6)
依次选择：
- 选AB（连通{A,B}，剩余需选3条边）
- 选BC（连通{A,B,C}，剩余需选2条）
- 跳过AC（A和C已连通，形成环）
- 选AD（连通{A,B,C,D}，任务完成）

最终 MST 总权重：1 + 2 + 4 = 7

// 参考题目：https://judge.yosupo.jp/problem/minimum_spanning_tree，为稀疏图  #include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std;  class Graph {     struct Edge {         int u, v, w, i;         bool operator<(const Edge& other) const {             return w < other.w;         }     };      vector<Edge> edges;     int n, m;  public:     void addEdge(int u, int v, int w, int i) {         edges.push_back({u, v, w, i});     }      Graph(int n, int m) : n(n), m(m), edges(m) {} // 构造函数，本题编号从 0 开始      long long kruskal(vector<int>& ans) {         sort(edges.begin(), edges.end());         ufs uf(n); // 并查集实现略         long long mst_weight = 0;         for (const auto& edge : edges) {             if (!uf.get(edge.u, edge.v)) {                 uf.set(edge.u, edge.v);                 mst_weight += edge.w;                 ans.push_back(edge.i);             }         }          // 若 ans 里的边数不为 n - 1，则说明图不连通，略         return mst_weight;     } };

Prim 算法：以点破面，聚沙成塔

想象你是一位部落首领，想要以最少的资源统一整片大陆。你的策略不是四处开花，而是从一座核心城池出发，步步为营，将最近的未征服领土纳入版图。Prim 算法正是这种“中心化扩张”的数学映射——以点为锚，逐步吞噬最小代价的边疆。其关注点而不是边，和 Dijkstra 很相似。

具体步骤：

选定起点：任选一个节点作为初始据点占领（如村庄A），作为最小生成树中的第一个点。
维护优先队列：记录当前“已占领区域”与“未占领区域”之间的所有边（称为前沿边），并始终选择其中权重最小的边。
扩张领土：将这条最小边连接的未占领节点纳入版图，并更新前沿边集合。
循环直至统一：重复直到所有节点被占领（选出 (|V|-1) 条边）。

正确性证明

Prim 的正确性依赖于“切割性质”：

定理：对于图的任意一个切割（将顶点分为两个集合 (S) 和 (V-S)），若边 (e) 是横跨该切割的最小权重边，则 (e) 属于某个最小生成树。

假设存在一个不包含 (e) 的 MST (T)。将 (e) 加入 (T) 会形成一个环，环中必有一条边 (e') 横跨同一切割且权重大于等于 (e)。用 (e) 替换 (e') 可得到总权更小或相等的树，矛盾。因此 (e) 必须属于 MST。

归纳法视角：

初始状态：集合 (S) 仅包含起点，此时所有连接 (S) 与 (V-S) 的边构成前沿边。
归纳假设：已选的边集 (T_k) 是某个 MST 的子集，且 (S) 是连通子图。
归纳步骤：选择最小前沿边 (e)，将其加入 (T_k)，扩展 (S)，保证 (T_{k+1}) 仍属于 MST。

时间复杂度

Prim 的性能因实现方式差异悬殊，其关键在于如何维护当前“未选择节点”到“已选择节点”的距离，并从中选出最小值。

二叉堆维护：
- 这是最常见的做法，使用优先队列维护前沿边，每次提取最小值 (O(log |V|))。
- 总操作次数 (O(|E| log |V|))，适合稀疏图。
暴力实现（邻接矩阵）：
- 每次遍历所有点，选择应该加入的点，时间复杂度 (O(|V|^2))。
- 这反而适合稠密图（如完全图），此时 (|E| approx |V|^2)，复杂度与 Kruskal 的 (O(|E| log |E|)) 相当。
斐波那契堆维护：
- 已经在堆内的节点，其距离值还可能降低。二叉堆无法直接实现降低一个堆内元素，只能让一个点多次入队并仅处理第一次；但斐波那契堆可以均摊 $O(1) $ 实现。
- 降低了优先级更新的成本，复杂度 (O(|E| + |V| log |V|))。
- 这是 Prim 的理论最优实现，但常数较大，且斐波那契堆的实现较难，实际应用较少。

// 二叉堆版本  class Graph {     struct Edge {         int to, weight, index;         Edge(int t, int w, int i) : to(t), weight(w), index(i) {}         bool operator<(const Edge& other) const {             return weight > other.weight; // 优先队列是最大堆         }     };     vector<vector<Edge>> adj; // 邻接表     int n; public:     Graph(int n) : n(n), adj(n) {}      void addEdge(int u, int v, int w, int i) {         adj[u].emplace_back(v, w, i);         adj[v].emplace_back(u, w, i);      }      long long prim(vector<int>& ans) {         vector<bool> inMST(n, false);         priority_queue<Edge> pq;         long long mst_weight = 0;         pq.emplace(0, 0, -1); // 从任意节点（此处选择 0）开始         while (!pq.empty()) {             Edge edge = pq.top(); pq.pop();                          int v = edge.to;             if (inMST[v]) continue; // 如果节点已经在生成树中，跳过             inMST[v] = true;             mst_weight += edge.weight;             if (edge.index != -1) ans.push_back(edge.index); // 跳过虚拟的起始边             for (const Edge& e : adj[v]) {                 if (!inMST[e.to]) {                     pq.emplace(e.to, e.weight, e.index);                 }             }         }         return mst_weight;     } };

实例演示

沿用 Kruskal 的例子：4 个村庄（A, B, C, D），边权如下：

AB: 1, AC: 3, AD: 4
BC: 2, BD: 5, CD: 6

从A出发的执行流程：

初始前沿边：AB(1), AC(3), AD(4)
- 选AB(1)，占领B，前沿边更新为：AC(3), AD(4), BC(2), BD(5)
当前前沿边：AC(3), AD(4), BC(2), BD(5)
- 选BC(2)，占领C，前沿边更新为：AC(3), AD(4), BD(5), CD(6)
当前前沿边：AC(3), AD(4), BD(5), CD(6)
- 选AD(4)，占领D，任务完成

最终 MST 总权重：1 + 2 + 4 = 7（与 Kruskal 结果一致）

Kruskal 与 Prim 的对决

Kruskal：
- 关注边的选择
- 所有边按权排序，通过并查集动态维护连通性，像一场自下而上的“边缘力量联合”。
- 若图中存在大量高权冗余边（如完全图），排序开销可能拖累全局效率。
Prim：
- 关注点的选择
- 以核心据点为中心，逐步将点加入生成树。通过优先队列维护扩张前沿，像一支训练有素的军队攻城略地。
- 若图结构松散（如稀疏图），频繁的优先队列更新可能得不偿失。

实战性能对比

算法	Kruskal	Prim
稀疏图	✅ 稳赢（ (\|E\| approx \|V\|) ）	❌ 二叉堆实现勉强一战
稠密图	❌ 排序成本过高	✅ 暴力实现碾压（(O(\|V\|^2))）
动态增边	✅ 天然支持	❌ 需重新计算
分布式计算	✅ 边排序可并行	❌ 强依赖全局状态

选择指南

“边多选 Prim，边少选 Kruskal”：
- 若 (|E| gg |V|)（如完全图），Prim 的暴力实现更优；
- 若 (|E| ll |V|^2)（如树状图），Kruskal 的排序+并查集组合更高效。
“动态变化选 Kruskal，静态结构选 Prim”：
- 需要动态增删边？Kruskal 天然支持；
- 图结构固定且需频繁求解？Prim 可预处理邻接矩阵。
“若要分布式，Kruskal 是唯一解”：
- MapReduce 处理超大规模图时，Kruskal 的边排序和并查集更易并行化。