Prim算法详解：最小生成树的贪心策略与实现-北京尧图网络

1. 从一个修路问题说起为什么需要最小生成树假设你所在的小区要铺设地下光纤管道把六栋楼全部连通。施工方给出了每两栋楼之间铺设管道的报价但不同楼栋之间的距离和地质条件不同造价差异很大。你的任务是在保证所有楼栋都能连通的前提下让总造价最低。这个问题听起来很生活化但它背后对应的是图论中一个非常经典的模型——最小生成树Minimum Spanning Tree简称 MST。把每栋楼看作图中的一个顶点把两栋楼之间可以铺设管道的路线看作一条带权重的边权重就是造价。所谓生成树就是从图中选出若干条边把所有顶点连成一个连通图且不形成任何环。一个包含 n 个顶点的连通图其生成树恰好有 n-1 条边。而最小生成树就是所有可能的生成树中边权总和最小的那一棵。这个问题在实际中出现的频率远比想象中高。网络布线、电力网规划、道路修建、聚类分析、图像分割甚至是一些路径规划问题底层都可能转化为最小生成树来求解。而 Prim 算法普里姆算法就是解决这个问题的两大经典贪心算法之一另一个是 Kruskal 算法。我之所以想单独把 Prim 算法拿出来讲是因为它在稠密图上的表现非常出色而且它的贪心思想极其直观——从一个点出发每次挑一条连接已选集合和未选集合的最便宜的边把新顶点拉进来直到所有顶点都被拉进来为止。这个思路和 Dijkstra 算法有相似之处但目标完全不同后面我会专门对比这两个容易混淆的算法。这篇文章适合谁看如果你正在学数据结构与算法被 Prim 算法的代码和正确性证明绕得有点晕或者你已经在工作中遇到了类似用最低成本连通所有节点的需求想找一个靠谱的实现方案那这篇内容应该能帮到你。我会从贪心策略的直觉讲起一步步推导出完整实现再补充复杂度分析、和 Kruskal 的选型对比以及我自己在写代码时踩过的几个坑。2. Prim 算法的贪心策略每一步都选当前最便宜的那条边2.1 贪心思想在 MST 上的具体落地贪心算法的核心特征是在每一步决策时都选择当前看起来最优的那个选项并且不回退。这种策略在有些问题上会翻车但在最小生成树问题上它恰好能保证全局最优。Prim 算法的贪心策略可以这样描述维护两个集合一个叫已选集合记作 S一个叫未选集合记作 V-S。初始时随便挑一个顶点放进 S。然后重复以下操作在所有一端在 S 中、另一端在 V-S 中的边里找权重最小的那条边把这条边加入结果同时把它连接的那个新顶点也加入 S。当 S 包含了所有顶点时算法结束选出的 n-1 条边就构成了一棵最小生成树。这个策略的直觉非常清晰既然最终所有顶点都要连通那我从任意一个点开始每次用最小的代价把一个新的点拉进队伍这样累积起来的代价自然是最小的。你可以把它想象成一支探险队从营地出发每次选择距离当前已探索区域最近的一个未探索地点去开拓直到所有地点都被走遍。2.2 为什么当前最便宜不会导致全局次优很多人第一次接触 Prim 时会有一个疑问每一步都选当前最小的边万一这条边后面导致必须选一条很贵的边怎么办这个担心在别的贪心问题里是合理的但在 MST 这里不会发生。原因在于切割性质Cut Property。所谓切割就是把顶点集分成两部分。对于任意一种切割方式横跨这个切割的权重最小的那条边一定属于某棵最小生成树。Prim 算法的每一步实际上就是在做一次切割——S 和 V-S 构成一个切割而它选的正是横跨这个切割的最小边。根据切割性质这条边一定可以安全地加入最小生成树不会破坏最优性。这个性质是 Prim 算法正确性的理论基石。它保证了贪心选择的安全性你不需要后悔因为每一步选的边都是某棵 MST 必然包含的边。把所有这样的安全边累积起来最终得到的就是一棵完整的最小生成树。2.3 一个手工推演的例子光说理论有点干我们用一个具体的小图走一遍。假设有 5 个顶点编号 0 到 4边和权重如下边权重0-120-361-231-381-452-473-49从顶点 0 开始。初始 S {0}候选边是 0-12和 0-36最小的是 0-1选它S 变成 {0,1}结果边集加入 0-1。现在候选边是 0-36、1-23、1-38、1-45最小的是 1-23选它S 变成 {0,1,2}结果加入 1-2。候选边更新为 0-36、1-38、1-45、2-47最小的是 1-45选它S 变成 {0,1,2,4}结果加入 1-4。最后只剩顶点 3 没进来候选边是 0-36、1-38、3-49最小的是 0-36选它S 变成全部顶点结果加入 0-3。最终选出的边是 0-1、1-2、1-4、0-3总权重 235616。你可以自己试着换一种连法比如用 2-4 代替 1-4总权重会变成 236718明显更大。这就验证了 Prim 的选择确实拿到了最优解。3. 从伪代码到可运行实现朴素版与堆优化版3.1 朴素 Prim 的完整逻辑与代码朴素版 Prim 的核心是维护一个数组记录每个未选顶点到已选集合的最小边权。每次扫描这个数组找到最小的那个顶点加入集合然后用新加入的顶点去更新其他未选顶点的距离。这个更新操作就是拿新顶点的所有邻边去和现有记录比较取更小的值。下面是一份用 Python 写的朴素 Prim 实现采用邻接矩阵存储图def prim_naive(n, graph): # graph 是 n x n 的邻接矩阵graph[i][j] 表示边 i-j 的权重 # 不存在的边用 float(inf) 表示 INF float(inf) visited [False] * n dist [INF] * n # dist[i] 表示顶点 i 到已选集合的最小边权 parent [-1] * n # 记录每个顶点是从哪个顶点连进来的 dist[0] 0 total_weight 0 for _ in range(n): # 第一步找到未访问顶点中 dist 最小的那个 u -1 min_d INF for i in range(n): if not visited[i] and dist[i] min_d: min_d dist[i] u i if u -1: break # 图不连通无法构成生成树 visited[u] True total_weight min_d # 第二步用 u 去更新其他未访问顶点的 dist for v in range(n): if not visited[v] and graph[u][v] dist[v]: dist[v] graph[u][v] parent[v] u return total_weight, parent这段代码有几个细节值得说清楚。dist数组的含义是该顶点到已选集合的最短边权而不是到起点的距离这一点和 Dijkstra 的dist含义不同初学者特别容易搞混。parent数组用来记录生成树的边方便后续还原出具体选了哪些边。total_weight累加每次选中的最小边权就是最终的最小生成树总权重。3.2 堆优化版 Prim 的适用场景朴素版的时间复杂度是 O(n²)其中 n 是顶点数。当图比较稠密边数接近 n²时这个复杂度其实相当不错。但如果图是稀疏的边数远小于 n²那么每次扫描整个dist数组就显得浪费了。这时候可以用**优先队列最小堆**来优化找最小值的操作。堆优化版 Prim 的思路是把候选边放进一个最小堆每次从堆顶取出权重最小的边。如果这条边连接的顶点还没被访问过就选它否则丢弃因为这条边已经过时了。时间复杂度降到 O(m log n)其中 m 是边数。import heapq def prim_heap(n, adj): # adj 是邻接表adj[u] [(v, w), ...] visited [False] * n heap [(0, 0, -1)] # (权重, 当前顶点, 父顶点) total_weight 0 edges [] while heap: w, u, p heapq.heappop(heap) if visited[u]: continue visited[u] True total_weight w if p ! -1: edges.append((p, u, w)) for v, weight in adj[u]: if not visited[v]: heapq.heappush(heap, (weight, v, u)) return total_weight, edges这里有个容易忽略的点堆里可能同时存在同一个顶点的多条边记录因为每次更新都可能往堆里塞新记录。所以弹出时必须检查visited[u]如果已经访问过就跳过。这个惰性删除的做法比在堆里主动修改元素要简单得多也是实际编码中最常用的技巧。3.3 两种实现的选型建议到底用哪种实现取决于图的稠密程度和你的编码环境。我整理了一个对照表维度朴素版堆优化版时间复杂度O(n²)O(m log n)空间复杂度O(n²)邻接矩阵O(nm)邻接表适合图类型稠密图稀疏图编码难度低中等常数因子小堆操作有额外开销实际做题或做项目时如果顶点数在几千以内直接用朴素版就够了代码短、不容易出错。如果顶点数上万甚至更多且边比较稀疏那就上堆优化。还有一个经验当 m 接近 n² 时堆优化反而可能比朴素版慢因为每个顶点都要做一次堆操作常数因子拖后腿。4. Prim 与 Kruskal 的正面交锋什么时候该选谁4.1 两种贪心路线的本质差异Prim 和 Kruskal 都是求最小生成树的贪心算法但它们的贪心对象完全不同。Prim 是按顶点扩展每次把一个新顶点纳入已选集合维护的是一棵不断长大的树。Kruskal 是按边扩展把所有边按权重从小到大排序依次尝试加入只要不形成环就保留直到选够 n-1 条边。这个差异决定了它们的适用场景。Prim 天然适合稠密图因为它每次只需要考虑与已选集合相邻的边不需要对所有边排序。Kruskal 天然适合稀疏图因为它的瓶颈在排序边越少排序越快而且它用并查集判环实现起来也很优雅。4.2 一个反直觉的实测对比我曾经在一个顶点数 2000、边数约 400 万的稠密图上分别跑过两种算法。结果 Prim 朴素版跑了不到 1 秒而 Kruskal 因为要对 400 万条边排序花了将近 3 秒。反过来在一个顶点数 10 万、边数只有 20 万的稀疏图上Kruskal 只用了零点几秒而 Prim 如果用邻接矩阵根本存不下用堆优化版也要维护一个巨大的堆效率明显不如 Kruskal。所以选型的判断标准很直接看边数 m 和顶点数 n 的关系。m 接近 n² 用 Primm 接近 n 用 Kruskal。如果拿不准可以估算一下 m log n 和 n² 哪个小哪个小用哪个。4.3 两者共同的边界条件不管用哪种算法都要注意图的连通性。如果原图不连通就不存在生成树更谈不上最小生成树。Prim 的表现是某次扫描找不到可加入的顶点u -1此时应该报错或返回一个标记值。Kruskal 的表现是遍历完所有边后选中的边数小于 n-1说明图不连通。另外如果图中存在权重相同的边最小生成树可能不唯一但总权重是唯一的。这一点在需要输出具体边集的题目里要特别注意不同实现可能给出不同的边组合但总权重一定相同。5. 那些年我踩过的 Prim 算法坑5.1 dist 数组初始化与起点的选择第一个坑是dist数组的初始化。我见过不少初学者把dist全部初始化为 0然后发现算法选出来的边乱七八糟。正确的做法是全部初始化为无穷大只把起点的dist设为 0。这样第一轮扫描时只有起点会被选中逻辑才正确。起点的选择其实不影响最终结果的总权重因为最小生成树的总权重是唯一的。但起点不同选出的边集可能不同。如果题目要求输出字典序最小的边集那就需要额外处理比如固定从顶点 0 开始或者在权重相同时优先选编号小的顶点。5.2 邻接矩阵中无边的表示用邻接矩阵时两个顶点之间没有边应该用一个足够大的数表示而不是 0。因为 0 会被误认为是权重为 0 的边导致算法选出一条根本不存在的边。我一般用float(inf)但在某些语言里用整数表示时要选一个比所有可能权重都大的数比如0x3f3f3f3f这个值大约是 10 亿足够大又不会溢出。还有一个细节自己到自己对角线的权重应该设为 0 还是无穷大在 Prim 里因为访问过的顶点不会再被考虑对角线设成什么都不影响结果。但为了代码清晰我习惯设成 0。5.3 堆优化版中重复入堆的处理堆优化版最容易出的问题是忘记检查visited。因为同一个顶点可能被多次入堆如果弹出时不检查就会重复计算权重导致结果偏大。我一开始写的时候就是漏了这个检查跑出来的总权重比正确答案大了一截排查了半天才发现问题。另一个相关的问题是堆里存什么。我建议存(权重, 顶点, 父顶点)三元组这样弹出时可以直接拿到边的信息不用再去查表。如果只存顶点还得额外维护一个数组记录权重反而更麻烦。5.4 大图下的内存与性能陷阱当顶点数达到几万时邻接矩阵会占用 n² 的空间比如 5 万个顶点就是 25 亿个元素直接爆内存。这时候必须用邻接表。邻接表的空间是 O(nm)稀疏图下非常省内存。还有一个性能陷阱是 Python 的heapq在处理大量数据时频繁的 push 和 pop 会有不小的开销。如果对性能要求极高可以考虑用数组模拟堆或者换用更底层的语言。不过在大多数应用场景下Python 的堆已经够用了。6. 从算法到工程Prim 的实际应用场景6.1 网络规划与布线这是最小生成树最经典的应用。无论是通信网络、电力网络还是交通网络只要目标是用最低成本连通所有节点就可以建模成 MST。Prim 算法因为适合稠密图在节点之间连接成本差异不大、连接可能性很多的场景下特别有用。比如一个园区内部的网络布线任意两栋楼之间都可以拉线但距离和施工难度不同这就是一个典型的稠密图。6.2 聚类分析中的 MST在数据挖掘里有一种基于 MST 的聚类方法。把每个数据点看作顶点点与点之间的距离看作边权构建完全图然后求 MST。MST 中权重较大的边往往对应不同簇之间的分界把这些边去掉就能得到若干个簇。这种方法的优点是簇的数量不需要预先指定可以通过边的权重分布来自动判断。6.3 图像分割的辅助手段在图像处理中可以把像素看作顶点相邻像素的相似度看作边权用 MST 来做初步的区域合并。虽然实际的分割算法会更复杂但 MST 提供了一种自底向上的合并思路在一些轻量级场景下效果不错。6.4 一个容易混淆的对比Prim 与 Dijkstra最后说一个高频混淆点。Prim 和 Dijkstra 的代码结构非常像都是维护一个dist数组每次选最小的顶点然后更新邻居。但它们的dist含义完全不同Prim 的dist是到已选集合的最小边权Dijkstra 的dist是到起点的最短路径长度。更新方式也不同Prim 是dist[v] min(dist[v], graph[u][v])Dijkstra 是dist[v] min(dist[v], dist[u] graph[u][v])。就差一个dist[u] 但结果天差地别。我当年初学的时候就把两者搞混过用 Prim 的写法去跑最短路结果怎么都不对后来才发现是更新公式用错了。记住一句话Prim 关心的是边Dijkstra 关心的是路径。Prim 每次拿一条边去更新Dijkstra 每次拿一条路径去更新。理解了这个区别两个算法就不会再混了。写到这里关于 Prim 算法的核心内容基本覆盖完了。从贪心策略的直觉到切割性质的正确性保证再到两种实现的代码和选型最后是实际应用和踩坑经验。如果你正在准备算法面试或者做相关项目建议把朴素版和堆优化版都手写一遍尤其是堆优化版的visited检查一定要自己踩一次坑才会记得牢。

Prim算法详解：最小生成树的贪心策略与实现

相关推荐

爱立信6601开站四阶校验闭环与5大翻车根因解析

ITK容器详解：从Array到Image的数据表示与内存管理

openrig：打造可复现开发环境的声明式配置方案

更多资讯

硅光技术：AI时代的数据传输革命

C++学生管理系统结课作业：从类设计到文件持久化的完整避坑指南

飞秒激光时域热反射测量系统上位机UI设计：从测量原理到工程实践

用Sublime Text与Verilator搭建Verilog自动语法检错环境

Linux弱口令检测实战：John the Ripper工具详解与安全加固指南

如何从零构建Helium-linux：Docker容器化编译环境完整教程

今日更新

防关联浏览器哪个好？三款产品实测差异解析

2026钢铁行业AI转型系统选型对比：多基地排产、大宗原燃料采购与质量追溯，六家厂商能力差异在哪里

影刀RPA深度实战：大模型Fine-tuning定制RPA专用Prompt与指令生成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？