最小生成树（Prim、Kruskal）
一、直观理解：用最省的边把所有点连通且不成环
最小生成树（Minimum Spanning Tree, MST）问题：在连通无向带权图中，选取一组边，使得：
- 所有顶点连成一片（连通）；
- 没有环（树）；
- 边权总和最小。
想象要在若干村镇之间架设光缆：不必两两直连，只要全村镇最终互通；每条光缆有成本，希望总成本最低，且不会出现「白花钱的回路」。
Prim 与 Kruskal 是两条经典精确算法，都基于贪心 + 安全边定理：每次加入一条不会破坏「存在某棵 MST 包含已选边集」的边，最终得到全局最优。不必智能优化。
二、适用场景与优缺点
| 类型 | 说明 |
|---|---|
| 适用场景 | 网络骨架设计、聚类中的单链接思想、近似 TSP 的一步、电路布线、行政区划连通、管道干线。 |
| 核心优点 | 有最优性保证；实现成熟；复杂度低；结果可解释（哪条边被选中）。 |
| 局限与缺点 | 标准 MST 不含容量、流量、根节点度约束；有向图是最小树形图另一套理论；动态权/多目标需扩展。 |
使用前确认：
- 图是否无向连通（不连通则得最小生成森林）；
- 权是否可直接比较（同一量纲）；
- 是否有额外约束（度限制、必须含某边）——有则可能要改模型；
- 规模以选 Prim 或 Kruskal。
三、核心原理
1. 树的性质
个顶点的树恰有 条边；任意两点路径唯一；加一边出环，减一边不连通。
2. 割性质（安全边）
将顶点分成两集合 ，跨割的边中权最小者，必属于某棵 MST。Prim 与 Kruskal 都在反复找安全边。
3. Kruskal 算法
- 边按权从小到大排序；
- 依次尝试加边，若两端不在同一连通分量（不成环）则加入；
- 用并查集（Union-Find）维护分量；
- 取满 条边停止。
复杂度 主导于排序。稀疏图很合适。
4. Prim 算法
- 从任意点开始生长树集 ；
- 反复选择连接 与 的最小权边，把新点并入 ；
- 类似 Dijkstra 的「最小键值」更新。
堆优化 。较稠密或邻接矩阵时实现友好。
5. 正确性直觉
贪心每步选安全边，归纳证明已选边集可扩展为 MST，最终即 MST。权可有相同，MST 可能不唯一，但最小总权唯一。
四、关键决策
1. Prim vs Kruskal
| 图特征 | 更合适 |
|---|---|
| 边很少 | Kruskal |
| 边很多 / 矩阵存储 | Prim |
| 需要边排序后的分析 | Kruskal |
| 与 Dijkstra 代码结构统一 | Prim |
2. 强制边 / 禁止边
必须含某边：先加入再在收缩图上求 MST。禁止某边：删边后求。
3. 最大生成树
权取负或排序反向，算法相同。
4. 额外约束
度约束 MST、Steiner 树、有容量的网络设计往往是 NP-hard，需 MILP 或近似，不能硬套裸 MST 却声称满足全部约束。
五、MATLAB 示例
例 1：Kruskal + 并查集
% 无向图边列表：u, v, w（1-based）
edges = [
1, 2, 4;
1, 3, 3;
2, 3, 1;
2, 4, 2;
3, 4, 5;
3, 5, 6;
4, 5, 7
];
n = 5;
edges = sortrows(edges, 3); % 按权升序
parent = 1:n;
rankv = zeros(1, n);
function r = findr(x)
while parent(x) ~= x
parent(x) = parent(parent(x));
x = parent(x);
end
r = x;
end
function united = unionr(a, b)
ra = findr(a); rb = findr(b);
united = false;
if ra == rb, return; end
united = true;
if rankv(ra) < rankv(rb)
parent(ra) = rb;
elseif rankv(ra) > rankv(rb)
parent(rb) = ra;
else
parent(rb) = ra; rankv(ra) = rankv(ra) + 1;
end
end
mst = [];
total = 0;
for i = 1:size(edges, 1)
u = edges(i, 1); v = edges(i, 2); w = edges(i, 3);
if unionr(u, v)
mst(end+1, :) = [u, v, w]; %#ok<AGROW>
total = total + w;
if size(mst, 1) == n - 1, break; end
end
end
disp("Kruskal MST 边："); disp(mst);
fprintf("总权 = %g\n", total);
注：若 MATLAB 版本对嵌套函数写在脚本中的方式敏感，可将
findr/unionr改为脚本内循环手写压缩，或放到独立函数文件。下面给无嵌套函数的紧凑写法。
edges = sortrows([
1 2 4; 1 3 3; 2 3 1; 2 4 2; 3 4 5; 3 5 6; 4 5 7
], 3);
n = 5; parent = 1:n;
mst = []; total = 0;
for i = 1:size(edges, 1)
u = edges(i, 1); v = edges(i, 2); w = edges(i, 3);
% find with path compression
x = u; while parent(x) ~= x, x = parent(x); end, ru = x;
x = v; while parent(x) ~= x, x = parent(x); end, rv = x;
if ru ~= rv
parent(ru) = rv;
mst(end+1, :) = [u v w]; %#ok<AGROW>
total = total + w;
if size(mst, 1) == n-1, break; end
end
end
fprintf("MST 总权=%g，边数=%d\n", total, size(mst,1));
disp(mst);
例 2：Prim（邻接矩阵）
INF = 1e12;
W = INF * ones(5);
und = [1 2 4; 1 3 3; 2 3 1; 2 4 2; 3 4 5; 3 5 6; 4 5 7];
for r = 1:size(und,1)
u = und(r,1); v = und(r,2); w = und(r,3);
W(u,v) = w; W(v,u) = w;
end
n = size(W,1);
inMST = false(1, n);
key = INF * ones(1, n);
par = zeros(1, n);
key(1) = 0;
for it = 1:n
u = 0; best = INF;
for i = 1:n
if ~inMST(i) && key(i) < best
best = key(i); u = i;
end
end
inMST(u) = true;
for v = 1:n
if ~inMST(v) && W(u,v) < key(v)
key(v) = W(u,v);
par(v) = u;
end
end
end
total = 0;
fprintf("Prim 边:\n");
for v = 2:n
fprintf("%d - %d : %g\n", par(v), v, W(par(v), v));
total = total + W(par(v), v);
end
fprintf("总权 = %g\n", total);
例 3：工具箱
G = graph([1 1 2 2 3 3 4], [2 3 3 4 4 5 5], [4 3 1 2 5 6 7]);
T = minspantree(G);
disp(T.Edges);
fprintf("总权 = %g\n", sum(T.Edges.Weight));
六、如何解释结果
报告：
- 顶点/边含义与权单位；
- 算法选择；
- MST 边列表与总权；
- 连通性验证（ 边且连通）；
- 是否唯一（是否存在等权替代边）；
- 业务含义：主干网络如何布局，哪些昂贵边被避开。
可画图标注入选边，比只报一个总权更清晰。
七、常见误区
1. 在有向图上直接 Kruskal
标准 MST 针对无向图；有向需最小树形图（朱-刘/Edmonds）。
2. 不连通仍称生成树
应输出各分量的生成森林并说明。
3. 把 MST 当最短路径树
二者不同：MST 最小化全树总权，不是最小化某点到各点距离和。
4. 有额外约束仍宣称 MST 最优
度限制、容量、多品种流量等会改变问题难度。
5. 权为负时惊慌
MST 算法通常允许负权（无向、无环目标是权和），与最短路不同。
6. 用遗传算法求标准 MST
无必要；贪心精确算法即可。
八、小结
最小生成树的核心思想可以概括为：
在无向带权连通图上，依据割性质贪心加入安全边（Prim 生长树、Kruskal 排序加边），得到连通无环且总权最小的 条边。
它是网络设计类题目的精确首选。写清假设、列出边集与总权，并在存在额外约束时明确是否仍适用 MST，或需升级为更一般的网络设计 / MILP 模型。