最小生成树（Minimum Spanning Tree, MST）是图论中的经典问题：给定一个带权无向连通图，找到一棵包含所有顶点的树，使得树中所有边的权值之和最小。本文将用Java实现两种经典算法——Prim算法和Kruskal算法，并深入分析它们的贪心策略与适用场景。
问题背景
想象一个场景：你需要为n个城市铺设通信光缆，城市之间可以铺设线路，每条线路有不同的建设成本。如何选择线路，使得所有城市都能连通，且总成本最低？这就是最小生成树问题的实际应用。
Prim算法：从顶点出发的贪心扩展
Prim算法的核心思想是：从一个起始顶点开始，每次选择连接已选顶点集合和未选顶点集合的最小权重边，直到所有顶点都被包含。
算法步骤
- 任选一个顶点作为起始点，加入已选集合
- 维护一个优先队列，存储从已选集合到未选集合的所有边
- 每次取出权重最小的边，如果该边连接的顶点未在已选集合中，则加入该顶点和边
- 重复步骤3，直到所有顶点都被选中
Java实现
import java.util.*;
/**
* Prim算法实现最小生成树
* 使用优先队列优化，时间复杂度 O((V+E)logV)
*/
public class PrimMST {
// 邻接表表示的图
static class Graph {
int vertices;
List<Edge>[] adjacencyList;
@SuppressWarnings("unchecked")
Graph(int vertices) {
this.vertices = vertices;
adjacencyList = new ArrayList[vertices];
for (int i = 0; i < vertices; i++) {
adjacencyList[i] = new ArrayList<>();
}
}
void addEdge(int source, int destination, int weight) {
adjacencyList[source].add(new Edge(source, destination, weight));
adjacencyList[destination].add(new Edge(destination, source, weight));
}
}
static class Edge implements Comparable<Edge> {
int source, destination, weight;
Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
/**
* Prim算法主方法
* @param graph 输入图
* @param startVertex 起始顶点
* @return 最小生成树的边集合
*/
public static List<Edge> primMST(Graph graph, int startVertex) {
List<Edge> mstEdges = new ArrayList<>();
boolean[] inMST = new boolean[graph.vertices];
// 优先队列存储从已选集合到未选集合的边
PriorityQueue<Edge> pq = new PriorityQueue<>();
// 从起始顶点开始
inMST[startVertex] = true;
pq.addAll(graph.adjacencyList[startVertex]);
int edgesAdded = 0;
while (!pq.isEmpty() && edgesAdded < graph.vertices - 1) {
Edge minEdge = pq.poll();
// 如果目标顶点已经在MST中，跳过（避免形成环）
if (inMST[minEdge.destination]) {
continue;
}
// 将顶点和边加入MST
inMST[minEdge.destination] = true;
mstEdges.add(minEdge);
edgesAdded++;
// 将新顶点的所有邻接边加入优先队列
for (Edge edge : graph.adjacencyList[minEdge.destination]) {
if (!inMST[edge.destination]) {
pq.offer(edge);
}
}
}
return mstEdges;
}
public static void main(String[] args) {
// 构建示例图：6个顶点，9条边
Graph graph = new Graph(6);
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 3);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(2, 4, 2);
graph.addEdge(3, 4, 3);
graph.addEdge(3, 5, 2);
graph.addEdge(4, 5, 5);
List<Edge> mst = primMST(graph, 0);
System.out.println("Prim算法生成的最小生成树边：");
int totalWeight = 0;
for (Edge edge : mst) {
System.out.printf("顶点 %d - 顶点 %d, 权重: %d%n",
edge.source, edge.destination, edge.weight);
totalWeight += edge.weight;
}
System.out.println("总权重: " + totalWeight);
}
}
Kruskal算法：从边出发的全局贪心
Kruskal算法的核心思想是：将所有边按权重从小到大排序，依次选择最小的边，如果该边不会与已选边形成环，则加入MST。
算法步骤
- 将所有边按权重升序排序
- 初始化并查集，每个顶点自成一个集合
- 遍历排序后的边，对于每条边(u, v)：
- 如果u和v不在同一个集合（不会形成环），则合并两个集合并选中该边
- 当选中V-1条边时停止
Java实现
import java.util.*;
/**
* Kruskal算法实现最小生成树
* 使用并查集检测环，时间复杂度 O(E log E)
*/
public class KruskalMST {
static class Edge implements Comparable<Edge> {
int source, destination, weight;
Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
/**
* 并查集（Union-Find）数据结构
* 用于高效检测添加边是否会形成环
*/
static class UnionFind {
int[] parent;
int[] rank;
UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// 路径压缩查找
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
// 按秩合并
boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return false; // 已经在同一集合，合并会形成环
}
// 将秩较小的树合并到秩较大的树下
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
return true;
}
}
/**
* Kruskal算法主方法
* @param edges 图中所有边的列表
* @param vertices 顶点数量
* @return 最小生成树的边集合
*/
public static List<Edge> kruskalMST(List<Edge> edges, int vertices) {
List<Edge> mstEdges = new ArrayList<>();
// 按权重升序排序所有边
Collections.sort(edges);
UnionFind uf = new UnionFind(vertices);
for (Edge edge : edges) {
// 尝试合并两个顶点，如果成功说明不会形成环
if (uf.union(edge.source, edge.destination)) {
mstEdges.add(edge);
// 当选中V-1条边时，MST已构建完成
if (mstEdges.size() == vertices - 1) {
break;
}
}
}
return mstEdges;
}
public static void main(String[] args) {
int vertices = 6;
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 4));
edges.add(new Edge(0, 2, 3));
edges.add(new Edge(1, 2, 1));
edges.add(new Edge(1, 3, 2));
edges.add(new Edge(2, 3, 4));
edges.add(new Edge(2, 4, 2));
edges.add(new Edge(3, 4, 3));
edges.add(new Edge(3, 5, 2));
edges.add(new Edge(4, 5, 5));
List<Edge> mst = kruskalMST(edges, vertices);
System.out.println("Kruskal算法生成的最小生成树边：");
int totalWeight = 0;
for (Edge edge : mst) {
System.out.printf("顶点 %d - 顶点 %d, 权重: %d%n",
edge.source, edge.destination, edge.weight);
totalWeight += edge.weight;
}
System.out.println("总权重: " + totalWeight);
}
}
两种算法对比
| 特性 | Prim算法 | Kruskal算法 |
|---|---|---|
| 贪心策略 | 顶点扩展，局部最优 | 全局选边，全局排序 |
| 数据结构 | 优先队列 + 邻接表 | 并查集 + 边列表 |
| 时间复杂度 | O((V+E) log V) | O(E log E) |
| 适用场景 | 稠密图（E接近V²） | 稀疏图（E远小于V²） |
| 空间复杂度 | O(V+E) | O(V+E) |
贪心正确性证明
最小生成树算法能够工作的关键在于切割性质：对于图中的任意一个切割（将顶点分为两个不相交的集合），如果有一条边是跨越该切割的最小权重边，则这条边一定属于某个最小生成树。
Prim算法每次选择的正是跨越”已选-未选”切割的最小边，Kruskal算法在考虑每条边时也保证了该边是连接两个不同连通分量的最小边之一。这两种策略都满足切割性质，因此贪心选择是安全的。
复杂度分析
- Prim算法：使用二叉堆时时间复杂度为O((V+E) log V)，使用斐波那契堆可优化至O(E + V log V)。对于稠密图（E = O(V²)），Prim更优。
- Kruskal算法：排序 dominates 时间复杂度为O(E log E)，并查集操作近似O(1)。对于稀疏图（E = O(V)），Kruskal更优。
扩展思考
- 次小生成树：在最小生成树的基础上，通过替换一条边得到第二小的生成树
- 严格次小生成树：要求总权重严格大于MST的最小生成树
- 最大生成树：将边权取反或排序改为降序即可
- 最小瓶颈生成树：最小化生成树中最大边权的生成树，MST一定是最小瓶颈生成树
总结
最小生成树问题是贪心算法的经典应用。Prim算法适合稠密图，从顶点出发逐步扩展；Kruskal算法适合稀疏图，从全局边集合中贪心选择。理解这两种算法的差异，有助于在实际问题中选择更合适的方案。并查集作为Kruskal的核心数据结构，其路径压缩和按秩合并的优化技巧也值得深入掌握。
