最小生成树算法详解

图论与网络优化中，最小生成树（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(n²)（n 为节点数），适合稠密图（边数接近 n²）。
• 邻接表+优先队列：优化后时间复杂度为 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(n²)，稀疏图 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~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～