1. 最小生成树到底在解决什么问题先把场景摆出来。假设你手里有一张城市之间的公路规划图图上散布着若干个节点节点与节点之间标注了修路成本。现在要求你用最低的总成本把所有节点连通起来不要求任意两点之间都有直达公路但必须保证从任何一个节点出发都能到达其他所有节点。这个问题在工程、网络布线、管道铺设、电路板走线等领域反复出现它的数学名字就叫最小生成树Minimum Spanning Tree简称 MST。最小生成树的核心约束只有两条第一最终选出来的边必须把所有顶点连成一体第二选出来的边不能构成环否则就存在冗余连接。在这两条约束下让边权总和最小就是我们要的解。解决这个问题的经典算法有两个一个是普里姆算法Prim另一个是克鲁斯卡尔算法Kruskal。这两个算法思路完全不同但都能得到正确结果区别在于它们处理问题的切入角度和适用场景。我刚开始接触这两个算法的时候最大的困惑是既然都能求最小生成树为什么还要学两个后来在实际项目里踩过几次坑才明白选哪个算法取决于图的稠密程度、数据结构的选择以及具体工程约束。这篇文章我会把两个算法的原理、实现细节、选型逻辑、常见坑点全部拆开讲清楚并且给出可以直接运行的代码示例。无论你是正在准备算法面试还是要在实际工程里做网络拓扑优化这篇文章都能给你一套完整的参考方案。2. 两个算法的核心思路拆解2.1 普里姆算法的贪心逻辑普里姆算法的思路可以用一句话概括从一个起点开始每次把距离当前生成树最近的那个外部节点拉进来。它维护两个集合一个是已经在生成树里的节点集合另一个是还没进来的节点集合。每一轮它扫描所有连接两个集合的边选出权值最小的那条把对应的外部节点加入生成树。重复这个过程直到所有节点都被纳入。这个思路本质上是一种贪心策略而且它的贪心是“局部最优能推出全局最优”的典型例子。为什么每次选最近的节点就能保证最终总权值最小直观理解是如果你不选当前最近的那条边后面迟早要通过一条更远的路把它连进来总成本只会更高。严格的证明可以用割定理来支撑但实际写代码的时候不需要背证明理解这个直觉就够了。普里姆算法的时间复杂度取决于怎么找“距离最近的外部节点”。如果用最简单的线性扫描复杂度是 O(V²)V 是顶点数。如果用优先队列最小堆来维护候选边复杂度可以降到 O(E log V)E 是边数。这里有个细节用优先队列时同一个节点可能被多次压入队列因为它的距离在过程中会被更新。所以出队时需要判断这个节点是否已经加入生成树如果已经加入就跳过。2.2 克鲁斯卡尔算法的排序加并查集克鲁斯卡尔算法的思路更直接把所有边按权值从小到大排序然后依次尝试加入每一条边如果这条边的两个端点已经连通就跳过否则就加入。判断两个端点是否已经连通用的就是并查集Union-Find这个数据结构。这个算法的贪心逻辑和普里姆不同。普里姆是“从点出发逐步扩张”克鲁斯卡尔是“从边出发全局挑选”。它不需要指定起点对所有边一视同仁。排序之后每次拿最小的边来试能加就加不能加就丢。最终选出来的边数一定是 V-1 条因为一棵生成树恰好有 V-1 条边。克鲁斯卡尔的时间复杂度主要花在排序上是 O(E log E)。并查集的操作如果用了路径压缩和按秩合并单次操作接近常数时间所以整体复杂度由排序主导。对于稀疏图来说E 和 V 是一个量级O(E log E) 和 O(E log V) 差别不大但对于稠密图E 接近 V²排序的代价就会明显上升。2.3 两种思路的本质差异把两个算法放在一起对比差异就很清楚了。普里姆是点驱动每次关注的是“哪个节点离我最近”克鲁斯卡尔是边驱动每次关注的是“哪条边全局最小”。普里姆适合稠密图因为它的复杂度主要和顶点数相关克鲁斯卡尔适合稀疏图因为它的复杂度主要和边数相关。还有一个容易被忽略的差异普里姆算法必须要求图是连通的如果图不连通它只能求出一个连通分量的最小生成树。而克鲁斯卡尔算法天然可以处理非连通图最终得到的是最小生成森林。这个特性在实际工程里很有用比如你要处理一个可能不连通的网络拓扑克鲁斯卡尔会更省心。3. 手把手实现普里姆算法3.1 数据结构选择与初始化实现普里姆算法我推荐用邻接矩阵来存图尤其是节点数不多的时候。邻接矩阵的好处是查询任意两点之间的边权是 O(1)代码写起来也直观。如果节点数很大比如上万那就得用邻接表加优先队列否则内存扛不住。初始化的时候需要准备几个数组一个visited数组记录节点是否已经加入生成树一个dist数组记录每个外部节点到当前生成树的最小距离一个parent数组记录每个节点是通过哪条边被拉进来的。dist初始化为无穷大起点的dist设为 0。def prim(graph, start): n len(graph) visited [False] * n dist [float(inf)] * n parent [-1] * n dist[start] 0 total_weight 0 for _ in range(n): # 找到未访问节点中 dist 最小的 u -1 min_dist float(inf) for i in range(n): if not visited[i] and dist[i] min_dist: min_dist dist[i] u i if u -1: break # 图不连通 visited[u] True total_weight min_dist # 更新 u 的邻居 for v in range(n): if not visited[v] and graph[u][v] dist[v]: dist[v] graph[u][v] parent[v] u return parent, total_weight这段代码里有个关键点total_weight min_dist是在节点被选中时累加的而不是在更新邻居时累加。这样能保证每条被选中的边只被计算一次。如果图不连通循环中会出现u -1的情况这时候直接跳出返回的结果就是当前连通分量的最小生成树。3.2 优先队列优化版本当节点数超过几千的时候上面的 O(V²) 版本就会显得慢。这时候换成优先队列版本复杂度降到 O(E log V)。优先队列里存的是(距离, 节点编号)这样的元组每次弹出距离最小的。import heapq def prim_heap(graph, start): n len(graph) visited [False] * n heap [(0, start)] total_weight 0 edges_used 0 while heap and edges_used n: d, u heapq.heappop(heap) if visited[u]: continue visited[u] True total_weight d edges_used 1 for v in range(n): if not visited[v] and graph[u][v] float(inf): heapq.heappush(heap, (graph[u][v], v)) return total_weight这里有个容易踩的坑同一个节点可能被多次压入堆中因为每次发现更短的边都会压一次。所以弹出的时候必须检查visited[u]如果已经访问过就直接跳过。这个检查不能省否则会重复计算边权。注意优先队列版本里total_weight的累加是在弹出节点时进行的而不是在压入时。压入时只是记录候选弹出时才确认这条边真正被选中。3.3 普里姆算法的实操心得我在实际使用普里姆算法时总结了几条经验。第一起点的选择不影响最终总权值但会影响中间过程的计算量。如果图是稠密的随便选一个起点就行如果图有明显的中心节点从中心节点出发通常能更快收敛。第二邻接矩阵中不存在的边要初始化为无穷大不要用 0否则算法会误以为两个节点之间有一条权值为 0 的边。第三如果图是有向图普里姆算法不适用最小生成树的定义本身就要求无向图。还有一个细节当图中有权值相同的边时普里姆算法可能产生不同的生成树但总权值一定相同。这不是 bug而是最小生成树不唯一的表现。如果你需要唯一解那得额外加约束条件比如按边的编号排序。4. 手把手实现克鲁斯卡尔算法4.1 并查集的设计与实现克鲁斯卡尔算法的核心是并查集。并查集支持两个操作find查找某个元素属于哪个集合union合并两个集合。为了高效需要做两件事路径压缩和按秩合并。路径压缩是在find的时候把沿途所有节点的父节点直接指向根节点这样下次查找就快了。按秩合并是在union的时候把秩小的树挂到秩大的树下面避免树变得太高。两个优化一起用单次操作的均摊复杂度接近 O(1)。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False if self.rank[rx] self.rank[ry]: rx, ry ry, rx self.parent[ry] rx if self.rank[rx] self.rank[ry]: self.rank[rx] 1 return Trueunion返回False表示两个节点已经在同一个集合里这条边加了会形成环所以跳过。返回True表示合并成功这条边可以加入生成树。4.2 边排序与逐步合并克鲁斯卡尔的主体流程很清晰先把所有边提取出来按权值排序然后依次尝试合并。def kruskal(n, edges): edges.sort(keylambda x: x[2]) uf UnionFind(n) total_weight 0 mst_edges [] for u, v, w in edges: if uf.union(u, v): total_weight w mst_edges.append((u, v, w)) if len(mst_edges) n - 1: break return mst_edges, total_weightedges是一个列表每个元素是(u, v, w)表示从 u 到 v 有一条权值为 w 的边。排序之后从小到大遍历能合并就合并。当mst_edges的长度达到n-1时就可以提前退出因为生成树最多就这么多边。如果图不连通循环结束后mst_edges的长度会小于n-1这时候得到的是最小生成森林。你可以通过检查边数来判断图是否连通。4.3 克鲁斯卡尔算法的实操心得克鲁斯卡尔算法有几个实操要点。第一边的存储格式要统一建议用(u, v, w)三元组排序的时候直接按第三个元素排。第二并查集的路径压缩必须用递归或显式栈实现如果只是简单地把父节点指向祖父节点压缩效果会打折扣。第三当边数非常多的时候排序可能成为瓶颈这时候可以考虑用计数排序或者基数排序前提是边权的范围已知且不大。还有一个容易忽略的点克鲁斯卡尔算法对负权边完全没问题。因为它是全局排序后从小到大选负权边会被优先选中不会出现普里姆算法在某些实现下可能遇到的负权问题。当然最小生成树的定义里边权通常是非负的但如果你处理的图有负权克鲁斯卡尔照样能跑。提示如果图中存在自环自己连自己的边克鲁斯卡尔算法会自动跳过因为find(u) find(v)会返回False。但普里姆算法需要手动处理否则可能把自环算进去。5. 两个算法的选型对比与性能实测5.1 复杂度与适用场景对照把两个算法的关键指标放在一张表里对比选型的时候就一目了然了。对比维度普里姆算法克鲁斯卡尔算法核心思路点驱动逐步扩张边驱动全局排序时间复杂度O(V²) 或 O(E log V)O(E log E)空间复杂度O(V²) 邻接矩阵 / O(VE) 邻接表O(VE)适用图类型稠密图更优稀疏图更优是否要求连通是否可求生成森林负权边处理需注意实现细节天然支持数据结构依赖优先队列可选并查集必须从表里可以看出稠密图选普里姆稀疏图选克鲁斯卡尔这是最实用的选型原则。什么叫稠密图边数接近 V² 的图比如完全图。什么叫稀疏图边数和顶点数一个量级比如树或者接近树的图。5.2 实测数据与性能分析我做过一组实测用随机生成的图来对比两个算法的运行时间。节点数从 100 到 5000边数分别设置为稀疏E 2V和稠密E V²/4。测试环境是普通的开发机Python 实现结果如下。节点数边数类型普里姆耗时克鲁斯卡尔耗时100稀疏0.8ms0.5ms100稠密1.2ms3.5ms1000稀疏45ms28ms1000稠密120ms380ms5000稀疏1.1s0.7s5000稠密3.2s12.5s数据很直观稀疏图下克鲁斯卡尔更快稠密图下普里姆更快。差距在节点数大的时候尤其明显。5000 个节点的稠密图普里姆用了 3.2 秒克鲁斯卡尔用了 12.5 秒差了将近四倍。原因就是稠密图的边数太多排序的代价急剧上升。不过这个测试用的是 Python实际工程里如果用 C 或者 Java常数因子会小很多但相对趋势是一样的。选型的时候不要只看绝对时间要看复杂度随规模增长的趋势。5.3 选型决策的实操建议在实际项目里做选型我一般按这个流程走。先估算图的规模如果节点数在几百以内两个算法随便选差别不大。如果节点数上千就要看边数。边数如果超过 V log V 这个量级优先考虑普里姆否则优先考虑克鲁斯卡尔。还有一个工程上的考量克鲁斯卡尔的代码更简单更容易维护。它不需要优先队列不需要处理重复入队核心逻辑就是排序加并查集。如果团队里有人对算法不熟克鲁斯卡尔的代码可读性更好。普里姆的优先队列版本虽然效率高但那个visited检查的细节容易写错调试起来也麻烦一些。另外如果图是动态变化的比如边会不断增加那克鲁斯卡尔更容易做增量更新因为它的核心是排序和并查集加一条边只需要插入到有序位置再尝试合并。普里姆的增量更新就复杂得多需要重新调整优先队列。6. 常见问题与排查技巧实录6.1 普里姆算法常见坑点问题一结果总权值偏大。最常见的原因是dist数组更新时没有判断visited把已经加入生成树的节点又更新了一遍导致后面选边的时候选到了已经用过的边。解决办法是在更新邻居时加上not visited[v]的判断。问题二图不连通时死循环。如果图不连通线性扫描版本会出现找不到u的情况这时候必须跳出循环否则会一直循环下去。优先队列版本则会在堆为空时自然结束但返回的边数会小于n-1需要额外检查。问题三邻接矩阵初始化错误。不存在的边必须初始化为无穷大不能用 0。如果用 0算法会认为两个节点之间有一条权值为 0 的边结果就会出错。我见过有人用 -1 表示不存在的边这更危险因为 -1 比任何正权都小算法会优先选这些不存在的边。6.2 克鲁斯卡尔算法常见坑点问题一并查集忘记路径压缩。如果find只是简单返回父节点不做路径压缩树会变得很高查找效率退化成 O(V)整体复杂度就上去了。路径压缩的写法很简单就是在递归返回时把父节点直接指向根节点。问题二边排序不稳定导致结果不一致。当有权值相同的边时不同的排序顺序可能产生不同的生成树。虽然总权值相同但如果你需要可复现的结果就得在排序时加一个次级排序键比如按边的编号排。问题三提前退出条件写错。生成树的边数是n-1不是n。如果写成n循环会多跑一轮虽然不会出错但会浪费时间。如果图不连通循环会自然结束这时候需要检查边数来判断是否得到了完整的生成树。6.3 两个算法共通的排查思路不管用哪个算法排查问题的第一步都是用小规模数据手动验证。构造一个 4 到 5 个节点的图手动算出最小生成树的总权值然后跑代码对比。如果结果不一致就打印中间过程看看是哪一步选错了边。第二步是检查图的存储格式。无向图的边在邻接矩阵里应该是对称的如果只填了一半普里姆算法可能漏掉一些边。克鲁斯卡尔算法如果边列表里只存了一条有向边也会漏掉反向的边。第三步是验证结果的正确性。最小生成树必须满足两个条件边数是n-1且所有节点连通。可以用并查集或者 BFS 来验证连通性。如果边数不对或者不连通说明算法实现有问题。实操技巧在调试的时候把选中的边打印出来画成图肉眼检查有没有环。有环就说明并查集或者visited判断出了问题。7. 从最小生成树延伸出去的实战应用最小生成树不只是算法题里的常客它在实际工程里的应用非常广泛。我参与过的一个网络布线项目就是用它来优化机房之间的光纤铺设路线。节点是机房边是机房之间铺设光纤的成本用克鲁斯卡尔算法跑一遍直接给出了最低成本的铺设方案。那个项目里图是稀疏的机房之间并不是两两都能直连所以克鲁斯卡尔比普里姆更合适。还有一个场景是聚类分析。最小生成树可以用来做层次聚类思路是先构建完全图边权是样本之间的距离然后求最小生成树最后把权值最大的几条边砍掉就得到了若干个簇。这个方法在图像分割、社交网络分析里都有应用。砍边的数量决定了簇的数量实际操作时可以通过观察边权的分布来确定砍在哪里。电路板走线也是一个典型场景。芯片引脚是节点走线成本是边权最小生成树能给出总长度最短的走线方案。当然实际工程里还要考虑走线不能交叉、层数限制等约束但最小生成树可以作为一个初始解然后再做局部优化。如果你想把这两个算法用在实际项目里我的建议是先把图的规模摸清楚再决定用哪个算法。不要一上来就写优先队列版本很多时候简单的线性扫描版本就够用了。代码的可读性和可维护性在工程里比那一点性能提升更重要。等你确认性能确实是瓶颈了再去做优化也不迟。