普利姆（Prim）
普利姆算法（Prim's Algorithm） 是一种用于在带权无向连通图中求解 最小生成树 的经典贪心算法。
提出者：1930 年由捷克数学家沃伊捷赫·亚尔尼克（Vojtěch Jarník）首次提出；1957 年由美国计算机科学家罗伯特·普里姆（Robert C. Prim）重新发现；1959 年艾兹格·迪杰斯特拉（Edsger W. Dijkstra）再次独立提出该算法。
别名：因此该算法也被称为 Jarník 算法或 Prim–Jarník 算法。
核心思想：从任意一个顶点开始，不断地在已加入生成树的顶点集合与尚未加入的顶点集合之间，选择一条权值最小的边，将新顶点纳入生成树，直到所有顶点都被包含。
1、前置知识
1.1 生成树的性质
一个含 n 个顶点的连通图，其生成树恰好包含 n 个顶点、n−1 条边；
生成树中不存在环；
在生成树中任意添加一条边，必然形成且仅形成一个环；
最小生成树可能不唯一（当存在权值相等的边时），但其总权值唯一。
1.2 切分性质（Cut Property）
将图的顶点划分为两个集合 S 和 V−S，连接这两个集合的边称为横跨切分的边（crossing edge）。
切分定理：在所有横跨切分的边中，权值最小的那条边一定属于某棵最小生成树。
普利姆算法正是切分定理的直接应用 —— 每一步都在树内集合 {S} 与 树外集合 {V−S} 的切分上选取最短横跨边，因此贪心选择是安全的。
2、算法核心思想
普利姆算法可以概括为 从一个点长成一棵树：
初始时任选一个顶点，把它放入已选集合 S（此时生成树只有一个孤立顶点）；
维护树外每个顶点到集合 S 的**最短距离**（即该顶点与 S 中任一顶点相连边的最小权值）；
每次从树外选出距离 S 最近的顶点 u，将它及其对应的最短边加入生成树；
用 u 更新其余树外顶点到 S 的最短距离（松弛操作）；
重复步骤 3、4，直到 S 包含全部 n 个顶点。
整个过程与 Dijkstra 最短路径算法 极为相似，区别仅在于：Dijkstra 维护的是到源点的距离，而 Prim 维护的是到整棵生成树集合 S 的距离。
3、算法步骤
设图为 G = (V, E)，顶点编号 0 ~ n−1，使用三个辅助数组：
步骤：
初始化：任选起点（通常为顶点 0），令
lowCost[0] = 0，其余顶点lowCost[i] = ∞，parent[i] = -1。选点：重复 n 次，在所有未加入树的顶点中选出
lowCost最小的顶点 u，标记inMST[u] = true。记录边：若
parent[u] != -1，将边(parent[u], u)及其权值加入 MST。更新（松弛）：遍历 u 的所有邻接顶点 v，若 v 不在树中且边权
w(u,v) < lowCost[v]，则更新：lowCost[v] = w(u,v)parent[v] = u
终止：当所有顶点都加入树后，共得到 n−1 条边，算法结束；总权值即为各边权值之和。
4、手动模拟示例
以下图为例（边上数字为权值）：
从顶点 A 开始：
最小生成树的边：A–B(2)、B–D(3)、D–F(2)、D–C(4)、C–E(7)
总权值 = 2 + 3 + 2 + 4 + 7 = 18
5、伪代码
5.1 基础版本（邻接矩阵 + 线性查找）
算法：Prim(G, start)
输入：带权无向连通图 G（n 个顶点），起点 start
输出：最小生成树的边集合及其总权值
for i ← 0 to n-1 do
lowCost[i] ← ∞
parent[i] ← -1
inMST[i] ← false
lowCost[start] ← 0
totalWeight ← 0
for count ← 1 to n do
// 1. 选出树外 lowCost 最小的顶点
u ← -1
min ← ∞
for i ← 0 to n-1 do
if not inMST[i] and lowCost[i] < min then
min ← lowCost[i]
u ← i
// 2. 加入生成树
inMST[u] ← true
totalWeight ← totalWeight + lowCost[u]
if parent[u] ≠ -1 then
输出边 (parent[u], u)，权值 lowCost[u]
// 3. 用 u 松弛其余顶点
for v ← 0 to n-1 do
if not inMST[v] and weight[u][v] < lowCost[v] then
lowCost[v] ← weight[u][v]
parent[v] ← u
return totalWeight5.2 优化版本（邻接表 + 最小堆）
算法：PrimWithHeap(G, start)
lowCost[start] ← 0，其余为 ∞
最小堆 H ← {(0, start)} // (距离, 顶点)
inMST 全部为 false
edges ← 空，totalWeight ← 0
while H 非空 且 edges 数量 < n-1 do
(w, u) ← H.popMin()
if inMST[u] then continue // 过期条目，跳过
inMST[u] ← true
totalWeight ← totalWeight + w
if u ≠ start then edges.add(parent[u], u)
for each (v, weight) in adj[u] do
if not inMST[v] and weight < lowCost[v] then
lowCost[v] ← weight
parent[v] ← u
H.push((weight, v)) // 懒插入，不删除旧条目
return edges, totalWeight6、代码实现
6.1 Python：邻接矩阵版本（适合稠密图，O(n²)）
import sys
def prim_matrix(graph, start=0):
"""
:param graph: n×n 邻接矩阵，graph[i][j] 为边权，无边时为 INF
:param start: 起始顶点
:return: (MST 边列表, 总权值)
"""
n = len(graph)
INF = sys.maxsize
low_cost = [INF] * n
parent = [-1] * n
in_mst = [False] * n
low_cost[start] = 0
mst_edges = []
total_weight = 0
for _ in range(n):
# 1. 线性查找树外最小 lowCost 顶点
u = -1
minimum = INF
for i in range(n):
if not in_mst[i] and low_cost[i] < minimum:
minimum = low_cost[i]
u = i
if u == -1: # 图不连通，不存在生成树
raise ValueError("图不连通，无法生成最小生成树")
# 2. 加入生成树
in_mst[u] = True
total_weight += low_cost[u]
if parent[u] != -1:
mst_edges.append((parent[u], u, low_cost[u]))
# 3. 松弛邻接点
for v in range(n):
if not in_mst[v] and graph[u][v] < low_cost[v]:
low_cost[v] = graph[u][v]
parent[v] = u
return mst_edges, total_weight
# 对应第五节示例（A=0, B=1, C=2, D=3, E=4, F=5）
INF = sys.maxsize
graph = [
[0, 2, 6, 5, INF, INF],
[2, 0, INF, 3, INF, INF],
[6, INF, 0, 4, 7, INF],
[5, 3, 4, 0, INF, 2 ],
[INF, INF, 7, INF, 0, 8 ],
[INF, INF, INF, 2, 8, 0 ],
]
edges, total = prim_matrix(graph)
print("MST 边：", edges) # [(0,1,2), (1,3,3), (3,5,2), (3,2,4), (2,4,7)]
print("总权值：", total) # 186.2 Python：邻接表 + 最小堆版本（适合稀疏图，O(E log V)）
import heapq
def prim_heap(adj, start=0):
"""
:param adj: 邻接表，adj[u] = [(v, weight), ...]
:param start: 起始顶点
:return: (MST 边列表, 总权值)
"""
n = len(adj)
INF = float("inf")
low_cost = [INF] * n
parent = [-1] * n
in_mst = [False] * n
low_cost[start] = 0
heap = [(0, start)]
mst_edges = []
total_weight = 0
while heap and len(mst_edges) < n - 1:
w, u = heapq.heappop(heap)
if in_mst[u]:
continue # 堆中残留的过期条目
in_mst[u] = True
total_weight += w
if parent[u] != -1:
mst_edges.append((parent[u], u, w))
for v, weight in adj[u]:
if not in_mst[v] and weight < low_cost[v]:
low_cost[v] = weight
parent[v] = u
heapq.heappush(heap, (weight, v))
if len(mst_edges) != n - 1:
raise ValueError("图不连通，无法生成最小生成树")
return mst_edges, total_weight
# 同一示例的邻接表写法
adj = [
[(1, 2), (2, 6), (3, 5)],
[(0, 2), (3, 3)],
[(0, 6), (3, 4), (4, 7)],
[(0, 5), (1, 3), (2, 4), (5, 2)],
[(2, 7), (5, 8)],
[(3, 2), (4, 8)],
]
edges, total = prim_heap(adj)
print("MST 边：", edges)
print("总权值：", total)6.3 Java：邻接矩阵版本
public class Prim {
public static void prim(int[][] graph, int start) {
int n = graph.length;
int INF = Integer.MAX_VALUE;
int[] lowCost = new int[n];
int[] parent = new int[n];
boolean[] inMST = new boolean[n];
for (int i = 0; i < n; i++) {
lowCost[i] = INF;
parent[i] = -1;
}
lowCost[start] = 0;
int totalWeight = 0;
for (int count = 0; count < n; count++) {
// 选出树外 lowCost 最小的顶点
int u = -1, min = INF;
for (int i = 0; i < n; i++) {
if (!inMST[i] && lowCost[i] < min) {
min = lowCost[i];
u = i;
}
}
inMST[u] = true;
totalWeight += lowCost[u];
if (parent[u] != -1) {
System.out.printf("边 (%d, %d)，权值 %d%n",
parent[u], u, lowCost[u]);
}
// 松弛
for (int v = 0; v < n; v++) {
if (!inMST[v] && graph[u][v] != 0 && graph[u][v] < lowCost[v]) {
lowCost[v] = graph[u][v];
parent[v] = u;
}
}
}
System.out.println("MST 总权值：" + totalWeight);
}
}7、正确性证明
结论： 普利姆算法输出的边集一定是一棵最小生成树。
证明（基于切分定理 + 归纳法）：
归纳基础：初始时 S 中只有起点，树为空。空集是任意一棵 [[最小生成树]] 的子集，命题成立。
归纳假设：假设算法第 k 步选出的边集 T 已包含于某棵最小生成树 T* 中，且这些边恰好覆盖顶点集合 S。
归纳步骤：第 k+1 步，算法选取横跨切分 (S, V−S) 的最小权边 e = (u, v)，其中 u ∈ S，v ∉ S。
若 e 已在 T 中，则 T ∪ {e} ⊆ T，假设继续成立；
若 e 不在 T 中，由于 T 是生成树，T 中必有另一条横跨该切分的边 e′ 将 v 连入。由切分定理，w(e) ≤ w(e′)。在 T 中用 e 替换 e′：
替换后仍连通、仍含 n−1 条边、仍无环，故仍是一棵生成树；
由于 w(e) ≤ w(e′)，新树总权值不增，它仍是最小生成树。
因而总能找到一棵包含 T ∪ {e} 的 [[最小生成树]]。
归纳终止：算法结束时 S = V，T 含 n−1 条边且包含于某棵 [[最小生成树]]，故 T 本身就是一棵最小生成树。∎
注意：上述证明要求边权有明确大小关系。当存在负权边时算法依然成立（MST 允许负权），因为切分定理对任意权值都有效；但若图不连通，则无法得到生成树（只能得到最小生成森林）。
8、复杂度分析
说明：
选点共执行 n 次；线性扫描每次 O(V)，合计 O(V²)；
堆版本中每条边至多触发一次"松弛入堆"，每次堆操作为 O(log V)，合计 O(E log V)；
当图为完全图时 E ≈ V²，此时 O(E log V) = O(V² log V)，反而不如矩阵版本，因此稠密图优先选矩阵实现。
9、Prim 与 克鲁斯卡尔-kruskal-算法的对比
两者都基于贪心、都能求出 最小生成树，但策略不同：
经验选择：
稠密图（如路网、完全图）→ Prim
稀疏图（如社交网络、通信骨干网）→ Kruskal
10、典型应用场景
网络建设：城市间铺设光纤/电缆/自来水管，以最小成本连通所有节点；
电路板布线：连接芯片上各引脚，使总线长最短（经典的 Steiner 树问题常用 MST 作近似）；
聚类分析：单链凝聚层次聚类（Single-linkage Clustering）本质上基于 MST，删除最长的 k−1 条边即得到 k 个簇；
图像分割：基于图割（Graph-based Segmentation）的方法利用 MST 结构合并相似区域；
旅行商问题近似：TSP 的 MST 近似算法（度量空间下 2-近似）以 MST 为基础；
游戏与地图生成：程序化生成地牢、道路、迷宫（在 MST 上额外加边可形成带环路径）；
分布式系统：设计最小开销的广播/组播生成树，减少冗余通信。
11、常见易错点与注意事项
图必须连通（单棵 MST 情形）：若图不连通，矩阵版本会选到
lowCost = ∞的顶点，堆版本最终边数不足 n−1，需单独处理。无向图存两条有向边：邻接表中
(u,v,w)要同时加入adj[u]和adj[v]。lowCost 不是到起点的距离：它是顶点到"当前整棵树集合 S"的最小边权，这是与 Dijkstra 最容易混淆之处。
起点任意：无论选哪个顶点开始，最终 MST 的总权值相同（树的形态可能不同）。
堆中允许过期条目：优化版本采用"懒删除"——弹出时若顶点已在树中则直接跳过，不必实现 decrease-key。
权值相等：图中若存在多条等权最短横跨边，任选其一即可，MST 可能有多棵但总权值一致。
自环与重边：自环永远不会被选（松弛时顶点在树内被排除）；重边在矩阵中只保留最小权、在邻接表中可共存不影响正确性。
12、知识小结
普利姆算法是求解最小生成树的贪心算法，依据切分性质保证正确性；
流程上"起点入树 → 选最短横跨边 → 新点入树 → 更新距离"循环 n−1 次；
两种主流实现：邻接矩阵 O(V²) 应对稠密图，邻接表 + 最小堆 O(E log V) 应对稀疏图；
与 Kruskal（排序 + 并查集） 互补，按图的稠密程度选型；
广泛应用于网络规划、聚类、图像分割、TSP 近似、程序化内容生成等领域。
一句话记忆：Prim 是从一棵树长成一片林网，每一步都把离树最近的那个点接进来。
- 感谢你赐予我前进的力量
-
微信 
支付宝
