分合之道：最小生成树的 Kruskal 与 Prim 算法
最小生成树问题想象你是一位城市规划师，面前摊开一张地图，标记着散落的村庄。你的任务是用最经济的成本，在村庄间铺设道路，让所有村庄互通。这个问题看似简单，却隐藏着一个经典的数学命题：如何在一张“带权图”中，找到一棵总权重最小的树，连接所有节点？
数学定义
给定一个连通无向图 \(G=(V,E)\)，其中每条边 \(e \in E\) 有一个权重 \(w(e)\)，最小生成树（MST）的目标是选择一个边集 \(T \subseteq E\)，满足：
[*]连通性：\(T\) 连接所有顶点，形成一棵树（无环且覆盖全部 \(|V|\) 个顶点）；
[*]最小总权：边集的总权重最小。
公式化表达为：
\
你可以将 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|)\)，性能瓶颈在于排序。
<hr>实例演示
假设有 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.emplace_back(v, w, i); adj.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) continue; // 如果节点已经在生成树中，跳过 inMST = true; mst_weight += edge.weight; if (edge.index != -1) ans.push_back(edge.index); // 跳过虚拟的起始边 for (const Edge& e : adj) { if (!inMST) { 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：
[*]关注点的选择
[*]以核心据点为中心，逐步将点加入生成树。通过优先队列维护扩张前沿，像一支训练有素的军队攻城略地。
[*]若图结构松散（如稀疏图），频繁的优先队列更新可能得不偿失。
<hr>实战性能对比
算法**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 的边排序和并查集更易并行化。
尽管路径迥异，Kruskal 与 Prim 最终都收敛于同一个最小总权值——这印证了数学的确定性之美。它们都在贪心策略的框架下，以局部最优逼近全局最优，正是算法设计中最深邃的智慧。
页:
[1]