4.3 Minimum Spanning Trees：切分定理、Prim、Kruskal与最优性证书

按官方4.3重建加权无向图与Edge API、MST基本原理、切分定理和交换证明、Lazy/Eager Prim、Kruskal、复杂度及最优性认证。

从“连通所有点，但不要多花一条边”开始

铺设光纤、电网、道路或芯片布线时，常见目标不是让任意两点都有直接连接，而是从已有候选连接中选出一组边：所有站点互相可达、没有冗余环路，并让总成本最低。这就是最小生成树（，minimum spanning trees）问题。

先预测：若每次都拿全图中当前最轻、且尚未选过的edge，最终一定是MST吗？不一定。轻边也可能在已连接区域内部形成cycle；算法必须说明当前edge跨越了哪一个cut，或用Union-Find证明它连接两个不同components。MST的greedy choice不是“看到小就拿”，而是“在明确的feasibility invariant下拿安全边”。

本节沿官方4.3的逻辑推进：先定义weighted undirected graph与spanning tree，再从tree的cycle/cut二重性推出切分定理，随后把同一个generic greedy algorithm实例化成Lazy Prim、Eager Prim与Kruskal，最后不信任算法名称，只靠结构与cut certificate独立验证结果。

selected edge = 3-4@0.45

either()

other(3)

weight()

0.45

adj(3) = 1-3@0.50 · 2-3@0.35 · 3-4@0.45 · 3-5@0.70

Immutable Edge storestwo endpoints与real weight；undirected adjacency lists在两端引用同一个Edge object。

4.3.1 Edge-weighted graphs：一条edge同时属于两个adjacency lists

加权无向图（，edge-weighted graphs）由vertices、unordered endpoint pairs与weights组成。Edge必须回答三个问题：任取一个endpoint、给定一个endpoint返回另一个、按weight比较。

public final class Edge implements Comparable<Edge> {
    private final int v;
    private final int w;
    private final double weight;
 
    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
    public double weight() { return weight; }
    public int either() { return v; }
    public int other(int vertex) {
        if (vertex == v) return w;
        if (vertex == w) return v;
        throw new IllegalArgumentException("not an endpoint");
    }
    public int compareTo(Edge that) {
        return Double.compare(this.weight, that.weight);
    }
}

EdgeWeightedGraph与4.1的Graph一样使用vertex-indexed adjacency lists，但两个list引用同一个immutable Edge object。添加edge (e=(v,w)) 时同时写入 adj[v] 与 adj[w]，edge count只增加一次：

public void addEdge(Edge e) {
    int v = e.either();
    int w = e.other(v);
    validateVertex(v);
    validateVertex(w);
    adj[v].add(e);
    adj[w].add(e);
    E++;
}

因此adjacency storage含 $2E$ 个references，space为 $\Theta(V+E)$ 。迭代全图unique edges时需避免输出两次：只在 other(e,v) > v 时yield；self-loop则每两次adjacency occurrence输出一次。

MST输入通常假设graph connected。若不连通，不存在覆盖全部vertices的single spanning tree；同一套greedy machinery会在每个connected component产生minimum spanning forest。Edge weights可以为负、为零或相等；负权不妨碍MST。Distinct weights只用于保证MST唯一，并非三种算法正确性的前提。

4.3.2 Spanning tree：连通、无环与V-1是同一结构的三张证书

生成树（spanning tree）是包含全部V个vertices的connected acyclic subgraph。对一个V-vertex undirected graph，下列任意两项会强迫第三项成立：connected、acyclic、edge count为V-1。因此候选集T的结构证书可以写成：

|T|=V-1,\qquad connected(T),\qquad acyclic(T)

树的两个基本事实驱动全部MST证明：

给tree添加一条non-tree edge会产生且只产生一个cycle。
从tree删除任意一条edge会产生且只产生一个cut，将vertices分成两个components。

MST目标是在所有spanning trees集合中最小化edge weights之和：

T^*=\operatorname*{arg\,min}_{T\text{ is a spanning tree}} w(T), \qquad w(T)=\sum_{e\in T}w(e)

这不是shortest-path tree。Shortest-path tree最小化某个source到每个vertex的path distance；MST只最小化整棵树的total edge weight，并不保证任意pair的tree path最短。两者都可能有V-1条边，但optimization objective完全不同。

4.3.3 Cut property：安全边必须跨过尊重当前forest的cut

切分（，cut）将vertices分为S与V-S。一个endpoint在S、另一个在V-S的edge称跨切边（，crossing edge）。

若当前已选edges集合A是一片forest，一个cut“尊重A”表示A中没有edge跨过该cut。切分定理（，cut property）给出generic greedy choice：

e=\operatorname*{arg\,min}_{x\in\delta(S)}w(x),\quad A\cap\delta(S)=\varnothing \quad\Longrightarrow\quad A\cup\{e\}\text{ is contained in an MST}

其中 $\delta(S)$ 是cut的crossing-edge set。若weights distinct，minimum crossing edge不仅safe，而且属于唯一MST。

切分定理不能省略“尊重A”。若cut已被A中的edge跨过，再加一个minimum crossing edge可能把A闭合成cycle。算法每轮真正维护的是invariant：已选A无cycle，并且存在某棵MST包含A。

交换证明：让任意MST接纳安全边

取一棵包含A的MST $T$ 。若minimum crossing edge e已在T中，结论直接成立。否则向T加入e，tree加一边形成unique cycle。因为e跨cut，该cycle必须至少用另一条crossing edge f返回cut原侧。Cut minimum保证 $w(e)\le w(f)$ 。删去f后得到新spanning tree：

T'=T+e-f,\qquad w(T')=w(T)+w(e)-w(f)\le w(T)

T本来最优，所以T'同样最优，并包含 $A\cup\{e\}$ 。这就是exchange argument：每一步greedy choice都能交换进某个global optimum，而不破坏此前选择。

若 $w(e)\lt w(f)$ ，任何包含f而不含e的tree都可被strictly improved；这也解释了distinct weights为何导出unique MST。若weights相等，交换后权重不变，可能存在多棵MST，但算法返回其中任意一棵都正确。

4.3.4 Generic greedy MST：每轮都把components减少一个

Generic algorithm从empty forest A开始，反复选择一个尊重A的cut，并加入该cut的minimum crossing edge。每次edge连接A的两个不同components，所以不会成环；V-1次后只剩一个component，A成为spanning tree。Cut property保证每个prefix都包含于某棵MST，最终A本身就是MST。

不同MST算法只是在回答两个工程问题时采用不同数据结构：

选择哪个respecting cut？
怎样快速找到它的minimum crossing edge？

Prim固定“tree vertices与non-tree vertices”这一动态cut；Kruskal让当前forest的任意component都可成为cut，并按global edge order找下一条连接different components的边。

4.3.5 Lazy Prim：允许失效边留在priority queue

Prim算法（，Prim's algorithm）维护marked set S，即当前MST tree的vertices。所有一端marked、一端unmarked的edges跨越cut $(S,V-S)$ 。Lazy implementation把每次新vertex的eligible incident edges全部压入MinPQ：

private void prim(EdgeWeightedGraph G, int s) {
    scan(G, s);
    while (!pq.isEmpty() && mst.size() < G.V() - 1) {
        Edge e = pq.delMin();
        int v = e.either(), w = e.other(v);
        if (marked[v] && marked[w]) continue; // obsolete
        mst.enqueue(e);
        weight += e.weight();
        if (!marked[v]) scan(G, v);
        if (!marked[w]) scan(G, w);
    }
}
 
private void scan(EdgeWeightedGraph G, int v) {
    marked[v] = true;
    for (Edge e : G.adj(v))
        if (!marked[e.other(v)]) pq.insert(e);
}

“Lazy”指失效处理推迟到 delMin：edge插入时跨cut，之后它的两个endpoints可能都进入tree，edge便不再crossing，但仍留在PQ。弹出时若两端marked，必须discard；否则它是当前cut的minimum crossing edge，由cut property安全。

每条edge最多插入一次、删除一次，PQ最多 $\Theta(E)$ ，time为 $O(E\log E)$ ，space为 $O(E)$ 。对connected graph，accepted edges恰好V-1；若PQ提前为空而数量不足，输入不连通，不能把partial tree报告成MST。

4.3.6 Eager Prim：每个non-tree vertex只保留最佳连接

Eager Prim仍使用相同cut，但不保留所有crossing edges。它为每个unmarked vertex w维护：distTo[w] 是当前tree到w的minimum known edge weight，edgeTo[w] 是实现该值的edge。IndexMinPQ以vertex为key，只让每个w保留一个entry。

private void scan(EdgeWeightedGraph G, int v) {
    marked[v] = true;
    for (Edge e : G.adj(v)) {
        int w = e.other(v);
        if (marked[w]) continue;
        if (e.weight() < distTo[w]) {
            distTo[w] = e.weight();
            edgeTo[w] = e;
            if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
            else pq.insert(w, distTo[w]);
        }
    }
}

distTo不是source-to-vertex path distance；它只是一条从当前tree跨cut连接w的edge weight。每次 delMin 取到global best vertex connection，对应edge就是current cut的minimum crossing edge。Vertex进入tree后，其key永久settled。

每条edge被scan常数次，最多触发一次successful decrease per direction；binary heap的insert、decreaseKey、delMin均 $\log V$ ，因此time为 $O(E\log V)$ ，extra space为 $O(V)$ 。它与Lazy Prim得到相同MST weight；equal weights时具体tree可能因tie order不同。

Eager状态的验收重点不是PQ长短，而是对每个unmarked w验证：edgeTo[w]确实跨当前cut，并且其weight等于所有从marked side到w edges的minimum。若scan漏边或decreaseKey方向写反，算法可能仍输出spanning tree，却失去MST optimality。

4.3.7 Kruskal：按global weight order合并components

Kruskal算法（，Kruskal's algorithm）不增长单棵tree，而是让forest components并行合并。先将所有edges按weight放入MinPQ或排序，再用Union-Find判定两个endpoints是否已connected：

MinPQ<Edge> pq = new MinPQ<>();
for (Edge e : G.edges()) pq.insert(e);
 
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
    Edge e = pq.delMin();
    int v = e.either(), w = e.other(v);
    if (uf.find(v) == uf.find(w)) continue;
    uf.union(v, w);
    mst.enqueue(e);
    weight += e.weight();
}

若v与w属于不同components，取v所在component为S。当前forest没有edge跨这个cut，否则两components早已connected；由于所有更轻edges已处理，e是尚可用crossing edges中的minimum，所以cut property成立。若两端已connected，加入e会在该component内形成cycle，必须skip。

Sorting dominates，time为 $O(E\log E)$ ；weighted quick-union with path compression提供近常数amortized connectivity operations，space为 $O(V+E)$ （若edges已经按序流入，可降到forest与UF storage）。Kruskal特别适合edges可统一排序、graph sparse或需要观察component merging的场景。

4.3.8 三种实现的成本与选择

三种算法共享同一个correctness theorem，但保存候选集的方式不同：

algorithm	frontier state	stale candidate	main bound	extra space
Lazy Prim	所有见过的crossing edges	留到delMin丢弃	$O(E\log E)$	$O(E)$
Eager Prim	每个non-tree vertex一个best edge	decreaseKey替换	$O(E\log V)$	$O(V)$
Kruskal	全部edges按global weight	UF拒绝成环	$O(E\log E)$	$O(V+E)$

因为simple connected graph满足 $E\le V^2$ ，所以 $\log E\le 2\log V$ ，两个log bounds在asymptotic层面相近；实际差别来自PQ size、cache behavior、edge input形式与是否已有排序。Dense graph也可用array-based eager Prim做到 $O(V^2)$ ，避免heap overhead。

不要把运行后weight相同当成唯一验收。若同权重允许multiple MST，edge sets不同完全合法；若两实现weight不同，至少一个结果错误，或input/precision/tie comparison不一致。Floating-point weights应使用同一comparison contract，避免一个模块round后排序、另一个模块用raw double。

4.3.9 MST optimality：不信任构造过程，只检查certificate

MST最优性（，MST optimality）需要分两层：先证明是spanning tree，再证明它minimum。

结构检查：

所有candidate edges都来自G，weight一致。
用fresh Union-Find逐边加入，任何edge若连接已connected endpoints，则存在cycle。
最后所有vertices与0 connected，且candidate edge count为V-1。
重新求和并核对reported weight，不能只信缓存字段。

最优性检查：对candidate tree中的每条edge e，临时从tree移除e。剩余tree形成cut；扫描G全部edges，确认没有更轻edge跨这个cut。若存在f且 $w(f)\lt w(e)$ ，则 T - e + f 是更轻spanning tree，candidate不是MST。形式化为：

\forall e\in T,\quad w(e)=\min\{w(f): f\text{ crosses the cut induced by }T-e\}

这个certificate与构造算法独立：即使Prim/Kruskal实现内部state错了，validator仍可发现cycle、disconnection、weight mismatch或nonoptimal replacement。Naive validation对每条tree edge扫描所有graph edges，约 $O(VE)$ ，适合测试和小图；生产级可用path maximum queries等技术加速。

Cut certificate也解释edge sensitivity。若降低non-tree edge f的weight，它与tree path形成cycle；当f比该path上的maximum-weight tree edge更轻时，应交换进入MST。若提高tree edge e的weight，应在删除e形成的cut上重新寻找minimum crossing replacement。

4.3.10 手工运行与验收路线

小结

Minimum spanning trees在connected edge-weighted graph中，以V-1条无环edges覆盖全部vertices并最小化total weight。
Tree加边产生unique cycle，tree删边产生unique cut；这组二重性支撑exchange argument。
Cut property说明：对尊重current forest的cut，minimum crossing edge是safe edge。
Prim's algorithm固定tree/non-tree cut；Lazy版本容忍stale edges，Eager版本为每个non-tree vertex维护best connection。
Kruskal's algorithm按global weight order扫描，并用Union-Find拒绝same-component cycle edge。
MST optimality不能只看edge count或total weight；应先验证spanning-tree structure，再验证每条tree edge的cut minimum certificate。