最小生成树（Minimum Spanning Tree, MST）
这玩意儿听起来挺唬人，但其实思想特别朴素。想象一下，现在有几个村庄，你要负责修路把它们都连起来，并且想花最少的钱。每条备选的路都有一个造价。你怎么设计这个路网，才能保证所有村庄都能互相到达，并且总造价最低？
这就是最小生成树。给你一张带权重的无向图，找一棵能连接所有顶点的树，并且这棵树所有边的权重之和最小。
扯远了，拉回来。搞定这个问题，有两个经典的“骚操作”，一个叫Kruskal，一个叫Prim。这两个都是贪心算法，但贪心的角度不太一样。今天咱们把这俩都盘明白了。
准备工作：图怎么表示？
在撸代码之前，得先把图这个结构定义好。一个图由点（Vertex）和边（Edge）组成。对于最小生成树问题，边是核心，因为它有权重。所以，我一般会这么定义：
// 边
class Edge implements Comparable<Edge> {
int from; // 边的起点
int to; // 边的终点
int weight; // 边的权重
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
// 为了后续排序或放进优先队列
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
// 图的表示后面根据不同算法来定，因为Kruskal和Prim对图的结构要求不太一样
好了，家伙事儿备好了，开整！
解法一：Kruskal算法——从边的角度贪心
Kruskal的想法极其简单粗暴：每次都选当前没被选过、并且权重最小的边，加入到我的结果集里，但有个前提——不能形成环。
为啥不能有环？因为咱们要的是一棵“树”，树的定义就是无环连通图。如果加了一条边形成了环，那说明这条边的两个端点之前已经能互相到达了，再加这条边纯属浪费钱，肯定不是最优解。
所以，Kruskal算法的核心就两个事：
怎么保证每次都拿到权重最小的边？
怎么判断新加入的边会不会形成环？
第一个问题好办，把所有边按权重从小到大排个序，或者直接扔进一个小根堆（优先队列）里，每次取堆顶就行了。
第二个问题是关键。判断环？听起来挺麻烦。但换个思路想：如果一条边的两个端点，在当前已选的边构成的图中，已经属于同一个连通分量了，那再把这条边加上，不就形成环了吗？
这不就是并查集（Union-Find） 的标准应用场景吗？
并查集这东西，就是专门用来处理“连通性”问题的。它主要提供两个操作：
find(i): 查找元素i属于哪个集合（哪个老大带的）。union(i, j): 合并元素i和j所在的两个集合。
用并查集来辅助Kruskal，思路一下就清晰了：
初始化一个并查集，图里有几个顶点，并查集里就有几个独立的集合。
把所有的边都扔进一个优先队列（按权重从小到大）。
从优先队列里弹出权重最小的边
(u, v)。用并查集的
find操作检查u和v是不是已经在同一个集合里了。如果是，说明
u和v已经连通了，加这条边会成环。扔掉，继续下一条。如果不是，说明这条边是安全的。采纳它，把它加入结果集，然后用
union操作把u和v合并到同一个集合。
重复这个过程，直到我们选够了
V-1条边（V是顶点数），一棵树就形成了。
代码实现：
import java.util.*;
// 并查集结构
class UnionFind {
private int[] parent;
private int count; // 记录连通分量的数量
public UnionFind(int n) {
parent = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i; // 初始时，每个节点的父节点是自己
}
}
public int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]); // 路径压缩
}
return parent[i];
}
public void union(int i, int j) {
int rootI = find(i);
int rootJ = find(j);
if (rootI != rootJ) {
parent[rootI] = rootJ;
count--;
}
}
public boolean isConnected(int i, int j) {
return find(i) == find(j);
}
}
public class MST_Kruskal {
// 假设顶点编号从0到n-1
public static List<Edge> kruskalMST(int n, List<Edge> edges) {
UnionFind uf = new UnionFind(n);
// 使用优先队列自动按权重排序
PriorityQueue<Edge> pq = new PriorityQueue<>(edges);
List<Edge> result = new ArrayList<>();
int totalWeight = 0;
while (!pq.isEmpty() && result.size() < n - 1) {
Edge edge = pq.poll();
if (!uf.isConnected(edge.from, edge.to)) {
uf.union(edge.from, edge.to);
result.add(edge);
totalWeight += edge.weight;
}
}
System.out.println("Kruskal - 最小权重和: " + totalWeight);
return result;
}
public static void main(String[] args) {
int n = 4; // 4个顶点 0, 1, 2, 3
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 10));
edges.add(new Edge(0, 2, 6));
edges.add(new Edge(0, 3, 5));
edges.add(new Edge(1, 3, 15));
edges.add(new Edge(2, 3, 4));
List<Edge> mst = kruskalMST(n, edges);
System.out.println("Kruskal - 最小生成树的边:");
for (Edge edge : mst) {
System.out.println(edge.from + " - " + edge.to + " : " + edge.weight);
}
}
}
Kruskal算法不关心图的局部结构，视野很大，上来就对所有边“排座次”，所以它不依赖于从哪个点开始，适合处理边比较稀疏的图。
解法二：Prim算法——从点的角度贪心
Prim算法和Kruskal的思路完全不同。它不看全局的边，而是采用一种“扩张”的策略。
想象一下，你站在其中一个村庄，你要做的就是找到一条通往“外面”世界（未连接的村庄）的、造价最低的路，然后把路修过去，把那个新的村庄也纳入你的“版图”。然后，你站在你已经连接好的所有村庄的“版图”上，再重复这个过程：找到一条连接“版图内”和“版图外”的最便宜的路，修过去，扩大版图。
这个过程，就是Prim算法的核心：
随便选一个点作为起点，把它加入集合
S（表示已经属于我们生成树的点）。找到所有一端在
S中，另一端不在S中的边。从这些“跨界”边中，选出权重最小的一条边
(u, v)，其中u在S中，v不在S中。把这条边加入我们的最小生成树，并把点
v也加入集合S。重复步骤2-4，直到所有点都加入了集合
S。
这个过程中，最关键的一步是“如何高效地找到那条权重最小的跨界边”。这又是一个“找最小”的问题，小根堆（优先队列）再次登场。
思路细化：
需要一个集合（比如
boolean[] visited）来记录哪些点已经加入了生成树。需要一个优先队列，用来存放所有“跨界”的边。
从一个点（比如0号点）开始：
标记0号点为已访问。
把它所有相连的边都加入优先队列。
当优先队列不为空，并且我们还没选够
V-1条边时，循环：从优先队列中弹出权重最小的边
(u, v)。检查这条边的另一个端点
v是不是已经访问过了。如果访问过了，说明这条边连接的是两个已经在我们“版图”内的点，会形成环。扔掉。
如果没访问过，那太好了，这就是我们要找的最小“跨界”边。采纳它，把
v标记为已访问，然后把v所有通往“未知世界”（未访问过的点）的边，都加入优先队列。
代码实现：
为了方便找到一个点的所有邻边，这里用邻接表来表示图。
import java.util.*;
// Prim算法一般使用邻接表来表示图
// Edge 类复用上面的定义
public class MST_Prim {
public static List<Edge> primMST(int n, List<List<Edge>> graph) {
List<Edge> result = new ArrayList<>();
int totalWeight = 0;
// 小根堆，存放待考察的边
PriorityQueue<Edge> pq = new PriorityQueue<>();
// visited数组，标记哪些点已经加入了生成树
boolean[] visited = new boolean[n];
// 从0号点开始
visited[0] = true;
// 把0号点连出去的所有边都加入pq
for (Edge edge : graph.get(0)) {
pq.add(edge);
}
while (!pq.isEmpty() && result.size() < n - 1) {
Edge edge = pq.poll();
int toNode = edge.to; // 边的另一个端点
// 如果这个端点已经被访问过，说明这条边是连接“内部”的，会成环
if (visited[toNode]) {
continue;
}
// 找到了新的最小跨界边
visited[toNode] = true;
result.add(edge);
totalWeight += edge.weight;
// 把新加入的点(toNode)的所有"跨界"边也加入pq
for (Edge nextEdge : graph.get(toNode)) {
if (!visited[nextEdge.to]) {
pq.add(nextEdge);
}
}
}
System.out.println("Prim - 最小权重和: " + totalWeight);
return result;
}
public static void main(String[] args) {
int n = 4;
// 构建邻接表
List<List<Edge>> graph = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 由于是无向图，一条边要加两次
addEdge(graph, 0, 1, 10);
addEdge(graph, 0, 2, 6);
addEdge(graph, 0, 3, 5);
addEdge(graph, 1, 3, 15);
addEdge(graph, 2, 3, 4);
List<Edge> mst = primMST(n, graph);
System.out.println("Prim - 最小生成树的边:");
for (Edge edge : mst) {
// 注意，因为邻接表加了双向边，打印时可能会有from/to颠倒，但边是一样的
System.out.println(edge.from + " - " + edge.to + " : " + edge.weight);
}
}
private static void addEdge(List<List<Edge>> graph, int u, int v, int w) {
// 无向图，from和to其实不重要，但为了实现方便，我们定义一个方向
graph.get(u).add(new Edge(u, v, w));
graph.get(v).add(new Edge(v, u, w));
}
}
Prim算法像是在一个点上“点火”，然后火势（版图）慢慢蔓延开来，每次都烧向最近的那个易燃物。它非常适合处理边比较稠密的图。
解法三：Prim算法的另一种实现——无堆优化（适用于稠密图）
上面那个Prim版本依赖优先队列，时间复杂度是 O(E logV)。在大多数情况下，这已经非常优秀了。但如果图是稠密图（边的数量 E 接近 V^2），我们还有一种更“暴力”但可能更快的玩法。
这个版本的Prim不用优先队列，而是用一个数组 dist[] 来维护“外部”的点到我们“版图”（集合 S）的最短距离。
思路：
初始化一个
dist数组，dist[i]表示节点i到已选集合S的最短边的权重。初始时，除了起点（比如0号点，dist[0]=0），其他都设为无穷大。初始化一个
visited数组，全都设为false。循环
V次： a. 在所有未被访问的节点中，找到dist值最小的那个点u。 b. 把u标记为已访问，并将dist[u]加入总权重（如果dist[u]不是初始的0）。 c. 遍历u的所有邻居v，如果v还没被访问，就更新dist[v]的值：dist[v] = min(dist[v], weight(u, v))。也就是说，看看通过新加入的u点，能不能让v到我们版图的距离变得更近。
这个过程本质上和Dijkstra算法求单源最短路径非常像，只是更新 dist 数组的逻辑不同。Dijkstra是累加路径，而Prim是直接取边的权重。
代码实现：
这种实现通常用邻接矩阵表示图，会更直观。
import java.util.Arrays;
public class MST_Prim_Dense {
private static final int INF = Integer.MAX_VALUE;
public static void primMST(int n, int[][] graph) {
int[] dist = new int[n]; // dist[i]表示节点i到已选集合的最短距离
boolean[] visited = new boolean[n]; // 标记节点是否已加入MST
int totalWeight = 0;
// 初始化
Arrays.fill(dist, INF);
dist[0] = 0; // 从0号节点开始
// 需要V次循环，每次找到一个新节点加入MST
for (int i = 0; i < n; i++) {
int u = -1, min_dist = INF;
// 1. 找到dist值最小的未访问节点
for (int v = 0; v < n; v++) {
if (!visited[v] && dist[v] < min_dist) {
min_dist = dist[v];
u = v;
}
}
// 如果找不到（图不连通），则提前结束
if (u == -1) break;
// 2. 将找到的节点u加入MST
visited[u] = true;
totalWeight += min_dist;
// 3. 更新u的邻居到MST的距离
for (int v = 0; v < n; v++) {
if (!visited[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) {
dist[v] = graph[u][v];
}
}
}
System.out.println("Prim (无堆优化) - 最小权重和: " + totalWeight);
}
public static void main(String[] args) {
int n = 4;
// 邻接矩阵表示图, 0表示不连通
int[][] graph = {
{0, 10, 6, 5},
{10, 0, 0, 15},
{6, 0, 0, 4},
{5, 15, 4, 0}
};
primMST(n, graph);
}
}
这个版本的时间复杂度是 O(V^2)，因为它有两层循环，内层循环每次都要遍历所有顶点来找最小值。当 E 远小于 V^2（稀疏图）时，它不如带堆优化的Prim快；但当 E 接近 V^2（稠密图）时，O(V^2) 就可能比 O(E logV) ~ O(V^2 logV) 更优了。
总结一下
| 特性 | Kruskal | Prim (堆优化) | Prim (无堆优化) |
| 贪心策略 | 从 边 出发，选全局最小、不构成环的边 | 从 点 出发，扩张集合，选连接内外的最小边 | 同左 |
| 核心数据结构 | 并查集、优先队列 | 优先队列、访问集合 | 数组 (dist, visited) |
| 时间复杂度 | O(E logE) 或 O(E logV) | O(E logV) | O(V^2) |
| 适用场景 | 稀疏图 (E 远小于 V^2) | 通用，特别是稀疏图 | 稠密图 (E 接近 V^2) |
| 实现特点 | 简单直观，不依赖起点 | 从一个点开始“蔓延” | 类似Dijkstra，实现简单 |
Kruskal是“边”的视角，大局观强；Prim是“点”的视角，步步为营。最终都能殊途同归。理解了它们各自的贪心策略和实现瓶颈，才能在不同的场景下选择最合适的工具。