数据结构与算法 / 系统课时
Prim 算法
Prim 算法
本课解决如何在连通带权无向图中,以较低总代价连接全部顶点。我们将用优先队列实现 Prim 算法,并明确它与 Kruskal 算法在数据组织和适用场景上的差异。
学习目标
- 理解 Prim 算法按“跨割最小边”扩展生成树的过程。
- 使用邻接表和优先队列实现 Prim 算法。
- 根据图的存储方式与稠密程度选择 Prim 或 Kruskal 算法。
原理与执行过程
最小生成树需要连接图中全部顶点,包含恰好 V - 1 条边,并使边权总和最小。Prim 算法维护一个已进入生成树的顶点集合,每轮从所有“一端在集合内、另一端在集合外”的边中选择权重最小者。

优先队列保存当前可能连接到新顶点的候选边。弹出最小边后,如果目标顶点已经访问,就丢弃这条过期候选边;否则将其加入生成树,并把新顶点发出的未访问边继续压入队列。
执行时需要关注三个边界条件:输入必须是无向图;图必须连通才能得到单棵生成树;起点会影响具体选边顺序,但不会改变最小生成树的最小总权重。图中允许出现负权边,Prim 算法仍然成立。
完整可运行示例
下面使用 Java 17 的邻接表和 PriorityQueue。将代码保存为 PrimDemo.java。
java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
public class PrimDemo {
private record Edge(int from, int to, int weight) {
}
public static void main(String[] args) {
int vertexCount = 5;
List<List<Edge>> graph = createGraph(vertexCount);
// 每条无向边需要以两个方向写入邻接表。
addUndirectedEdge(graph, 0, 1, 2);
addUndirectedEdge(graph, 0, 3, 6);
addUndirectedEdge(graph, 1, 2, 3);
addUndirectedEdge(graph, 1, 3, 8);
addUndirectedEdge(graph, 1, 4, 5);
addUndirectedEdge(graph, 2, 4, 7);
addUndirectedEdge(graph, 3, 4, 9);
List<Edge> tree = prim(graph, 0);
int totalWeight = 0;
for (Edge edge : tree) {
System.out.printf(
"%d - %d, 权重 = %d%n",
edge.from(),
edge.to(),
edge.weight()
);
totalWeight += edge.weight();
}
System.out.println("最小生成树总权重 = " + totalWeight);
}
private static List<List<Edge>> createGraph(int vertexCount) {
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i < vertexCount; i++) {
graph.add(new ArrayList<>());
}
return graph;
}
private static void addUndirectedEdge(
List<List<Edge>> graph,
int u,
int v,
int weight
) {
graph.get(u).add(new Edge(u, v, weight));
graph.get(v).add(new Edge(v, u, weight));
}
private static List<Edge> prim(List<List<Edge>> graph, int start) {
boolean[] visited = new boolean[graph.size()];
List<Edge> tree = new ArrayList<>();
PriorityQueue<Edge> queue = new PriorityQueue<>(
Comparator.comparingInt(Edge::weight)
.thenComparingInt(Edge::from)
.thenComparingInt(Edge::to)
);
// 从任意起点建立初始割,并加入所有跨割候选边。
visited[start] = true;
queue.addAll(graph.get(start));
while (!queue.isEmpty() && tree.size() < graph.size() - 1) {
Edge edge = queue.poll();
// 同一顶点可能对应多条候选边,旧候选边需要延迟丢弃。
if (visited[edge.to()]) {
continue;
}
visited[edge.to()] = true;
tree.add(edge);
for (Edge next : graph.get(edge.to())) {
if (!visited[next.to()]) {
queue.offer(next);
}
}
}
if (tree.size() != graph.size() - 1) {
throw new IllegalArgumentException(
"图不连通,无法得到单棵最小生成树"
);
}
return tree;
}
}运行命令:
bash
javac PrimDemo.java
java PrimDemo预期输出:
text
0 - 1, 权重 = 2
1 - 2, 权重 = 3
1 - 4, 权重 = 5
0 - 3, 权重 = 6
最小生成树总权重 = 16复杂度、选择与易错点
使用邻接表和二叉堆时,候选边的入队与出队使时间复杂度为 O(E log V),空间复杂度为 O(V + E)。如果图非常稠密,使用邻接矩阵实现的 O(V²) Prim 反而可能更简单且更高效。
| 对比维度 | Prim 算法 | Kruskal 算法 |
|---|---|---|
| 核心动作 | 从一棵树向外扩展 | 按边权从小到大合并连通块 |
| 常用结构 | 邻接表或邻接矩阵、优先队列 | 边列表、排序、并查集 |
| 更适合 | 稠密图或天然按顶点访问的图 | 稀疏图或已经持有完整边列表的场景 |
| 非连通图 | 需对每个连通分量分别执行 | 可自然得到最小生成森林 |
常见错误包括只把无向边加入一个方向、没有跳过指向已访问顶点的过期边,以及忘记检查最终是否选满 V - 1 条边。调试时可以打印每轮弹出的边和 visited 数组,确认候选边确实跨越当前割。
本课练习
- 将示例图增加顶点
5,并添加边2-5、4-5。要求程序仍输出V - 1条边,并手工核对总权重。 - 修改程序,使其在非连通图上返回最小生成森林,而不是抛出异常。验收条件是每个连通分量都得到一棵生成树,孤立顶点也被正确识别。
本课总结
- Prim 算法每轮选择跨越当前割的最小权边,并逐步扩大已选顶点集合。
- 邻接表配合优先队列可实现
O(E log V)的常用版本。 - Prim 与 Kruskal 都能求最小生成树,但数据组织方式和非连通图处理不同。
下一课预告
下一课进入“流网络建模”,把带方向和容量限制的网络抽象为源点、汇点、容量与流量,为后续最大流算法建立统一表示。
按自己的节奏,确认真正理解。