最小生成树

一、直观理解：用最便宜的线把所有点连成一体

给定连通无向带权图，生成树是包含全部 $n$ 个顶点、恰有 $n-1$ 条边且无环的子图。**最小生成树（MST）**是所有生成树中边权总和最小者。

应用直觉：

• 村村通光纤：连接所有村子，总长度尽量短，且不必形成环；
• 聚类中的单链接思想与 MST 相关；
• 近似 TSP 的经典 2-近似也用到 MST。

注意：MST 保证连通且无环，但不直接给出“旅行顺序”；它是网络骨架，不是巡回路径。

二、适用场景与优缺点

类型	说明
适用场景	基础设施最小造价连通；网络设计基线；作为更复杂网络优化的松弛/子结构。
核心优点	贪心正确（切割/回路性质）；Kruskal/Prim 清晰；可证明最优；实现容易。
局限与缺点	只要连通不要流/容量；有向图对应分支问题更难；点必须全部连接，若允许不连需 Steiner 等变体。

三、核心原理

1. 切割性质

对任意切割，权最小的跨越边一定属于某 MST（边权互异时属于唯一 MST）。

2. 回路性质

环上权最大边一定不在某 MST 中。

3. Kruskal

边按权升序；若两端不在同一连通分量则加入（并查集）。$O(m\log m)$。

4. Prim

从一点长树，每次加连接树内与树外的最小边。稠密图可用 $O(n^2)$，稀疏图用堆。

两者在边权唯一时得到同一棵 MST；有并列最优时可有多棵。

四、关键决策

1. Kruskal 还是 Prim

边少点多：Kruskal；稠密：Prim 数组版很干净。

2. 权相同

报告可能非唯一，可输出一棵并说明。

3. 变体

• 最大生成树：权取负或排序反过来；
• 度约束 MST、Steiner 树：NP-hard，需优化/近似。

4. 验证

边数 $n-1$、连通、无环、可用“换边论证”抽查。

五、MATLAB 示例

% 无向图
s = [1 1 1 2 2 3 3 4];
t = [2 3 4 3 5 4 5 5];
w = [4 3 5 2 6 3 4 2];
G = graph(s, t, w);
T = minspantree(G);
fprintf("MST 总权 = %g\n", sum(T.Edges.Weight));
disp(T.Edges);

figure;
p = plot(G, "EdgeLabel", G.Edges.Weight);
highlight(p, T, "EdgeColor", "r", "LineWidth", 2);
title("最小生成树（红）");

% ---- 手写 Kruskal ----
edges = [s' t' w'];
edges = sortrows(edges, 3);
parent = 1:5;
function r = findr(parent, x)
    while parent(x) ~= x
        parent(x) = parent(parent(x));
        x = parent(x);
    end
    r = x;
end
mst = [];
for e = 1:size(edges,1)
    u = edges(e,1); v = edges(e,2); c = edges(e,3);
    ru = findr(parent, u); rv = findr(parent, v);
    if ru ~= rv
        parent(ru) = rv;
        mst = [mst; u v c]; %#ok<AGROW>
    end
end
disp("Kruskal 边:"); disp(mst);
fprintf("总权=%g\n", sum(mst(:,3)));

% ---- 手写 Prim O(n^2) ----
n = 5; W = inf(n);
for e = 1:numel(s)
    W(s(e),t(e)) = w(e); W(t(e),s(e)) = w(e);
end
in = false(1,n); in(1) = true;
key = W(1,:); key(1) = 0; pre = ones(1,n);
for k = 1:n-1
    best = inf; u = -1;
    for i = 1:n
        if ~in(i) && key(i) < best
            best = key(i); u = i;
        end
    end
    in(u) = true;
    for v = 1:n
        if ~in(v) && W(u,v) < key(v)
            key(v) = W(u,v); pre(v) = u;
        end
    end
end
prim_w = 0;
for v = 2:n
    prim_w = prim_w + W(pre(v), v);
    fprintf("Prim 边 %d-%d w=%g\n", pre(v), v, W(pre(v),v));
end
fprintf("Prim 总权=%g\n", prim_w);

六、如何解释结果

1. 顶点/边含义与权单位；
2. 算法；
3. 入选边列表与总造价；
4. 是否唯一；
5. 实际约束（地质、已有线路）未入模则说明；
6. 与次优方案对比（可选）。

七、常见误区

1. 有向图直接套无向 MST

问题已变。

2. 把 MST 当最短路树

最短路树最小化到根距离，MST 最小化总边权，两者不同。

3. 不验证连通

数据有孤立点时无 MST。

4. 负权惊慌

无向 MST 允许负权（无环问题），与 Dijkstra 不同。

八、小结

最小生成树的核心是：

用贪心边选择（切割/回路性质）得到连接全部顶点的最小总权无环子图。

Kruskal 与 Prim 是标准解法。建模时把它定位为“最小连通骨架”，并与路径、流、TSP 等不同目标区分清楚。