在图论的世界里，最小生成树（Minimum Spanning Tree, MST）是一个至关重要的概念，它在通信网络设计、电路布线、交通规划等领域有着广泛的应用。求解最小生成树的算法中，Prim 算法以其独特的 “逐步扩展” 思想占据着重要地位。
Prim 算法的基本概念
在正式介绍 Prim 算法之前，我们先回顾一下最小生成树的定义：对于一个具有n个顶点的带权连通图，其最小生成树是包含所有n个顶点的一棵无环子图，且该子图中所有边的权值之和最小。
Prim 算法的核心目标就是找到这样一棵最小生成树。与 Kruskal 算法从边入手不同，Prim 算法从顶点出发，通过逐步添加边来构建最小生成树。它始终维持一个 “已选顶点集”，并不断从 “已选顶点集” 到 “未选顶点集” 的所有边中，选择权值最小的边加入生成树，同时将该边连接的未选顶点纳入 “已选顶点集”，直到所有顶点都被纳入为止。
Prim 算法的思想
Prim 算法基于贪心策略，其核心思想可以概括为：从一个初始顶点开始，不断将权值最小的、连接 “已选顶点集” 和 “未选顶点集” 的边加入生成树，并扩展 “已选顶点集”，直至所有顶点都被包含。
具体执行过程如下：
- 初始化：
-
- 选择一个初始顶点（通常为顶点0），将其加入 “已选顶点集”。
-
- 初始化一个距离数组dist，其中dist[i]表示从 “已选顶点集” 到顶点i的最小边的权值。初始时，与初始顶点直接相连的顶点的dist值为对应边的权值，其他顶点的dist值为无穷大。
- 迭代扩展：
-
- 从 “未选顶点集” 中选择dist值最小的顶点u，将其加入 “已选顶点集”。
-
- 对于顶点u的所有邻接顶点v，如果v仍在 “未选顶点集” 中，且边(u, v)的权值小于dist[v]，则更新dist[v]为边(u, v)的权值。
- 结束条件：当 “已选顶点集” 包含所有n个顶点时，停止迭代。此时，dist数组中所有被选中的边的权值之和即为最小生成树的总权值。
通过以下图示可以更直观地理解 Prim 算法的执行过程：
Prim 算法的解题思路
使用 Prim 算法解决实际问题时，通常遵循以下步骤：
- 构建图模型：根据问题描述，将实际场景抽象为带权连通图，确定顶点和边的含义，以及边的权值。
- 选择初始顶点：任意选择一个顶点作为初始顶点（对结果无影响）。
- 初始化数据结构：
-
- 初始化 “已选顶点集”（可通过布尔数组visited标记）。
-
- 初始化距离数组dist，设置初始顶点的dist值为0（或根据实际连接情况设置），其他顶点为无穷大。
- 执行迭代：重复选择dist值最小的未选顶点，更新 “已选顶点集” 和dist数组，直至所有顶点被选中。
- 计算结果：累加被选中的边的权值，得到最小生成树的总权值；若图不连通（即无法选中所有顶点），则返回特定值（如-1）。
LeetCode 例题及 Java 代码实现
例题 1：连接所有点的最小费用（LeetCode 1584）
给你一个points数组，表示2D平面上的一些点，其中points[i] = [x_i, y_i]。连接点[x_i, y_i]和点[x_j, y_j]的费用为它们之间的曼哈顿距离：|x_i - x_j| + |y_i - y_j|。请你计算连接所有点的最小总费用。
解题思路
本题可将每个点视为图的顶点，两点间的曼哈顿距离视为边的权值，问题转化为求该图的最小生成树的总权值。使用 Prim 算法，通过邻接矩阵或邻接表存储图，按上述步骤执行即可。
代码实现
import java.util.Arrays;
public class MinCostToConnectAllPoints {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
if (n <= 1) return 0;
// 初始化距离数组和访问标记
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0; // 选择0作为初始顶点
int totalCost = 0;
int count = 0;
while (count < n) {
// 找到未访问的距离最小的顶点
int u = -1;
int minDist = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
u = i;
}
}
if (u == -1) return -1; // 图不连通
visited[u] = true;
totalCost += minDist;
count++;
// 更新距离数组
for (int v = 0; v < n; v++) {
if (!visited[v]) {
int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
if (d < dist[v]) {
dist[v] = d;
}
}
}
}
return totalCost;
}
}
例题 2：最小生成树的边（LeetCode 1135 变式）
给定n个城市和m条连接城市的道路，每条道路有一个建设成本。请返回构建最小生成树所使用的所有道路的列表（若有多个最小生成树，返回任意一个）。
解题思路
在 Prim 算法执行过程中，不仅记录总权值，还记录每次选中的边（即从已选顶点集到新顶点的边），最后返回这些边的列表即可。
Java 代码实现
import java.util.*;
public class FindMSTEdges {
public List<int[]> findMSTEdges(int n, int[][] edges) {
// 构建邻接表：每个顶点对应一个列表，存储[邻接顶点, 边索引, 权值]
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0];
int v = edges[i][1];
int w = edges[i][2];
adj.get(u).add(new int[]{v, i, w});
adj.get(v).add(new int[]{u, i, w});
}
int[] dist = new int[n];
int[] edgeIndex = new int[n]; // 记录到达每个顶点的边的索引
boolean[] visited = new boolean[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Arrays.fill(edgeIndex, -1);
dist[0] = 0;
List<int[]> mstEdges = new ArrayList<>();
int count = 0;
while (count < n) {
int u = -1;
int minDist = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
if (!visited[i] && dist[i] < minDist) {
minDist = dist[i];
u = i;
}
}
if (u == -1) return new ArrayList<>(); // 图不连通
visited[u] = true;
if (edgeIndex[u] != -1) {
mstEdges.add(edges[edgeIndex[u]]);
}
count++;
// 更新距离和边索引
for (int[] neighbor : adj.get(u)) {
int v = neighbor[0];
int idx = neighbor[1];
int w = neighbor[2];
if (!visited[v] && w < dist[v]) {
dist[v] = w;
edgeIndex[v] = idx;
}
}
}
return mstEdges;
}
}Prim 算法与考研 408
在计算机考研 408 中，Prim 算法是数据结构与算法部分的核心考点，主要涉及以下内容：
1. 算法原理与实现细节
考研 408 常考查 Prim 算法的执行流程，要求考生能手动模拟算法在给定图上的步骤，包括 “已选顶点集” 的扩展过程和dist数组的更新过程。此外，还需掌握算法的两种实现方式：
- 邻接矩阵实现：适用于稠密图，时间复杂度为\(O(n^2)\)（n为顶点数）。
- 邻接表 + 优先队列实现：适用于稀疏图，时间复杂度优化为\(O(m \log n)\)（m为边数）。
2. 与 Kruskal 算法的对比
特性 |
Prim 算法 |
Kruskal 算法 |
适用场景 |
稠密图（边多顶点少） |
稀疏图（边少顶点多） |
核心数据结构 |
距离数组 +（优先队列） |
并查集 + 排序边 |
时间复杂度 |
\(O(n^2)\) 或 \(O(m \log n)\) |
\(O(m \log m)\) |
空间复杂度 |
\(O(n^2)\)（邻接矩阵） |
\(O(m + n)\) |
考研中常以选择题或简答题形式考查两者的区别及适用场景。
3. 算法正确性证明
Prim 算法的正确性基于贪心选择性质和最优子结构性质：
- 贪心选择性质：每次选择的边是连接 “已选” 和 “未选” 顶点的最小边，该边必属于某个最小生成树。
- 最优子结构：若T是图G的最小生成树，则T的子树也是对应子图的最小生成树。
理解证明过程有助于深入掌握算法思想，考研中可能以证明题形式出现（虽概率较低，但需了解）。
4. 应用与变形
考研中可能结合实际问题考查 Prim 算法的变形，例如：
- 带限制条件的最小生成树（如某些顶点必须直接相连）。
- 最大生成树（只需将权值取负，再用 Prim 算法求解）。
总结
Prim 算法作为最小生成树的经典算法，其贪心思想和迭代扩展策略具有重要的学习价值。通过本文的讲解，相信你已掌握其核心思想、解题步骤、LeetCode 实战技巧及考研 408 考点。
希望本文能够帮助读者更深入地理解Prim 算法，并在实际项目中发挥其优势。谢谢阅读！
希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。
