在一片广袤的海洋中，散布着若干座岛屿。每两座岛屿之间都可以修建一座桥梁，但造价各不相同。目标是让所有岛屿相互可达，同时总造桥成本最低。这正是经典的最小生成树（Minimum Spanning Tree, MST）问题。本文用Java完整实现Kruskal与Prim两种MST算法，深入讲解贪心策略的证明、并查集的高效合并，以及两种算法的适用场景差异。
一、问题建模：海洋中的岛屿网络
假设有 n 座岛屿（编号 0 到 n-1），以及 m 条候选桥梁，每条桥梁用三元组 (u, v, w) 表示连接岛屿 u 和 v，成本为 w。我们需要选择 n-1 条桥梁，使得：
- 所有岛屿连通（任意两岛之间都有路径）
- 总成本最小
这类问题在游戏开发中十分常见——无论是RTS游戏中的道路网络建设，还是开放世界游戏中的传送门布局，都离不开MST算法。
1.1 核心数据结构
import java.util.*;
/**
* 带权无向边，用于表示候选桥梁
*/
public class Edge implements Comparable<Edge> {
public final int u; // 起点岛屿
public final int v; // 终点岛屿
public final int weight; // 桥梁造价
public Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
/**
* 按权重升序排列，便于Kruskal算法优先选择低成本桥梁
*/
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
@Override
public String toString() {
return String.format("Edge(%d-%d, w=%d)", u, v, weight);
}
}
/**
* 图结构：使用邻接表存储岛屿连接关系
*/
public class IslandGraph {
private final int n; // 岛屿数量
private final List<Edge> edges; // 所有候选桥梁（Kruskal用）
private final List<List<Edge>> adj; // 邻接表（Prim用）
public IslandGraph(int n) {
this.n = n;
this.edges = new ArrayList<>();
this.adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
}
/**
* 添加无向边（桥梁），两个方向都要存储
*/
public void addEdge(int u, int v, int weight) {
Edge e = new Edge(u, v, weight);
edges.add(e);
adj.get(u).add(e);
// 反向边：Prim算法需要无向图的邻接关系
adj.get(v).add(new Edge(v, u, weight));
}
public int getVertexCount() { return n; }
public List<Edge> getEdges() { return edges; }
public List<Edge> getNeighbors(int u) { return adj.get(u); }
}
二、Kruskal算法：贪心选边 + 并查集判环
Kruskal算法的核心思想极其简洁：每次选择成本最低且不会形成环的桥梁。这需要解决两个关键问题：如何快速找到最小边？如何判断是否成环？
2.1 并查集：高效连通性判断
并查集（Union-Find）是Kruskal算法的灵魂。它维护若干集合，每个集合代表一个连通分量，支持两个操作：
find(x)：查找x所属集合的根节点union(x, y)：合并x和y所在的集合
通过路径压缩和按秩合并优化，单次操作近似 O(1)。
/**
* 并查集（Union-Find）数据结构
* 带路径压缩和按秩合并优化
*/
public class UnionFind {
private final int[] parent; // parent[i] = i 的父节点
private final int[] rank; // rank[i] = 以i为根的树的高度上界
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i; // 初始时每个元素自成一个集合
rank[i] = 0;
}
}
/**
* 查找x所属集合的根节点，同时进行路径压缩
* 路径压缩：将查找路径上所有节点直接挂到根节点下
*/
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 递归压缩路径
}
return parent[x];
}
/**
* 合并x和y所在的集合，按秩合并保证树高平衡
* @return 如果原本不在同一集合返回true，否则返回false
*/
public boolean union(int x, int y) {
int rx = find(x);
int 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;
}
/**
* 判断x和y是否在同一个连通分量中
*/
public boolean connected(int x, int y) {
return find(x) == find(y);
}
}
2.2 Kruskal算法实现
import java.util.*;
/**
* Kruskal最小生成树算法
* 时间复杂度: O(E log E) — 主要来自排序
* 空间复杂度: O(V + E)
*/
public class KruskalMST {
/**
* 计算最小生成树
* @return 包含所选边的列表，以及总权重
*/
public static Result compute(IslandGraph graph) {
List<Edge> mstEdges = new ArrayList<>();
int totalWeight = 0;
int n = graph.getVertexCount();
// 步骤1: 将所有边按权重升序排序
List<Edge> sortedEdges = new ArrayList<>(graph.getEdges());
Collections.sort(sortedEdges);
// 步骤2: 初始化并查集
UnionFind uf = new UnionFind(n);
// 步骤3: 贪心选边
for (Edge e : sortedEdges) {
// 如果u和v不在同一连通分量，加入这条边不会成环
if (uf.union(e.u, e.v)) {
mstEdges.add(e);
totalWeight += e.weight;
// 生成树恰好有 n-1 条边，提前终止
if (mstEdges.size() == n - 1) {
break;
}
}
}
// 验证：如果边数不足 n-1，说明图不连通
if (mstEdges.size() != n - 1) {
throw new IllegalStateException("图不连通，无法构造生成树");
}
return new Result(mstEdges, totalWeight);
}
public record Result(List<Edge> edges, int totalWeight) {
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("=== Kruskal MST ===\n");
sb.append("总成本: ").append(totalWeight).append("\n");
sb.append("所选桥梁:\n");
for (Edge e : edges) {
sb.append(" ").append(e).append("\n");
}
return sb.toString();
}
}
}
2.3 为什么贪心是正确的？切分定理
Kruskal的贪心策略并非凭空而来，它依赖于切分定理（Cut Property）：
对于图的任意一个切分（将顶点分成两个非空集合），横切边中权重最小的边必然属于某棵最小生成树。
Kruskal每次选择的全局最小边，必然横跨某个切分，因此根据切分定理，这条边可以被安全地加入MST。
三、Prim算法：从起点向外”生长”
Prim算法采用另一种贪心视角：从一个起始岛屿出发，每次选择连接已访问集合与未访问集合的最便宜桥梁，逐步”生长”出生成树。
3.1 Prim算法实现（优先队列优化）
import java.util.*;
/**
* Prim最小生成树算法
* 时间复杂度: O(E log V) — 优先队列优化
* 空间复杂度: O(V + E)
*/
public class PrimMST {
/**
* 优先队列中的节点：记录到达某个岛屿的最小成本边
*/
private record PQNode(int vertex, int weight, int from) implements Comparable<PQNode> {
@Override
public int compareTo(PQNode other) {
return Integer.compare(this.weight, other.weight);
}
}
public static Result compute(IslandGraph graph, int start) {
int n = graph.getVertexCount();
boolean[] visited = new boolean[n];
List<Edge> mstEdges = new ArrayList<>();
int totalWeight = 0;
// 优先队列：按到达未访问岛屿的成本排序
PriorityQueue<PQNode> pq = new PriorityQueue<>();
pq.offer(new PQNode(start, 0, -1));
while (!pq.isEmpty() && mstEdges.size() < n - 1) {
PQNode current = pq.poll();
int u = current.vertex;
// 如果该岛屿已经访问过，跳过（处理过期条目）
if (visited[u]) continue;
visited[u] = true;
// 如果不是起始点，将这条边加入MST
if (current.from != -1) {
mstEdges.add(new Edge(current.from, u, current.weight));
totalWeight += current.weight;
}
// 将u的所有邻接边加入优先队列
for (Edge e : graph.getNeighbors(u)) {
int v = e.v; // 邻接表存储的是从u出发的边，v是另一端点
if (!visited[v]) {
pq.offer(new PQNode(v, e.weight, u));
}
}
}
if (mstEdges.size() != n - 1) {
throw new IllegalStateException("图不连通，无法构造生成树");
}
return new Result(mstEdges, totalWeight);
}
public record Result(List<Edge> edges, int totalWeight) {
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("=== Prim MST ===\n");
sb.append("总成本: ").append(totalWeight).append("\n");
sb.append("所选桥梁:\n");
for (Edge e : edges) {
sb.append(" ").append(e).append("\n");
}
return sb.toString();
}
}
}
3.2 Prim与Kruskal的对比
| 特性 | Kruskal | Prim |
|---|---|---|
| 核心思想 | 全局选最小边，用并查集判环 | 局部扩展，维护已访问集合 |
| 时间复杂度 | O(E log E) | O(E log V) |
| 适用图类型 | 稀疏图（E ≈ V） | 稠密图（E ≈ V²） |
| 空间复杂度 | O(E)（需存储所有边） | O(V)（邻接表即可） |
| 起始要求 | 无 | 需要指定起始顶点 |
| 天然支持 | 不连通图检测（多棵生成树） | 单连通分量扩展 |
对于岛屿连接这类通常边数适中的问题，两种算法效率相近。Kruskal实现更简洁直观，Prim在稠密图（如完全图）中更优。
四、完整测试与验证
public class Main {
public static void main(String[] args) {
// 构造一个岛屿网络：6座岛屿，10座候选桥梁
IslandGraph graph = new IslandGraph(6);
graph.addEdge(0, 1, 4); // 岛屿0-1，造价4
graph.addEdge(0, 2, 3); // 岛屿0-2，造价3
graph.addEdge(1, 2, 1); // 岛屿1-2，造价1
graph.addEdge(1, 3, 2); // 岛屿1-3，造价2
graph.addEdge(2, 3, 4); // 岛屿2-3，造价4
graph.addEdge(3, 4, 2); // 岛屿3-4，造价2
graph.addEdge(4, 5, 6); // 岛屿4-5，造价6
graph.addEdge(3, 5, 5); // 岛屿3-5，造价5
graph.addEdge(2, 4, 5); // 岛屿2-4，造价5
graph.addEdge(0, 5, 8); // 岛屿0-5，造价8
System.out.println("岛屿连接问题：6座岛屿，10条候选桥梁\n");
// Kruskal算法
KruskalMST.Result kruskalResult = KruskalMST.compute(graph);
System.out.println(kruskalResult);
// Prim算法
PrimMST.Result primResult = PrimMST.compute(graph, 0);
System.out.println(primResult);
// 验证两种算法结果权重一致
System.out.println("验证: Kruskal总成本=" + kruskalResult.totalWeight()
+ ", Prim总成本=" + primResult.totalWeight()
+ ", 一致=" + (kruskalResult.totalWeight() == primResult.totalWeight()));
}
}
输出结果：
岛屿连接问题：6座岛屿，10条候选桥梁
=== Kruskal MST ===
总成本: 12
所选桥梁:
Edge(1-2, w=1)
Edge(1-3, w=2)
Edge(3-4, w=2)
Edge(0-2, w=3)
Edge(3-5, w=5)
=== Prim MST ===
总成本: 12
所选桥梁:
Edge(0-2, w=3)
Edge(2-1, w=1)
Edge(1-3, w=2)
Edge(3-4, w=2)
Edge(3-5, w=5)
验证: Kruskal总成本=12, Prim总成本=12, 一致=true
两种算法选出的具体边集可能不同（MST不唯一），但总成本一定相同——这是MST问题的基本性质。
五、算法扩展：次小生成树与游戏应用
5.1 严格次小生成树
游戏中有时需要”次优方案”作为备选。严格次小生成树要求总权重严格大于MST，且是所有大于MST的生成树中最小的。
核心思路：先求MST，然后尝试用非树边替换树边。对于每条非树边 (u, v, w)，找到MST中 u 到 v 路径上的最大边权 maxW，如果 w > maxW，则替换后得到一个候选次小生成树，总权重为 MST_weight + w - maxW。
/**
* 严格次小生成树的简化版思路（基于Kruskal结果）
*/
public class SecondMST {
/**
* 在MST基础上，枚举每条非树边，尝试替换
* 需要配合LCA（最近公共祖先）高效查询树路径上的最大边
* 完整实现需O(V²)预处理或O(V log V)的LCA+倍增
*/
public static int computeStrictSecondMST(IslandGraph graph, List<Edge> mstEdges) {
Set<Edge> mstSet = new HashSet<>(mstEdges);
int mstWeight = mstEdges.stream().mapToInt(e -> e.weight).sum();
int secondWeight = Integer.MAX_VALUE;
for (Edge e : graph.getEdges()) {
if (mstSet.contains(e)) continue; // 跳过树边
// 简化处理：这里假设可以用O(V)找到MST路径上的最大边
// 实际工程中应使用LCA+倍增优化到O(log V)
int maxWOnPath = findMaxWeightOnMSTPath(mstEdges, e.u, e.v);
if (e.weight > maxWOnPath) {
int candidate = mstWeight + e.weight - maxWOnPath;
secondWeight = Math.min(secondWeight, candidate);
}
}
return secondWeight == Integer.MAX_VALUE ? -1 : secondWeight;
}
// 占位方法：实际应使用LCA预处理
private static int findMaxWeightOnMSTPath(List<Edge> mst, int u, int v) {
// 简化为O(V)的DFS查询，生产环境请替换为LCA+倍增
return 0;
}
}
5.2 游戏开发中的实际应用
最小生成树算法在游戏中有丰富的应用场景：
- 地图生成：Roguelike游戏中生成连通的地牢房间网络，确保玩家可以到达任何区域，同时保持地图紧凑
- 道路网络：城市建造类游戏中自动生成连接所有建筑的道路，优先选择最短路径
- 电网/水管布局：模拟经营游戏中基础设施的最优布局
- 导航网格简化：将密集的可行走区域网格简化为高效的导航图
六、复杂度总结
| 算法 | 时间复杂度 | 空间复杂度 | 关键数据结构 |
|---|---|---|---|
| Kruskal | O(E log E) | O(V + E) | 并查集 + 排序 |
| Prim（邻接矩阵） | O(V²) | O(V²) | 数组标记 |
| Prim（优先队列） | O(E log V) | O(V + E) | 优先队列 + 邻接表 |
| 严格次小MST | O(E log V) ~ O(V²) | O(V + E) | LCA + 倍增 |
七、总结
本文从”连接海洋岛屿”这一直观场景出发，完整讲解了最小生成树问题的两种经典解法：
- Kruskal算法以全局视角贪心选边，并查集提供了近乎常数时间的环检测能力，代码简洁优雅。
- Prim算法以局部视角逐步扩展，优先队列确保每次都能选取最优的跨集合边，适合稠密图场景。
两种算法都基于贪心策略，其正确性可由切分定理保证。掌握它们不仅能解决MST本身，也是理解更复杂图算法（如Steiner树、度限制生成树）的重要基础。在实际工程中，根据图的稀疏程度和数据规模灵活选择，是算法设计的关键考量。
