圖論與網絡優化中，最小生成樹（Minimum Spanning Tree，MST）是一類重要問題，它能在連接所有節點的前提下，找到總權重最小的邊集合，廣泛應用于通信網絡布線、管道鋪設、電路設計等場景（核心需求是“用最少成本連接所有節點”）。

一、最小生成樹基礎概念

1.1 生成樹與最小生成樹

• 生成樹：對于一個有 n 個節點的連通圖，生成樹是包含所有 n 個節點且恰好有 n-1 條邊的子圖，且子圖中無環（保證連通性的同時無冗余邊）。
• 最小生成樹：在帶權連通圖中，所有生成樹中總邊權之和最小的生成樹稱為最小生成樹。

1.2 核心性質

• 連通性：包含原圖所有節點，任意兩點之間有且僅有一條路徑。
• 無環性：恰好有 n-1 條邊，若再添加一條邊必形成環。
• 最小性：總邊權之和在所有可能的生成樹中最小。

1.3 應用場景

• 通信網絡布線：用最少的線纜連接所有城市。
• 電路設計：在芯片中用最短的導線連接所有元件。
• 管道鋪設：以最低成本修建管道連接所有工廠。
• 聚類分析：通過最小生成樹的邊權劃分數據簇。

二、Prim 算法：從頂點出發的“生長式”構建

Prim 算法的核心是“從一個起點開始，逐步添加邊以連接新節點，始終保持子圖無環且總權最小”。

2.1 算法原理

1. 初始化：

   • 選擇任意節點作為起點（如節點 0），標記為“已加入生成樹”。
   • 維護一個 lowCost 數組：lowCost[i] 表示未加入生成樹的節點 i 與生成樹中節點的最小邊權（若無邊連接則為 +∞）。

2. 迭代選擇：

   • 從 lowCost 中選擇權值最小的邊，對應節點 u 加入生成樹。
   • 更新 lowCost 數組：對所有未加入生成樹的節點 v，若邊 u-v 的權值小于 lowCost[v]，則更新 lowCost[v] 為該權值（因為 u 已加入生成樹，v 到生成樹的最小邊可能變為 u-v）。

3. 終止條件：

   • 當生成樹包含所有 n 個節點（共選擇 n-1 條邊），算法結束。
     

2.2 Java 代碼實現（鄰接矩陣版）

public class PrimMST {// 鄰接矩陣：graph[i][j]表示邊i-j的權值，0表示無直接連接public int[] prim(int[][] graph) {int n = graph.length;int[] parent = new int[n]; // parent[i]記錄生成樹中i的父節點（用于還原樹）int[] lowCost = new int[n]; // 未加入節點到生成樹的最小邊權boolean[] inMST = new boolean[n]; // 標記節點是否已加入生成樹// 初始化：起點為0lowCost[0] = 0;parent[0] = -1; // 起點無父節點for (int i = 1; i < n; i++) {lowCost[i] = graph[0][i] == 0 ? Integer.MAX_VALUE : graph[0][i];parent[i] = 0;}inMST[0] = true;// 共需要加入n-1個節點for (int count = 1; count < n; count++) {// 步驟1：選擇lowCost中權值最小的未加入節點uint u = -1;int min = Integer.MAX_VALUE;for (int i = 0; i < n; i++) {if (!inMST[i] && lowCost[i] < min) {min = lowCost[i];u = i;}}if (u == -1) {// 圖不連通，無法生成MSTreturn null;}inMST[u] = true; // 加入生成樹// 步驟2：更新lowCost數組for (int v = 0; v < n; v++) {if (!inMST[v] && graph[u][v] != 0 && graph[u][v] < lowCost[v]) {lowCost[v] = graph[u][v];parent[v] = u;}}}return parent; // parent數組記錄生成樹的邊（v-parent[v]）}// 測試public static void main(String[] args) {// 鄰接矩陣表示帶權圖（0表示無邊）int[][] graph = {{0, 2, 0, 6, 0},{2, 0, 3, 8, 5},{0, 3, 0, 0, 7},{6, 8, 0, 0, 9},{0, 5, 7, 9, 0}};PrimMST prim = new PrimMST();int[] parent = prim.prim(graph);if (parent != null) {System.out.println("Prim生成樹的邊（子節點-父節點）：");int totalWeight = 0;for (int i = 1; i < parent.length; i++) {int weight = graph[i][parent[i]];System.out.println(i + "-" + parent[i] + "（權值：" + weight + "）");totalWeight += weight;}System.out.println("總權值：" + totalWeight); // 輸出16（2+3+5+6）} else {System.out.println("圖不連通，無法生成生成樹");}}
}

2.3 復雜度分析

• 鄰接矩陣實現：時間復雜度為 O(n2)（n 為節點數），適合稠密圖（邊數接近 n2）。
• 鄰接表+優先隊列：優化后時間復雜度為 O(m log n)（m 為邊數），適合稀疏圖。
• 空間復雜度：O(n)（存儲 lowCost、parent 等數組）。

三、Kruskal 算法：按邊權排序的“選邊式”構建

Kruskal 算法的核心是“按邊權從小到大選擇邊，避免形成環，直到連接所有節點”。

3.1 算法原理

1. 初始化：

   • 將所有邊按權值從小到大排序。
   • 初始化并查集（Union-Find）：每個節點各自為一個集合（用于檢測環）。
   • 維護一個邊集合，用于存儲生成樹的邊。

2. 選邊與合并：

   • 按排序后的順序遍歷邊 (u, v)：
     • 若 u 和 v 不在同一個集合（無環），則將該邊加入生成樹，并合并 u 和 v 所在的集合。
     • 若 u 和 v 在同一個集合（會形成環），則跳過該邊。

3. 終止條件：

   • 當生成樹的邊數達到 n-1（連接所有節點），算法結束。
     

3.2 Java 代碼實現（并查集+邊排序）

import java.util.*;// 邊的表示（起點，終點，權值）
class Edge implements Comparable<Edge> {int u, v, weight;public Edge(int u, int v, int weight) {this.u = u;this.v = v;this.weight = weight;}@Overridepublic int compareTo(Edge other) {return Integer.compare(this.weight, other.weight); // 按權值升序排序}
}// 并查集（用于檢測環）
class UnionFind {private int[] parent;public UnionFind(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i; // 初始化：每個節點的父節點是自己}}// 查找根節點（帶路徑壓縮）public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]); // 路徑壓縮：縮短后續查找路徑}return parent[x];}// 合并兩個集合（按秩合并優化）public boolean union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX == rootY) {return false; // 已在同一集合（會形成環）}parent[rootY] = rootX; // 合并return true;}
}public class KruskalMST {public List<Edge> kruskal(int n, List<Edge> edges) {List<Edge> mst = new ArrayList<>();UnionFind uf = new UnionFind(n);// 步驟1：按權值從小到大排序邊Collections.sort(edges);// 步驟2：遍歷邊，選邊并避免環for (Edge edge : edges) {if (mst.size() == n - 1) {break; // 已選夠n-1條邊，生成樹完成}int u = edge.u;int v = edge.v;if (uf.union(u, v)) { // 若u和v不在同一集合（無環）mst.add(edge);}}// 若邊數不足n-1，說明圖不連通return mst.size() == n - 1 ? mst : null;}// 測試public static void main(String[] args) {int n = 5; // 5個節點List<Edge> edges = new ArrayList<>();edges.add(new Edge(0, 1, 2));edges.add(new Edge(0, 3, 6));edges.add(new Edge(1, 2, 3));edges.add(new Edge(1, 3, 8));edges.add(new Edge(1, 4, 5));edges.add(new Edge(2, 4, 7));edges.add(new Edge(3, 4, 9));KruskalMST kruskal = new KruskalMST();List<Edge> mst = kruskal.kruskal(n, edges);if (mst != null) {System.out.println("Kruskal生成樹的邊：");int totalWeight = 0;for (Edge edge : mst) {System.out.println(edge.u + "-" + edge.v + "（權值：" + edge.weight + "）");totalWeight += edge.weight;}System.out.println("總權值：" + totalWeight); // 輸出16（2+3+5+6）} else {System.out.println("圖不連通，無法生成生成樹");}}
}

3.3 復雜度分析

• 時間復雜度：O(m log m)（主要來自邊的排序，m 為邊數），適合稀疏圖（邊數少）。
• 空間復雜度：O(n + m)（存儲邊、并查集等）。

四、兩種算法的對比與選擇

特性	Prim 算法	Kruskal 算法
核心思想	從節點出發，生長式擴展	從邊出發，選邊式構建
關鍵數據結構	鄰接矩陣/優先隊列	并查集+排序邊
時間復雜度	稠密圖 O(n2)，稀疏圖 O(m log n)	O(m log m)（依賴邊排序）
適用場景	稠密圖（邊多節點少）	稀疏圖（邊少節點多）
優勢	無需排序邊，適合節點少的圖	邊排序后邏輯簡單，適合邊少的圖

五、最小生成樹的應用與拓展

5.1 經典應用

• 次小生成樹：在最小生成樹基礎上，替換一條邊得到的總權值次小的生成樹，用于容錯設計（某條邊失效時的備用方案）。
• 多源最小生成樹：連接多個起點的最小生成樹，適用于“多中心網絡”設計（如多個數據中心連接所有城市）。

5.2 實際問題中的優化

• 帶限制的最小生成樹：如“最多使用 k 條某類邊”，可在選邊時添加約束。
• 動態圖的最小生成樹：當圖中邊權或節點動態變化時，高效更新生成樹（避免重新計算）。

總結
最小生成樹是解決“低成本連接所有節點”問題的核心工具，Prim 和 Kruskal 是兩種經典實現：

• Prim 適合稠密圖，通過“生長式”擴展節點，用 lowCost 數組跟蹤最小邊。
• Kruskal 適合稀疏圖，通過“選邊式”添加邊，用并查集避免環。
  實際應用中，需根據圖的稠密程度選擇算法：稠密圖優先用 Prim（鄰接矩陣實現），稀疏圖優先用 Kruskal（邊排序+并查集）。掌握這兩種算法，能有效解決網絡布線、聚類分析等實際問題。

That’s all, thanks for reading~~
覺得有用就點個贊、收進收藏夾吧！關注我，獲取更多干貨～