Prim算法的核心目标是在加权连通图中找到一棵包含所有顶点、边权值总和最小的生成树，它的基本思路是从任意一个起始顶点开始，逐步挑选连接已选顶点集合和未选顶点集合的最小权值边，将对应的未选顶点加入已选集合，直到所有顶点都被纳入生成树中。
Prim算法核心逻辑梳理
实现Prim算法前需要先明确几个关键概念：
- 已选顶点集合：初始时只包含起始顶点，后续逐步加入新顶点
- 候选边集合：所有连接已选集合和未选集合的边
- 最小权值边选择：每次从候选边中挑选权值最小的边，将边对应的未选顶点加入已选集合
整个过程可以用以下步骤概括：
- 初始化已选顶点集合，放入起始顶点
- 初始化候选边集合，加入起始顶点的所有邻接边
- 循环执行：从候选边中选权值最小的边，将新顶点加入已选集合，将该新顶点的所有连接未选顶点的邻接边加入候选边，直到已选集合包含所有顶点
基于邻接矩阵的Python实现
邻接矩阵适合存储边数量较多的稠密图，假设我们用二维列表表示邻接矩阵，其中graph[i][j]表示顶点i到顶点j的边的权值，如果两个顶点不连通则权值为无穷大（这里用float('inf')表示）。
import sys
def prim_with_adj_matrix(graph):
"""
基于邻接矩阵的Prim算法实现
:param graph: 二维列表表示的邻接矩阵，graph[i][j]为顶点i到j的边权值
:return: 最小生成树的边集合，以及总权值
"""
# 顶点数量
vertex_num = len(graph)
# 已选顶点集合，初始为空
selected_vertices = set()
# 最小生成树的边集合
mst_edges = []
# 总权值
total_weight = 0
# 起始顶点，这里默认选择0号顶点
start_vertex = 0
selected_vertices.add(start_vertex)
while len(selected_vertices) < vertex_num:
min_weight = float('inf')
best_edge = None
# 遍历所有已选顶点
for u in selected_vertices:
# 遍历所有顶点，找连接已选和未选的最小边
for v in range(vertex_num):
# 如果v未被选中，且u和v之间有边，且边权值小于当前最小值
if v not in selected_vertices and graph[u][v] < min_weight:
min_weight = graph[u][v]
best_edge = (u, v, graph[u][v])
# 如果找到了合适的边
if best_edge:
u, v, weight = best_edge
selected_vertices.add(v)
mst_edges.append(best_edge)
total_weight += weight
else:
# 图不连通的情况
break
return mst_edges, total_weight
# 测试用例，邻接矩阵表示的无向图
# 顶点0-4，不连通的位置用inf表示
test_graph = [
[0, 2, float('inf'), 6, float('inf')],
[2, 0, 3, 8, 5],
[float('inf'), 3, 0, float('inf'), 7],
[6, 8, float('inf'), 0, 9],
[float('inf'), 5, 7, 9, 0]
]
edges, weight = prim_with_adj_matrix(test_graph)
print("最小生成树的边：")
for edge in edges:
print(f"顶点{edge[0]} - 顶点{edge[1]}，权值：{edge[2]}")
print(f"最小生成树总权值：{weight}")
基于邻接表的Python实现
邻接表更适合存储边数量较少的稀疏图，我们用字典来表示邻接表，键是顶点，值是该顶点的邻接顶点和对应边权值的列表。
import heapq
def prim_with_adj_list(graph):
"""
基于邻接表和优先队列的Prim算法实现，效率更高
:param graph: 字典表示的邻接表，graph[u] = [(v, weight), ...]
:return: 最小生成树的边集合，以及总权值
"""
vertex_num = len(graph)
selected_vertices = set()
mst_edges = []
total_weight = 0
# 优先队列，存储(边权值, 起始顶点, 目标顶点)
priority_queue = []
# 起始顶点选0号
start_vertex = 0
selected_vertices.add(start_vertex)
# 将起始顶点的所有邻接边加入优先队列
for neighbor, weight in graph[start_vertex]:
heapq.heappush(priority_queue, (weight, start_vertex, neighbor))
while len(selected_vertices) < vertex_num and priority_queue:
# 取出权值最小的边
weight, u, v = heapq.heappop(priority_queue)
# 如果目标顶点已经被选中，跳过
if v in selected_vertices:
continue
# 将目标顶点加入已选集合
selected_vertices.add(v)
mst_edges.append((u, v, weight))
total_weight += weight
# 将新顶点的邻接边加入优先队列
for neighbor, w in graph[v]:
if neighbor not in selected_vertices:
heapq.heappush(priority_queue, (w, v, neighbor))
return mst_edges, total_weight
# 测试用例，邻接表表示的无向图，和上面邻接矩阵的图是同一个
test_graph_list = {
0: [(1, 2), (3, 6)],
1: [(0, 2), (2, 3), (3, 8), (4, 5)],
2: [(1, 3), (4, 7)],
3: [(0, 6), (1, 8), (4, 9)],
4: [(1, 5), (2, 7), (3, 9)]
}
edges, weight = prim_with_adj_list(test_graph_list)
print("最小生成树的边：")
for edge in edges:
print(f"顶点{edge[0]} - 顶点{edge[1]}，权值：{edge[2]}")
print(f"最小生成树总权值：{weight}")
两种实现的复杂度对比
不同实现方式的时间复杂度有明显差异，具体对比如下：
| 实现方式 | 时间复杂度 | 适用场景 |
|---|---|---|
| 邻接矩阵+暴力遍历 | O(V²)，V为顶点数 | 稠密图，顶点数量不多的情况 |
| 邻接表+优先队列 | O(E log V)，E为边数，V为顶点数 | 稀疏图，顶点数量较多的情况 |
常见问题说明
在实际使用Prim算法时需要注意几个问题：
- 如果输入的图不是连通图，算法只会返回起始顶点所在连通分量的最小生成树，剩余顶点不会被纳入
- 对于无向图，邻接矩阵需要保证
graph[i][j] == graph[j][i]，邻接表中也需要同时添加两个方向的边，否则会得到错误结果 - 优先队列的实现可以有效减少每次选最小边的时间开销，在顶点和边数量较多时推荐使用这种实现方式