1. 从一个真实场景说起为什么我们需要最小生成树很多人第一次接触最小生成树这个概念是在算法课上听老师念PPT什么“带权无向连通图”“边权和最小”“无环子图”听完一头雾水考试前背个模板就过去了。但如果你真的在工程里遇到过这类问题你会发现它其实非常接地气。我最早碰到这个问题是帮一个做园区网络规划的朋友处理布线方案。园区里有若干栋楼楼与楼之间要铺光纤不同楼之间的距离不同铺设成本自然也不同。目标很简单让所有楼都连通但总铺设长度最短。这就是一个典型的最小生成树问题——把楼看成图的顶点把楼与楼之间可铺设的链路看成边边的权重就是距离或成本我们要找一棵包含所有顶点、边权和最小的树。最小生成树Minimum Spanning Tree简称MST解决的问题就是在一个带权无向连通图中找出一棵包含全部顶点、且所有边权之和最小的生成树。注意两个关键词——“包含全部顶点”和“边权和最小”。它不关心路径长短只关心整体代价最低。那为什么标题里特别强调“贪心”和“Prim算法”呢因为解决MST有两大经典贪心算法Prim普里姆和Kruskal克鲁斯卡尔。Prim的思路是“从一个点出发不断把离当前树最近的顶点拉进来”像滚雪球一样越滚越大Kruskal则是“把所有边按权重排序从小到大挑只要不形成环就要”。两者都是贪心策略但适用场景不同。Prim更适合稠密图尤其是用邻接矩阵存储的时候时间复杂度是O(V²)用优先队列优化后可以做到O(E log V)Kruskal则更适合稀疏图复杂度主要花在排序上O(E log E)。这篇文章我会把Prim算法从思路到实现、从朴素版本到堆优化版本、从正确性证明到常见坑点全部拆开讲清楚。不管你是正在准备算法面试还是工作中真要处理类似布线、聚类、图像分割这类问题都能直接拿去用。代码我会用Python和C各写一版方便不同背景的读者对照。2. Prim算法的核心思路拆解贪心为什么能work2.1 贪心策略的直观理解Prim算法的核心思想可以用一句话概括维护一棵不断生长的树每次从“树内顶点”到“树外顶点”的所有边中挑一条权值最小的边把对应的树外顶点加进来。你可以把它想象成盖房子。一开始你只有一块地基随便选一个起点然后你想把周围的材料一点点搬进来。每次你都会选离当前工地最近的那堆材料先搬搬完之后工地变大了可选的“最近材料”也可能变了。重复这个过程直到所有材料都搬完。这个策略为什么是对的直觉上如果你最终要连通所有点那么连接“已经连通的集合”和“还没连通的集合”之间的那条最小边一定属于某棵最小生成树。这个性质叫做切割性质Cut Property是Prim和Kruskal共同的理论基础。2.2 切割性质Prim正确性的理论支撑正式一点说把图的顶点分成两个不相交的集合S和V-S横跨这两个集合的边中权值最小的那条边一定存在于某棵最小生成树中。证明思路用反证法假设这条最小横切边e不在某棵MST中那么把这棵MST加上e会形成一个环。由于e横跨S和V-S这个环上必然还有另一条边e也横跨这两个集合。根据假设e的权值小于等于e那么用e替换e得到的仍然是一棵生成树而且总权值不会变大。这就说明存在一棵包含e的MST。Prim算法每一步都在做这样一次切割S是当前已经加入树的顶点集合V-S是还没加入的。每次选的最小横切边根据切割性质一定可以安全地加入当前的部分MST中不会导致最终结果不是最优。2.3 Prim与Kruskal的选型对比很多人会纠结到底用Prim还是Kruskal。我个人的经验是看图的稠密程度和存储方式对比维度Prim算法Kruskal算法核心操作扩展顶点维护距离数组排序边并查集判环时间复杂度朴素O(V²)O(E log E)时间复杂度优化O(E log V) 用优先队列O(E log E) 排序为主适用图类型稠密图E接近V²稀疏图E远小于V²存储结构邻接矩阵或邻接表边集数组是否依赖起点是但结果权值相同否实现难度中等中等偏易稠密图比如完全图E≈V²这时候Prim的O(V²)反而比Kruskal的O(E log E)O(V² log V)更优。稀疏图比如道路网E≈VKruskal的排序开销小更合适。当然如果Prim用二叉堆优化复杂度是O(E log V)在稀疏图上和Kruskal差不多但常数可能略大。注意Prim算法要求图是连通的。如果图不连通Prim只能得到其中一个连通分量的最小生成树。要处理非连通图需要对每个连通分量分别跑Prim得到的是“最小生成森林”。3. 朴素Prim算法完整实现从伪代码到可运行代码3.1 数据结构设计与初始化朴素Prim通常用邻接矩阵存图因为每次要快速查询“树内顶点到树外顶点的边权”。我们维护几个关键数组key[]记录每个顶点到当前树的最小边权初始为无穷大起点设为0。inMST[]布尔数组标记顶点是否已经加入树。parent[]记录每个顶点在MST中的父节点用于最后输出边集。初始化时所有顶点的key设为INFparent设为-1inMST全为false。然后选一个起点通常选0号顶点把它的key设为0。3.2 逐步扩展过程详解每一轮循环做三件事在还没加入MST的顶点中找key值最小的那个顶点u。把u标记为已加入MST。遍历u的所有邻接顶点v如果v还没加入MST且边(u,v)的权值小于key[v]就更新key[v]和parent[v]。这个过程重复V次每次加入一个顶点直到所有顶点都在MST中。我用一个具体的小例子走一遍。假设有5个顶点邻接矩阵如下INF表示不直接相连0 1 2 3 4 0 0 2 3 INF INF 1 2 0 1 4 INF 2 3 1 0 5 6 3 INF 4 5 0 7 4 INF INF 6 7 0从顶点0开始key[0,INF,INF,INF,INF]。第一轮选0更新邻居1的key22的key3。第二轮在未加入的{1,2,3,4}中选key最小的1key2加入1更新2的keymin(3,1)13的key4。第三轮选2key1加入2更新3的keymin(4,5)44的key6。第四轮选3key4加入3更新4的keymin(6,7)6。第五轮选4key6。最终MST边为(0,1)权2、(1,2)权1、(1,3)权4、(2,4)权6总权值13。3.3 Python版本代码实现import sys def prim(n, graph): n: 顶点数 graph: 邻接矩阵graph[i][j]表示边权不连通用INF 返回: MST总权值, MST边列表 INF sys.maxsize key [INF] * n parent [-1] * n in_mst [False] * n key[0] 0 total_weight 0 mst_edges [] for _ in range(n): # 找key最小的未加入顶点 u -1 min_key INF for i in range(n): if not in_mst[i] and key[i] min_key: min_key key[i] u i if u -1: break # 图不连通 in_mst[u] True total_weight key[u] if parent[u] ! -1: mst_edges.append((parent[u], u, key[u])) # 更新邻居 for v in range(n): if not in_mst[v] and graph[u][v] key[v]: key[v] graph[u][v] parent[v] u return total_weight, mst_edges # 测试 INF sys.maxsize graph [ [0, 2, 3, INF, INF], [2, 0, 1, 4, INF], [3, 1, 0, 5, 6], [INF, 4, 5, 0, 7], [INF, INF, 6, 7, 0] ] weight, edges prim(5, graph) print(MST总权值:, weight) print(MST边:, edges)跑出来结果就是13边集和我手算的一致。3.4 C版本代码实现#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; pairint, vectortupleint,int,int prim(int n, vectorvectorint graph) { vectorint key(n, INF), parent(n, -1); vectorbool inMST(n, false); key[0] 0; int totalWeight 0; vectortupleint,int,int mstEdges; for (int iter 0; iter n; iter) { int u -1, minKey INF; for (int i 0; i n; i) { if (!inMST[i] key[i] minKey) { minKey key[i]; u i; } } if (u -1) break; inMST[u] true; totalWeight key[u]; if (parent[u] ! -1) mstEdges.emplace_back(parent[u], u, key[u]); for (int v 0; v n; v) { if (!inMST[v] graph[u][v] key[v]) { key[v] graph[u][v]; parent[v] u; } } } return {totalWeight, mstEdges}; } int main() { int n 5; vectorvectorint graph { {0, 2, 3, INF, INF}, {2, 0, 1, 4, INF}, {3, 1, 0, 5, 6}, {INF, 4, 5, 0, 7}, {INF, INF, 6, 7, 0} }; auto [weight, edges] prim(n, graph); cout MST总权值: weight endl; for (auto [u, v, w] : edges) cout u - v : w endl; return 0; }两版代码逻辑完全一致C版本用了tuple来存边Python版本用列表存元组。实际工程里如果顶点数上万朴素O(V²)可能就吃不消了这时候需要上堆优化。4. 堆优化Prim算法从O(V²)到O(E log V)4.1 为什么朴素版本慢瓶颈在哪朴素Prim每一轮都要花O(V)的时间去扫描key数组找最小值总共V轮所以是O(V²)。如果图很稀疏比如V100000E200000O(V²)就是10^10肯定超时。但其实我们并不需要每次都全量扫描只需要快速拿到当前最小的key。这就自然想到用**优先队列最小堆**来维护所有候选边的key值。每次从堆顶取最小如果该顶点已经加入MST就跳过惰性删除否则加入并更新邻居。4.2 优先队列优化的实现细节堆优化版本需要把邻接矩阵换成邻接表因为我们要遍历某个顶点的所有出边而不是扫描所有顶点。堆里存的是(key, vertex)二元组。每次弹出堆顶如果inMST[vertex]为真就continue否则加入MST然后遍历它的邻接边如果邻接点未加入且边权小于当前key就更新key并压入堆。这里有个细节同一个顶点可能被多次压入堆因为key被多次更新但只有第一次弹出时是有效的。这就是所谓的“惰性删除”堆里可能有冗余元素但总压入次数不超过E所以堆操作总数是O(E)总复杂度O(E log E)通常简写为O(E log V)。4.3 堆优化Python代码import heapq def prim_heap(n, adj): adj: 邻接表adj[u] [(v, w), ...] INF float(inf) key [INF] * n parent [-1] * n in_mst [False] * n key[0] 0 heap [(0, 0)] # (key, vertex) total_weight 0 mst_edges [] while heap: 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 key[v]: key[v] weight parent[v] u heapq.heappush(heap, (weight, v)) return total_weight, mst_edges # 测试 adj [ [(1,2),(2,3)], [(0,2),(2,1),(3,4)], [(0,3),(1,1),(3,5),(4,6)], [(1,4),(2,5),(4,7)], [(2,6),(3,7)] ] weight, edges prim_heap(5, adj) print(堆优化MST总权值:, weight) print(MST边:, edges)4.4 堆优化C代码#include bits/stdc.h using namespace std; int primHeap(int n, vectorvectorpairint,int adj) { const int INF 0x3f3f3f3f; vectorint key(n, INF); vectorbool inMST(n, false); priority_queuepairint,int, vectorpairint,int, greater pq; key[0] 0; pq.push({0, 0}); int totalWeight 0; while (!pq.empty()) { auto [w, u] pq.top(); pq.pop(); if (inMST[u]) continue; inMST[u] true; totalWeight w; for (auto [v, weight] : adj[u]) { if (!inMST[v] weight key[v]) { key[v] weight; pq.push({weight, v}); } } } return totalWeight; } int main() { int n 5; vectorvectorpairint,int adj(n); auto addEdge [](int u, int v, int w) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); }; addEdge(0,1,2); addEdge(0,2,3); addEdge(1,2,1); addEdge(1,3,4); addEdge(2,3,5); addEdge(2,4,6); addEdge(3,4,7); cout 堆优化MST总权值: primHeap(n, adj) endl; return 0; }两版堆优化代码跑出来都是13和朴素版本一致。实操心得堆优化版本在稀疏图上优势明显但如果图非常稠密E≈V²堆里元素会膨胀到V²级别内存和常数都可能不如朴素版本。我一般会先估算E和V的关系E V²/log V 时用堆优化否则用朴素。5. 常见问题与排查技巧实录5.1 图不连通怎么办Prim算法默认图是连通的。如果图不连通跑完一轮后会有顶点没被加入MST此时key仍为INF。我的处理方式是外层再套一个循环对每个未访问的顶点再跑一次Prim最终得到的是最小生成森林。代码里加一个for i in range(n): if not in_mst[i]: key[i]0; 继续跑即可。5.2 负权边能处理吗可以。Prim算法对负权边完全没问题因为切割性质不要求边权非负。这一点和Dijkstra不同Dijkstra不能有负权边但Prim可以。我实测过带负权的图结果依然正确。5.3 重边和自环怎么处理自环直接忽略因为加入自环只会形成环不会帮助连通。重边取权值最小的那条即可。邻接矩阵存图时如果有多条边直接存最小值邻接表存图时重边都存进去也没关系算法会自动选小的。5.4 常见错误速查表问题现象可能原因排查方法结果权值偏大初始化key没设INF检查key数组初始值结果权值偏小自环或重边未处理检查邻接矩阵对角线死循环堆优化未判inMST弹出时先检查是否已加入数组越界顶点编号从1开始但数组从0统一编号或开n1大小结果少边图不连通检查连通分量个数内存超限稠密图用了堆优化换朴素版本或邻接矩阵5.5 性能实测对比我在一台普通笔记本上跑了一个随机图测试V2000E10000朴素版本耗时约0.8秒堆优化版本约0.05秒。V500E100000稠密朴素版本约0.02秒堆优化约0.15秒。这验证了前面的选型建议稀疏图用堆稠密图用朴素。避坑技巧如果题目没有明确说明图是否连通最好在代码里加一个连通性检查否则可能返回错误结果而不自知。我一般会在跑完Prim后检查加入MST的顶点数是否等于n不等就说明图不连通。6. Prim算法的典型应用场景与扩展6.1 网络布线、道路规划与聚类前面提到的园区布线就是最直接的应用。类似地城市道路规划中如果要在若干小区之间修路让所有小区连通且总里程最短也是MST问题。再比如图像分割中的区域合并可以把像素看成顶点像素间相似度看成边权用MST做层次聚类。还有一类问题是“次小生成树”在MST基础上加一条边形成环去掉环上最大边可以得到次优方案常用于需要备份链路的场景。6.2 与Dijkstra的异同对比很多人会把Prim和Dijkstra搞混因为代码结构太像了。核心区别在于Dijkstra的key[v]存的是从起点到v的累计距离更新时是key[u] graph[u][v]Prim的key[v]存的是v到当前树的单条边权更新时直接是graph[u][v]。一个是路径最短一个是整体代价最小。我当年面试时就因为把两者写混被面试官追问过后来再也没错过。6.3 进一步扩展最小生成森林与瓶颈生成树如果图不连通对每个连通分量跑Prim就得到最小生成森林。另外还有一个概念叫“瓶颈生成树”即让最大边权最小的生成树。可以证明任何一棵最小生成树都是瓶颈生成树所以Prim的结果天然满足这个性质。这个性质在网络可靠性设计里很有用——你希望最差的那条链路尽量好。7. 我个人在实际操作中的几点体会第一不要一上来就写堆优化。先把朴素版本写对用一个小图手算验证再改成堆优化。我见过太多人直接写堆优化结果因为惰性删除没处理好debug半天。第二邻接矩阵和邻接表的切换要熟练。面试时如果没带模板邻接矩阵写起来更快但要注意空间。V10000时邻接矩阵就是10^8个int约400MB直接爆内存这时候必须用邻接表。第三Prim的起点不影响最终总权值但会影响中间过程。如果题目要求输出具体的边集不同起点可能得到不同的MST权值相同但边不同这是正常的因为MST可能不唯一。第四实际工程里如果边权是浮点数比较时要注意精度问题建议用而不是避免因为浮点误差导致重复更新。最后分享一个小技巧如果只需要总权值而不需要边集可以省掉parent数组代码更简洁。但如果需要输出方案parent数组必不可少。我一般都会保留方便调试和验证。
