Appearance
Prim 算法
为什么需要Prim 算法
在实际问题中，经常需要用最小的代价将所有节点连通——例如铺设城市间的光缆、修建公路网等。这类问题的本质就是求最小生成树（Minimum Spanning Tree, MST）。
最小生成树的定义：对于一个有 n 个顶点的连通无向带权图，选取 n-1 条边将所有顶点连通，且边权之和最小，所得到的树即为最小生成树。
Prim 算法是求 MST 的经典算法之一，采用贪心策略，适用于稠密图（边数较多的图）。408 考研中，Prim 与 Kruskal 是图论章节的核心考点。
核心思想
Prim 算法的核心是逐步扩展——从任意一个顶点出发，每次将离当前生成树最近的顶点加入树中：
- 贪心策略：每一步都选择连接树内顶点与树外顶点的权值最小的边
- 逐顶点生长：每次加入一个顶点，共执行 n-1 轮
- 辅助数组：用
lowcost[]和closest[]记录树外各顶点到树的最短距离及对应的树内顶点
算法维护两个集合：已加入 MST 的顶点集合 U 和未加入的顶点集合 V-U。每轮从 V-U 中选取 lowcost 值最小的顶点加入 U，并更新剩余顶点的 lowcost 和 closest。
交互可视化
通过下方的交互动画，你可以逐步观察Prim 算法的执行过程：
操作详解
算法思路
关键步骤：
- 初始化：选取起始顶点加入 U，用邻接矩阵初始化
lowcost[]和closest[] - 循环 n-1 次：
- 在
lowcost[]中找到值最小且未加入树的顶点 k - 将 k 加入 U，标记
lowcost[k] = 0 - 扫描 k 的所有邻接顶点 j，若
cost[k][j] < lowcost[j]，则更新lowcost[j]和closest[j]
- 在
- 循环结束后，得到 MST 的 n-1 条边
cpp
void Prim(int cost[][MAXV], int n, int v0) {
int lowcost[MAXV], closest[MAXV];
int visited[MAXV] = {0};
// 初始化：以 v0 为起点
for (int i = 0; i < n; i++) {
lowcost[i] = cost[v0][i];
closest[i] = v0;
}
visited[v0] = 1;
for (int i = 1; i < n; i++) {
// 找 lowcost 最小的未访问顶点
int min = INF, k = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
visited[k] = 1; // 将 k 加入 MST
// 更新 lowcost 和 closest
for (int j = 0; j < n; j++) {
if (!visited[j] && cost[k][j] < lowcost[j]) {
lowcost[j] = cost[k][j];
closest[j] = k;
}
}
}
}执行过程详解
以一个 5 顶点的图为例，假设从顶点 0 开始：
| 轮次 | 操作 | 加入顶点 | 选取的边 |
|---|---|---|---|
| 初始 | 以顶点 0 初始化 lowcost[] | 0 | — |
| 第 1 轮 | 找 lowcost 最小的顶点 | k₁ | (0, k₁) |
| 第 2 轮 | 更新后再找最小 | k₂ | (closest[k₂], k₂) |
| ... | 重复直到所有顶点加入 | ... | ... |
| 第 n-1 轮 | 最后一个顶点加入 MST | kₙ₋₁ | (closest[kₙ₋₁], kₙ₋₁) |
每轮的核心操作分为两步：选最小（遍历 lowcost 找最小值）和更新（用新加入顶点的邻接边更新 lowcost）。
复杂度分析
- 外层循环执行 n-1 次
- 每轮内部有两次遍历，各 O(V)
- 总时间复杂度：O(V²)，与边数无关
- 若使用最小堆优化，可降至 O(E log V)，但 408 考研中一般考察朴素版本
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V²) | 两层循环，每层 O(V) |
| 空间复杂度 | O(V) | lowcost[]、closest[]、visited[] |
| 堆优化时间 | O(E log V) | 使用优先队列，适合稀疏图 |
Prim vs Kruskal 对比：
| 对比项 | Prim | Kruskal |
|---|---|---|
| 策略 | 逐顶点扩展 | 逐边选取 |
| 时间复杂度 | O(V²) | O(E log E) |
| 适用场景 | 稠密图（边多） | 稀疏图（边少） |
| 数据结构 | 邻接矩阵 | 边集数组 + 并查集 |
| 初始状态 | 从一个顶点开始 | 从所有边开始 |
考研高频考点
- ⭐ Prim 算法的执行过程手动模拟（选择题/填空题高频，给图求 MST）
- ⭐ Prim 与 Kruskal 的适用场景对比（简答题必考：稠密图用 Prim，稀疏图用 Kruskal）
- ⭐ 时间复杂度 O(V²) 的推导及含义（与边数无关，只与顶点数有关）
- ⭐ lowcost[] 和 closest[] 数组的含义及更新规则
- MST 的性质：n 个顶点恰好 n-1 条边，权值之和最小，MST 可能不唯一
- 切割定理（Cut Property）：跨越任意切割的最小权边一定属于某棵 MST