一、什么是 Prim 算法？
Prim 算法是一种最小生成树算法，由 Robert Prim 在 1957 年提出。它的核心思想是从一个起点出发，每次选择离当前连通分量最近的节点，将其加入连通分量，直到所有节点都连通，最终得到一棵总权重最小的生成树。
简单来说，Prim 算法就像 “从北京出发，逐步连通全国 34 个省份”：
- 先从北京开始，找到离北京最近的天津，把它们连起来；
- 再从当前连通的城市中，找到离它们最近的河北，连起来；
- 重复这个过程，每次只连最近的城市，直到所有省份都连通；
- 这样连出来的公路总长度最短，也就是最小生成树。
二、Prim 算法的核心步骤
Prim 算法的核心步骤可以分为以下几步：
三、Prim 算法的代码实现
1. Python 版本（直观易懂）
import heapq
def prim(graph, start):
# 初始化距离：所有节点距离设为无穷大
distances = {node: float('inf') for node in graph}
distances[start] = 0
# 优先队列：存储（距离，节点），距离小的优先
priority_queue = []
heapq.heappush(priority_queue, (0, start))
# 记录是否已加入连通分量
in_mst = {node: False for node in graph}
# 记录路径
path = {node: None for node in graph}
total_weight = 0
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# 如果当前节点已加入连通分量，跳过
if in_mst[current_node]:
continue
# 加入连通分量
in_mst[current_node] = True
total_weight += current_distance
# 遍历邻居
for neighbor, weight in graph[current_node].items():
if not in_mst[neighbor] and weight < distances[neighbor]:
distances[neighbor] = weight
path[neighbor] = current_node
heapq.heappush(priority_queue, (weight, neighbor))
return total_weight, path
# 测试：全国34个省份连通问题
graph = {
'北京': {'天津': 110, '河北': 263, '山西': 337},
'天津': {'北京': 110, '河北': 269},
'河北': {'北京': 263, '天津': 269, '山西': 174, '山东': 269, '河南': 360},
'山西': {'北京': 337, '河北': 174, '内蒙古': 337, '河南': 360, '陕西': 435},
'山东': {'河北': 269, '河南': 466, '安徽': 446},
'河南': {'河北': 360, '山西': 360, '山东': 466, '陕西': 435, '湖北': 310, '安徽': 466},
'安徽': {'山东': 446, '河南': 466, '江苏': 149, '湖北': 310, '浙江': 238},
'江苏': {'安徽': 149, '上海': 165, '浙江': 238},
'上海': {'江苏': 165, '浙江': 165},
'浙江': {'安徽': 238, '江苏': 238, '上海': 165, '福建': 447, '江西': 261},
'湖北': {'河南': 310, '安徽': 310, '江西': 261, '湖南': 287, '陕西': 435},
'江西': {'湖北': 261, '浙江': 261, '福建': 447, '湖南': 287, '广东': 568},
'湖南': {'湖北': 287, '江西': 287, '广东': 568, '广西': 411, '贵州': 373},
'福建': {'浙江': 447, '江西': 447, '台湾': 250, '广东': 568},
'台湾': {'福建': 250},
'广东': {'江西': 568, '湖南': 568, '福建': 568, '广西': 411, '海南': 411, '香港': 65, '澳门': 65},
'广西': {'湖南': 411, '广东': 411, '海南': 373, '贵州': 373, '云南': 461},
'海南': {'广东': 411, '广西': 373},
'香港': {'广东': 65},
'澳门': {'广东': 65},
'贵州': {'湖南': 373, '广西': 373, '云南': 461, '重庆': 325},
'云南': {'广西': 461, '贵州': 461, '四川': 433, '西藏': 1248},
'重庆': {'贵州': 325, '四川': 263, '陕西': 507},
'四川': {'重庆': 263, '云南': 433, '西藏': 1248, '青海': 507, '甘肃': 507},
'西藏': {'云南': 1248, '四川': 1248, '青海': 1441},
'青海': {'四川': 507, '西藏': 1441, '甘肃': 507, '新疆': 1441},
'甘肃': {'四川': 507, '青海': 507, '陕西': 507, '宁夏': 345, '新疆': 1441},
'陕西': {'山西': 435, '河南': 435, '湖北': 435, '重庆': 507, '四川': 507, '甘肃': 507, '宁夏': 345},
'宁夏': {'陕西': 345, '甘肃': 345, '内蒙古': 337},
'内蒙古': {'山西': 337, '宁夏': 337, '辽宁': 605},
'辽宁': {'内蒙古': 605, '吉林': 280, '河北': 605},
'吉林': {'辽宁': 280, '黑龙江': 230},
'黑龙江': {'吉林': 230},
'新疆': {'甘肃': 1441, '青海': 1441}
}
total_weight, path = prim(graph, '北京')
print("最小生成树总权重：", total_weight)
print("路径：", path)
2. C 语言版本（更贴近底层）
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define INF INT_MAX
#define N 34 // 全国34个省份
// 省份名称
char* provinces[] = {
"北京", "天津", "河北", "山西", "山东", "河南", "安徽", "江苏", "上海", "浙江",
"湖北", "江西", "湖南", "福建", "台湾", "广东", "广西", "海南", "香港", "澳门",
"贵州", "云南", "重庆", "四川", "西藏", "青海", "甘肃", "陕西", "宁夏", "内蒙古",
"辽宁", "吉林", "黑龙江", "新疆"
};
// 图的邻接矩阵
int graph[N][N] = {
{0, 110, 263, 337, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{110, 0, 269, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{263, 269, 0, 174, 269, 360, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{337, INF, 174, 0, INF, 360, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 435, INF, 337, INF, INF, INF, INF},
{INF, INF, 269, INF, 0, 466, 446, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, 360, 360, 466, 0, 466, INF, INF, INF, 310, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 435, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, 446, 466, 0, 149, INF, 238, 310, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, 149, 0, 165, 238, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, 165, 0, 165, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, 238, 238, 165, 0, INF, 261, INF, 447, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, 310, 310, INF, INF, INF, 0, 261, 287, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 435, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, 261, 261, 0, 287, 447, INF, 568, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 287, 287, 0, INF, INF, 568, 411, INF, INF, INF, 373, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, 447, INF, 447, INF, 0, 250, 568, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 250, 0, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 568, 568, 568, INF, 0, 411, 411, 65, 65, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 411, INF, INF, 411, 0, 373, INF, INF, 373, 461, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 411, 373, 0, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 65, INF, INF, 0, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 65, INF, INF, INF, 0, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 373, INF, INF, INF, 373, INF, INF, INF, 0, 461, 325, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 461, INF, INF, INF, 461, 0, INF, 433, 1248, INF, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 325, INF, 0, 263, INF, INF, INF, 507, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 433, 263, 0, 1248, 507, 507, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 1248, INF, 1248, 0, 1441, INF, INF, INF, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 507, 1441, 0, 507, INF, INF, INF, INF, INF, INF, 1441},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 507, INF, 507, 0, 507, 345, INF, INF, INF, INF, 1441},
{INF, INF, INF, INF, INF, 435, INF, INF, INF, INF, 435, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 507, INF, INF, INF, 507, 0, 345, INF, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 345, 345, 0, 337, INF, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 337, 0, 605, INF, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 605, 0, 280, INF, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 280, 0, 230, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 230, 0, INF},
{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 1441, 1441, INF, INF, INF, INF, INF, INF, 0}
};
// Prim算法
void prim(int start) {
int dist[N]; // 存储到连通分量的最短距离
int in_mst[N]; // 标记是否已加入连通分量
int path[N]; // 记录路径
int total_weight = 0;
// 初始化
for (int i = 0; i < N; i++) {
dist[i] = INF;
in_mst[i] = 0;
path[i] = -1;
}
dist[start] = 0;
for (int count = 0; count < N; count++) {
// 找到离连通分量最近的未加入节点
int min_dist = INF, u = -1;
for (int i = 0; i < N; i++) {
if (!in_mst[i] && dist[i] < min_dist) {
min_dist = dist[i];
u = i;
}
}
// 加入连通分量
in_mst[u] = 1;
total_weight += min_dist;
// 更新邻居的距离
for (int v = 0; v < N; v++) {
if (!in_mst[v] && graph[u][v] != INF && graph[u][v] < dist[v]) {
dist[v] = graph[u][v];
path[v] = u;
}
}
}
// 打印结果
printf("起点：%s\\n", provinces[start]);
printf("最小生成树总权重：%d\\n", total_weight);
printf("路径：\\n");
for (int i = 0; i < N; i++) {
if (path[i] != -1) {
printf("%s -> %s，权重：%d\\n", provinces[path[i]], provinces[i], graph[path[i]][i]);
}
}
}
int main() {
prim(0); // 从北京出发
return 0;
}
四、Prim 算法的特点
- 时间复杂度：O (n²)（朴素实现），O (m log n)（优先队列实现）；
- 空间复杂度：O (n)，需要存储距离和访问标记；
- 适用场景：稠密图，边数较多的图；
- 从点出发：从一个起点出发，逐步扩展连通分量。
五、Prim 算法的优化
为了提高 Prim 算法的效率，可以进行以下优化：
六、Prim 算法的实际应用场景
Prim 算法是一种非常基础且重要的算法，常见场景包括：
七、Prim 算法 vs Kruskal 算法
Prim 算法和 Kruskal 算法是两种最常用的最小生成树算法，它们的区别如下：
八、总结
Prim 算法是一种最小生成树算法，它通过从一个起点出发，每次选择离当前连通分量最近的节点，将其加入连通分量，直到所有节点都连通，最终得到一棵总权重最小的生成树。
Prim 算法的核心是优先选择最近的节点，适合稠密图，在网络设计、集群计算、图像处理等领域广泛应用。
希望这篇文章能帮助你理解 Prim 算法的原理和实现！
