最小生成樹算法深度解析：Prim 與 Kruskal 算法原理、證明與 Java 實現

最小生成樹（MST）基礎概念

給定一個**加權連通無向圖** G=(V, E)，最小生成樹是包含所有頂點、邊權重總和最小的**樹**（無環連通子圖）。MST 應用於網路佈線、電路設計、叢類分析等場景。

Prim 算法（普林姆算法）

核心思想：貪心擴展頂點集合

維護兩個集合：U（已納入 MST 的頂點）、V-U（未納入頂點）。每步從連接兩集合的邊中選**權重最小**的邊，將新頂點加入 U，直到 U = V。

詳細步驟

1. 任選起始頂點 x，U = {x}，E_new = ∅。
2. 重複直到 U 包含所有頂點：
    a. 在所有 u∈U, v∉U 的邊中選權重最小的 <u, v>。
    b. 將 v 加入 U，將 <u, v> 加入 E_new。
3. 輸出 U, E_new 為 MST。

圖示演示（權重和 = 39）

起點 D → 選 AD(5) → 選 DF(6) → 選 AB(7) → 選 BE(7) → 選 EC(5) → 選 EG(9)。最終包含所有 7 個頂點，總權重 39。

正確性證明（反證法）

1. 假設 Prim 產生的樹 G₀ 非最小，存在 G_min 使 cost(G_min) < cost(G₀)。
2. G_min 中必有邊 <u,v> ∉ G₀。將其加入 G₀ 形成環。
3. <u,v> 不是該環最長邊（因屬於 G_min），但 Prim 每步選最短邊，矛盾。
4. 故假設不成立，Prim 產生的必為 MST。

Kruskal 算法（克魯斯克爾算法）

核心思想：貪心選擇全局最小邊，避免成環

將所有邊按權重升序排列，依序檢查：若邊兩端點**不在同一連通分量**，則加入 MST；否則跳過（會成環）。使用**并查集（Union-Find）**高效判斷連通性。

詳細步驟

1. 輸入圖 G(V, E)，建立空圖 G_new(V, ∅)。
2. 所有邊按權重升序排序。
3. 遍歷排序後的邊：
    若邊 <u,v> 兩端點在 G_new 中不連通 → 加入 G_new。
    直到 G_new 連通（邊數 = |V|-1）。

圖示演示（同樣權重和 = 39）

排序邊：AD(5), CE(5), DF(6), AB(7), BE(7), BC(8), EF(8), BD(8), EG(9), FG(11)...
依序選 AD、CE、DF、AB、BE、EG（跳過 BC、EF、BD 因成環），最終形成 MST。

正確性證明（數學歸納法）

1. 基礎：n=1 顯然成立。
2. 歸納：假設 k 階圖成立。對 k+1 階圖 G，合併最短邊 <u,v> 端點得 k 階圖 G'。G' 的 MST 為 T'。證明 T' ∪ {<u,v>} 是 G 的 MST。反證：若存在更小 T，則 T-{<u,v>} 是 G' 的生成樹且權重 < T'，矛盾。

Java 實現：Prim 算法（鄰接矩陣/邊列表）

public class MinTreePrim {
    static class Vertex { String name; }
    static class Edge { Vertex u, v; int w; }
    static class Graph { Vertex[] vs; Edge[] es; int minWeight; }

    private static List visited = new ArrayList<>();
    private static List unvisited = new ArrayList<>();
    private static List mstEdges = new ArrayList<>();

    public static void prim(Graph g) {
        visited.add(g.vs[0]); unvisited.remove(g.vs[0]);
        while (!unvisited.isEmpty()) {
            Edge minEdge = null; Vertex next = null; int minW = Integer.MAX_VALUE;
            for (Vertex u : visited) {
                for (Vertex v : unvisited) {
                    for (Edge e : g.es) {
                        if ((e.u == u && e.v == v) || (e.u == v && e.v == u)) {
                            if (e.w < minW) { minW = e.w; minEdge = e; next = v; }
                        }
                    }
                }
            }
            visited.add(next); unvisited.remove(next);
            mstEdges.add(minEdge); g.minWeight += minW;
        }
        // 輸出結果...
    }
}

優化提示：稠密圖用鄰接矩陣 + 優先隊列可達 O(E log V)；稀疏圖 Kruskal + 并查集更優。

兩算法對比與選型指南

擴展應用

• 次小生成樹：枚舉 MST 中每條邊，刪除後重新求 MST 取最小者。
• 最小瓶頸生成樹：MST 即為最小瓶頸樹（最大邊權最小）。
• 有向圖 MST：Chu-Liu/Edmonds 算法。