【数据结构与算法体系】之图算法（二）-最小生成树

一、问题定义与基本概念

1.1 生成树的数学定义

给定连通无向带权图 $G = (V, E)$，其中每条边 $(u, v)$ 有权重 $w(u, v) \in \mathbb{R}$。生成树（Spanning Tree） 是 $G$ 的一个子图 $T = (V, E_T)$，满足 $|E_T| = |V| - 1$ 且 $T$ 是连通的（即 $T$ 是一棵树，连通且无环）。

最小生成树（Minimum Spanning Tree, MST） 问题：在所有生成树中，找到使得总权重最小的一棵：

$$T^* = \arg\min_{T \text{ is spanning tree}} \sum_{e \in E_T} w(e)$$

注意：MST 可能不唯一（当存在多条权重相同的边时），但所有 MST 的边权多重集是相同的。

1.2 贪心策略的直觉

MST 是贪心算法最经典的应用之一。贪心直觉：在每一步选择当前可用且不形成环的最小权重边。这依赖于 MST 的割性质（Cut Property）和环性质（Cycle Property），它们共同保证贪心选择的正确性。

二、割性质与环性质（核心理论）

2.1 割性质（Cut Property）

定理（割性质）：设 $S \subset V$ 是顶点的任意非空真子集。考虑横跨割 $(S, V \setminus S)$ 的所有边，其中权重最小的边 $e$ 必定属于某棵 MST。

证明（交换论证法）：设 $e = (u, v)$ 是横跨割 $(S, V \setminus S)$ 的最小权重边（$u \in S, v \notin S$）。设 $T^*$ 是任意一棵 MST。

若 $e \in T^*$，则命题成立。
若 $e \notin T^*$，则 $T^* \cup {e}$ 包含唯一的一个环 $C$。由于 $e$ 横跨割，环 $C$ 必定包含至少另一条横跨割的边 $f$（$f \neq e$）。由割性质的前提，$w(e) \leq w(f)$。

构造 $T’ = (T^* \setminus {f}) \cup {e}$。$T’$ 仍然是一棵生成树（删去环上的一条边，加入 $e$，连通性保持且边数不变）。且：

$$w(T’) = w(T^*) - w(f) + w(e) \leq w(T^*)$$

由于 $T^*$ 是 MST，$w(T’) \geq w(T^*)$，故 $w(T’) = w(T^*)$，即 $T’$ 也是 MST。因此 $e$ 属于某棵 MST。$\square$

2.2 环性质（Cycle Property）

定理（环性质）：设 $C$ 是图 $G$ 中的任意环，$e$ 是 $C$ 上权重最大的边。则 $e$ 不属于任何 MST。

证明：反设 $e$ 属于某棵 MST $T^*$。删去 $e$ 将 $T^*$ 分裂为两个连通分量。由于 $e$ 在环 $C$ 中，$C$ 上存在另一条边 $f$（$f \neq e$）连接这两个连通分量。且 $w(f) \leq w(e)$（因为 $e$ 是环上最大权重的边）。

构造 $T’ = (T^* \setminus {e}) \cup {f}$。$T’$ 仍是生成树，且 $w(T’) = w(T^*) - w(e) + w(f) < w(T^*)$（严格小于，若 $w(f) < w(e)$）或 $w(T’) = w(T^*)$。若 $w(f) < w(e)$，则 $T^*$ 不是 MST，矛盾。若 $w(f) = w(e)$，$e$ 被 $f$ 替代后仍得 MST，原命题”$e$ 不属于任何 MST”在存在严格最大边时成立。$\square$

2.3 贪心算法的通用框架

任何满足以下规则的算法都能构造 MST：

GENERIC-MST(G):
    A = ∅  // 当前已选边集
    while A 不构成生成树:
        找到一个割(S, V\S)，使得A中没有边横跨此割
        选择横跨该割的最小权重边e
        A = A ∪ {e}
    return A

Prim 和 Kruskal 都遵循这个框架，只是选择割的方式不同：

Prim：维护一个不断增长的连通分量 $S$，割为 $(S, V \setminus S)$
Kruskal：按权重升序考虑每条边，每条边定义了一个由”已连接顶点”隐式形成的割

三、Prim 算法

3.1 算法思想

Prim 算法从任意起始顶点开始，维护一个逐步生长的”树”（已选顶点集合 $S$）。每一步，选择连接 $S$ 与 $V \setminus S$ 的最小权重边，将对应顶点加入 $S$。这是割性质的直接应用。

PRIM(G, r):
    for each v in V:
        key[v] = ∞; parent[v] = null; inTree[v] = false
    key[r] = 0
    while 存在不在树中的顶点:
        u = EXTRACT-MIN(key) // 选择key最小的未加入顶点
        inTree[u] = true
        for each neighbor v of u:
            if not inTree[v] and w(u,v) < key[v]:
                key[v] = w(u,v); parent[v] = u

3.2 Lazy Prim — $O(E \log E)$

“懒惰”版本在每次更新 key 时直接向优先队列中插入新的（key, vertex）对，而不删除旧的。当旧的（较大 key 的）记录出队时，通过 inTree 标记跳过。

import java.util.*;

class LazyPrim {
    static class Edge implements Comparable<Edge> {
        int to, weight;
        Edge(int t, int w) { to = t; weight = w; }
        public int compareTo(Edge o) { return Integer.compare(weight, o.weight); }
    }
    
    public static List<int[]> prim(List<Edge>[] graph, int n) {
        boolean[] inTree = new boolean[n];
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        
        // 优先队列存储候选边：(权重, 目的顶点)
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        // 从顶点0开始
        pq.offer(new int[]{0, 0}); // (权重, 顶点)
        
        int edgesTaken = 0;
        List<int[]> mst = new ArrayList<>();
        
        while (!pq.isEmpty() && edgesTaken < n) {
            int[] cur = pq.poll();
            int weight = cur[0], v = cur[1];
            
            if (inTree[v]) continue; // 懒惰删除：该顶点已在树中
            inTree[v] = true;
            edgesTaken++;
            
            if (edgesTaken > 1) { // 第一个顶点(起始点)没有父边
                mst.add(new int[]{parent[v], v, weight});
            }
            
            for (Edge e : graph[v]) {
                if (!inTree[e.to]) {
                    parent[e.to] = v;
                    pq.offer(new int[]{e.weight, e.to});
                }
            }
        }
        return mst;
    }
}

复杂度分析：每个顶点最多将其所有邻居边插入优先队列，共 $O(E)$ 次 offer 操作。每次 poll 为 $O(\log E)$。总时间 $O(E \log E) = O(E \log V)$（因为 $E = O(V^2)$，$\log E = O(\log V)$）。优先队列最多包含 $O(E)$ 条记录，空间 $O(V + E)$。

懒惰版本的缺点：队列中可能堆积大量”过期”的边（一个顶点通过多条边被多次插入，只有最小 key 的有效）。在稠密图（$E \approx V^2$）上内存开销大。

3.3 Eager Prim — $O(E \log V)$ with Indexed Priority Queue

“饥饿”版本维护一个索引优先队列（Indexed Priority Queue），每个顶点在队列中只有一个条目。当发现更小的 key[v] 时，不插入新记录，而是原地更新（decreaseKey）。

// 索引优先队列（Indexed Priority Queue / Indexed Min Heap）
class IndexedPQ {
    int[] heap;      // heap[i] = 顶点编号
    int[] pos;       // pos[v] = 顶点v在heap中的位置
    int[] keys;      // keys[v] = 顶点v当前的key值
    int size;
    
    public IndexedPQ(int n) {
        heap = new int[n];
        pos = new int[n];
        keys = new int[n];
        Arrays.fill(pos, -1);
        Arrays.fill(keys, Integer.MAX_VALUE);
        size = 0;
    }
    
    public void insert(int v, int key) {
        pos[v] = size;
        heap[size] = v;
        keys[v] = key;
        swim(size);
        size++;
    }
    
    public void decreaseKey(int v, int newKey) {
        if (newKey >= keys[v]) return;
        keys[v] = newKey;
        swim(pos[v]); // key减小，可能需要上浮
    }
    
    public int extractMin() {
        int min = heap[0];
        swap(0, size - 1);
        size--;
        sink(0);
        pos[min] = -1;
        return min;
    }
    
    public boolean isEmpty() { return size == 0; }
    public boolean contains(int v) { return pos[v] != -1; }
    
    private void swim(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (keys[heap[i]] >= keys[heap[parent]]) break;
            swap(i, parent);
            i = parent;
        }
    }
    
    private void sink(int i) {
        while (true) {
            int left = 2 * i + 1, right = 2 * i + 2, smallest = i;
            if (left < size && keys[heap[left]] < keys[heap[smallest]]) smallest = left;
            if (right < size && keys[heap[right]] < keys[heap[smallest]]) smallest = right;
            if (smallest == i) break;
            swap(i, smallest);
            i = smallest;
        }
    }
    
    private void swap(int i, int j) {
        int tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp;
        pos[heap[i]] = i; pos[heap[j]] = j;
    }
}

class EagerPrim {
    static class Edge { int to, weight; Edge(int t, int w) { to = t; weight = w; } }
    
    public static List<int[]> prim(List<Edge>[] graph, int n) {
        boolean[] inTree = new boolean[n];
        int[] parent = new int[n];
        int[] key = new int[n];
        Arrays.fill(parent, -1);
        Arrays.fill(key, Integer.MAX_VALUE);
        
        IndexedPQ pq = new IndexedPQ(n);
        key[0] = 0;
        pq.insert(0, 0);
        
        List<int[]> mst = new ArrayList<>();
        
        while (!pq.isEmpty()) {
            int v = pq.extractMin();
            inTree[v] = true;
            
            if (parent[v] != -1) {
                mst.add(new int[]{parent[v], v, key[v]});
            }
            
            for (Edge e : graph[v]) {
                if (!inTree[e.to] && e.weight < key[e.to]) {
                    key[e.to] = e.weight;
                    parent[e.to] = v;
                    if (pq.contains(e.to)) {
                        pq.decreaseKey(e.to, e.weight);
                    } else {
                        pq.insert(e.to, e.weight);
                    }
                }
            }
        }
        return mst;
    }
}

复杂度分析：

insert 和 decreaseKey：$O(\log V)$（堆的 swim 操作）
extractMin：$O(\log V)$
每个顶点恰好被 extract 一次，每条边触发一次 decreaseKey/insert
总时间：$O((V + E) \log V) = O(E \log V)$

Prim 两种实现的对比：

┌─────────────┬──────────────────┬──────────────────┐
│   实现       │   Lazy Prim      │   Eager Prim     │
├─────────────┼──────────────────┼──────────────────┤
│ 数据结构     │ PriorityQueue    │ IndexedPQ        │
│ PQ操作      │ offer (不更新)    │ decreaseKey      │
│ 时间        │ O(E log E)       │ O(E log V)       │
│ 空间        │ O(E)             │ O(V)             │
│ 稠密图      │ 内存大,可行       │ 更优             │
│ 稀疏图      │ 可行              │ 略微复杂         │
│ 实现难度    │ 简单              │ 中等             │
└─────────────┴──────────────────┴──────────────────┘

3.4 Dense Prim — $O(V^2)$ for Adjacency Matrix

当图用邻接矩阵表示且 $E \approx V^2$ 时，朴素的 $O(V^2)$ Prim 实际上比基于堆的实现更快（省去堆操作的 $\log V$ 开销）。

int primDense(int[][] graph, int n) {
    boolean[] inTree = new boolean[n];
    int[] key = new int[n];
    int[] parent = new int[n];
    Arrays.fill(key, Integer.MAX_VALUE);
    key[0] = 0;
    
    int totalWeight = 0;
    for (int i = 0; i < n; i++) {
        // 从key中选择最小值（未加入树的顶点）
        int u = -1, minKey = Integer.MAX_VALUE;
        for (int v = 0; v < n; v++) {
            if (!inTree[v] && key[v] < minKey) {
                minKey = key[v];
                u = v;
            }
        }
        if (u == -1) break; // 图不连通
        
        inTree[u] = true;
        totalWeight += minKey;
        
        // 更新邻居的key
        for (int v = 0; v < n; v++) {
            if (!inTree[v] && graph[u][v] != 0 && graph[u][v] < key[v]) {
                key[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }
    return totalWeight;
}

时间复杂度：$O(V^2)$。当 $E = \Theta(V^2)$ 时，$O(V^2)$ 与 $O(E \log V) = O(V^2 \log V)$ 相比，朴素版本快了 $\log V$ 倍。

四、Kruskal 算法

4.1 算法思想

Kruskal 算法将所有边按权重升序排序，然后依次考虑每条边：如果该边连接的两个顶点当前不在同一个连通分量中（即加入该边不会形成环），则将其加入 MST。

Kruskal 可以看作割性质的”延迟”版本：当考虑边 $(u, v)$ 时，$u$ 和 $v$ 分属不同的连通分量 $C_u$ 和 $C_v$。此时 $(C_u, V \setminus C_u)$ 是一个割，而 $(u, v)$ 是该割上所有未考虑边中权重最小的（因为边是按权重升序处理的）。

4.2 并查集（Union-Find）集成

class Kruskal {
    static class Edge implements Comparable<Edge> {
        int u, v, weight;
        Edge(int _u, int _v, int _w) { u = _u; v = _v; weight = _w; }
        public int compareTo(Edge o) { return Integer.compare(weight, o.weight); }
    }
    
    // 并查集（路径压缩 + 按秩合并）
    static class UnionFind {
        int[] parent, rank;
        UnionFind(int n) { 
            parent = new int[n]; rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
            return parent[x];
        }
        boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false; // 已在同一集合中
            if (rank[rx] < rank[ry]) { parent[rx] = ry; }
            else if (rank[rx] > rank[ry]) { parent[ry] = rx; }
            else { parent[ry] = rx; rank[rx]++; }
            return true; // 合并成功
        }
    }
    
    public static List<Edge> kruskal(List<Edge> edges, int n) {
        Collections.sort(edges);
        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();
        
        for (Edge e : edges) {
            if (uf.union(e.u, e.v)) {
                mst.add(e);
                if (mst.size() == n - 1) break; // MST完成
            }
        }
        return mst.size() == n - 1 ? mst : null; // null表示不连通
    }
}

4.3 复杂度分析

排序：$O(E \log E) = O(E \log V)$
并查集操作：每条边进行 2 次 find 和至多 1 次 union，总计 $O(E \cdot \alpha(V))$，其中 $\alpha$ 是反 Ackermann 函数（可视为常数 $< 5$）
总时间：$O(E \log E)$，由排序主导
空间：$O(V + E)$

Kruskal 的优势：当图用邻接表存储且 $E$ 较小时，排序的 $O(E \log E)$ 开销可接受。对于大规模稀疏图（$E = O(V)$），Kruskal 非常高效。

4.4 示例演算

考虑加权图（顶点 0-6）：

(0,1,w=7)  (1,2,w=8)  (0,3,w=5)  (1,3,w=9)
(1,4,w=7)  (2,4,w=5)  (3,4,w=15) (3,5,w=6)
(4,5,w=8)  (4,6,w=9)  (5,6,w=11)

按权重排序后：[(0,3,5),(2,4,5),(3,5,6),(0,1,7),(1,4,7),(1,2,8),(4,5,8),(1,3,9),(4,6,9),(5,6,11),(3,4,15)]

处理过程：

(0,3,5): union(0,3) ✓ → MST: {(0,3)}
(2,4,5): union(2,4) ✓ → MST: {(0,3), (2,4)}
(3,5,6): union(3,5) ✓ → MST: {(0,3), (2,4), (3,5)}
(0,1,7): union(0,1) ✓ → MST: {(0,3), (2,4), (3,5), (0,1)}
(1,4,7): union(1,4) ✓ → MST: {(0,3), (2,4), (3,5), (0,1), (1,4)}
(1,2,8): find(1)==find(2) → skip（形成环）
(4,6,9): union(4,6) ✓ → MST 完成（6 条边 = 7-1）

总权重 = 5+5+6+7+7+9 = 39。

五、Boruvka 算法

5.1 算法思想

Boruvka 算法（1926）是最早的 MST 算法。每轮迭代中，每个连通分量独立选择其出边中权重最小的一条，然后合并所有选中的边（处理可能形成环的情况）。

算法步骤：

初始时每个顶点是一个独立的连通分量
每轮：对每个分量，找到连接该分量与另一个分量的最小权重边
将所有选中边加入 MST，合并分量
重复直到只剩一个分量

5.2 完整实现

class Boruvka {
    static class Edge { int u, v, w; Edge(int u, int v, int w) { this.u = u; this.v = v; this.w = w; } }
    
    public static List<Edge> boruvka(List<Edge> edges, int n) {
        UnionFind uf = new UnionFind(n);
        List<Edge> mst = new ArrayList<>();
        int components = n;
        
        while (components > 1) {
            // 为每个分量找最小出边
            Edge[] cheapest = new Edge[n]; // cheapest[c] = 分量c的最小出边
            
            for (Edge e : edges) {
                int compU = uf.find(e.u);
                int compV = uf.find(e.v);
                if (compU == compV) continue; // 同分量，跳过
                
                if (cheapest[compU] == null || e.w < cheapest[compU].w)
                    cheapest[compU] = e;
                if (cheapest[compV] == null || e.w < cheapest[compV].w)
                    cheapest[compV] = e;
            }
            
            // 添加最小出边并合并
            boolean anyMerged = false;
            for (int c = 0; c < n; c++) {
                Edge e = cheapest[c];
                if (e != null && uf.find(e.u) != uf.find(e.v)) {
                    uf.union(e.u, e.v);
                    mst.add(e);
                    components--;
                    anyMerged = true;
                }
            }
            
            if (!anyMerged) break; // 无法继续合并（图不连通）
        }
        
        return components == 1 ? mst : null;
    }
}

5.3 复杂度与适用场景

每轮迭代分量数至少减半（最坏情况下分量成对合并），因此最多 $O(\log V)$ 轮。每轮扫描所有边，$O(E)$。总时间 $O(E \log V)$。

Boruvka 在现代应用中似乎不如 Prim 和 Kruskal 常用，但在并行环境下非常出色——每轮各分量的最小出边选择可以完全并行化。这也是它为何能在MapReduce/Hadoop框架中高效实现的原因。

六、MST 算法的全面对比

┌─────────────────┬──────────┬──────────┬──────────┬──────────────┐
│     算法         │  Prim    │  Kruskal │ Boruvka  │   Dense Prim │
│                 │(Eager)   │          │          │   (朴素)      │
├─────────────────┼──────────┼──────────┼──────────┼──────────────┤
│ 时间复杂度       │O(E log V)│O(E log E)│O(E log V)│  O(V²)       │
│ 空间复杂度       │O(V)      │O(V)      │O(V)      │  O(V²)       │
│ 数据结构         │IndexedPQ │UnionFind │UnionFind │  Adj Matrix  │
│ 推荐图类型       │边列表图  │边列表图  │并行/分布 │  稠密图      │
│ 在线/离线       │在线      │离线(排序)│离线      │  在线        │
│ 可并行性         │差        │中等      │好        │  差          │
│ 实现难度         │中等      │简单      │中等      │  简单        │
└─────────────────┴──────────┴──────────┴──────────┴──────────────┘

选择建议：

稠密图（$E \approx V^2$）：朴素 Prim $O(V^2)$ > Eager Prim $O(E \log V)$
稀疏图（$E = O(V)$）：Kruskal 或 Eager Prim 接近 $O(V \log V)$
需要在线增量计算：Prim（可以自然地处理新加入的顶点）
分布式/并行环境：Boruvka
竞技编程（代码量最小）：Kruskal（只需 sort + Union-Find）

七、实际应用

7.1 网络设计（Network Design）

最经典的应用场景。铺设光缆连接 $n$ 个城市，城市间有不同的铺设成本（距离、地形等）。MST 给出总成本最小的连接方案（确保所有城市互联）。可以是物理网络（电力网、水管网、通信基站布局）或逻辑网络（广播树、组播路由）。

7.2 聚类（Single-Linkage Clustering）

单链聚类（层次聚类的一种变体）：将 $n$ 个数据点视为完全图的顶点，两点间的边权为它们的距离（如欧几里得距离）。构造该图的 MST 后，去掉 MST 中权重最大的 $k-1$ 条边，即可得到 $k$ 个聚类。

直觉：MST 中边权表示合并两个聚类的”最小成本”。去掉最大边等同于拒绝代价最高的合并。这种方法能自然地发现非球状的簇。

// 单链聚类：从MST获取k个聚类
List<List<Integer>> clusterFromMST(List<int[]> mst, int n, int k) {
    // 按权重大小降序排列MST边
    mst.sort((a, b) -> b[2] - a[2]);
    
    UnionFind uf = new UnionFind(n);
    // 添加最小的n-k条边（即忽略最大的k-1条）
    int edgesToUse = n - k;
    for (int i = mst.size() - 1; i >= 0 && edgesToUse > 0; i--, edgesToUse--) {
        uf.union(mst.get(i)[0], mst.get(i)[1]);
    }
    
    // 按分量收集
    Map<Integer, List<Integer>> clusters = new HashMap<>();
    for (int v = 0; v < n; v++) {
        int root = uf.find(v);
        clusters.computeIfAbsent(root, x -> new ArrayList<>()).add(v);
    }
    return new ArrayList<>(clusters.values());
}

7.3 图像分割（Image Segmentation）

Felzenszwalb-Huttenlocher 算法将图像分割问题转化为图划分问题，其中 MST 的思想被用于定义区域内的”内部差异”和区域间的”外部差异”。若两个相邻区域间的外部差异小于各自的内部差异，则合并这两个区域。本质上是一种自适应的 MST 阈值分割。

7.4 近似 TSP（Traveling Salesman Problem）

MST 启发式：对任意度量空间的 TSP 实例，MST 的权重 ≤ TSP 最优值的权重（因为从 TSP 最优环中删去一条边就得到一棵生成树）。利用 MST 可以在多项式时间内构造一个 $\leq 2\cdot OPT$ 的近似解：构造 MST → DFS 遍历（每条边访问两次）→ Shortcut 跳过重复顶点。

八、MST 的唯一性

定理：若图中所有边的权重互不相同，则 MST 唯一。

证明：反设存在两个不同的 MST $T_1 \neq T_2$。令 $e$ 为在 $T_1 \setminus T_2$ 中权重最小的边。将 $e$ 加入 $T_2$ 形成环，该环上至少有一条边 $f$ 属于 $T_2 \setminus T_1$。由选择 $e$ 的方式，$w(e) < w(f)$（严格小于，因为所有权重互异且 $e$ 在 $T_1 \setminus T_2$ 中最小）。在 $T_2$ 中用 $e$ 替换 $f$ 得到更小的生成树，矛盾。$\square$

推论：当权重可以相同时，MST 不唯一。但对所有 MST，各权重值出现的次数相同（即边权多重集唯一）。

九、面试常见追问

问题一：Prim 和 Kruskal 各适合什么场景？能否给出一个 Prim 比 Kruskal 显著快的例子？

回答：当图是稠密图（$E \approx V^2$）且用邻接矩阵存储时，朴素 Prim 的 $O(V^2)$ 显著快于 Kruskal 的 $O(E \log E) = O(V^2 \log V)$。例如 $V = 10^4$ 的完全图（$E \approx 5 \times 10^7$）：朴素 Prim 需要 $10^8$ 次操作（常数小，仅整数比较），而 Kruskal 需要排序 $5 \times 10^7$ 条边（内存可能放不下）。

反过来，当图非常稀疏（$E = O(V)$），且边已经在一个列表中时，Kruskal 的 $O(V \log V)$ 排序开销完全可以接受，且代码更简洁。

问题二：如何找到”次小生成树”（Second MST）？

回答：次小生成树可以通过枚举法构造：

先求出 MST $T$（$n-1$ 条边）
对 $T$ 中的每条边 $e$，暂时从图中删除 $e$，求剩余图的 MST
所有这些 MST 中最小的那个即为次小生成树

时间复杂度 $O(V \cdot T_{\text{MST}})$，其中 $T_{\text{MST}}$ 是单次 MST 算法的时间。更高效的做法是预处理”对于 MST 中任意两点，MST 路径上的最大边权”，然后对于每条非 MST 边 $(u, v)$，尝试用它替换 MST 中 $u$ 到 $v$ 路径上的最大边，找到最小的替换增量。这可以做到 $O(E \log V)$ 或 $O(V^2)$。

问题三：MST 是否一定包含了图中最短路径的边？即，任意两点间的 MST 路径是否一定是它们在图中的最短路径？

回答：不是。 MST 最小化的是所有边的总权重，而不保证任意两点间路径最短。经典反例：考虑一个三角形 (A-B 权 2, B-C 权 2, A-C 权 3)。MST 是 {A-B, B-C}（总权 4），但 A 到 C 的最短路径是直接的边 A-C（权 3），而 MST 路径 A-B-C 的权重是 4 > 3。

补充概念：最小生成树与最短路径树的根本区别在于目标函数不同。前者最小化 $\sum_{e \in T} w(e)$，后者最小化 $\sum_{v \in V} d(s, v)$。它们仅在特殊情况下一致（如树形图本身）。

问题四：如果图中存在负权边，MST 算法还正确吗？

回答：是的，Prim、Kruskal 和 Boruvka 都正确处理带负权的边。所有算法依赖于割性质的相对排序（”最小权重”），而非权的绝对大小。负权边只是相对其他边更小，被优先选中，这与算法的贪心逻辑一致。但需注意：如果图连通且所有边权为负，MST 仍然是存在的（选择绝对值最大的负权边 = 即权重最小的边）。

问题五：如何利用 Kruskal 算法判断图的连通性？

回答：在 Kruskal 执行结束后，如果 MST 中的边数 $< n-1$，说明图不是连通的，且并查集中所有 find(x) 值相同的顶点属于同一个连通分量。

十、总结

最小生成树问题是图论的经典问题，也是贪心算法正确性的典范。三个核心要点：

割性质是所有 MST 算法的共同理论基础，证明干净漂亮（交换论证法）
Prim 维护一棵生长的树（适合稠密图），Kruskal 按权重排序合并分量（适合稀疏图），Boruvka 适合并行环境
实际应用中，MST 不仅是网络连接问题的基础，更延伸到聚类、图像分割等看似不相关的领域

掌握了 MST 的割性质和交换论证法，你其实也掌握了证明许多其他贪心算法正确性的通用技术。本系列的下一篇文章将讨论【数据结构与算法体系】之图算法（三）-单源最短路径，在那里你将看到贪心策略在不同目标函数下的另一番精彩应用。