今天训练营走到第六十二天图论这部分总算啃到了最硬的一块骨頭最小生成树。说实话prim算法和kruskal算法这两个名字光听就有点劝退但真学完之后你会发现它们背后就是最朴素的贪心思想套了一层图论的外衣并没有想象中那么玄乎。这篇内容适合三类人看一是跟着代码随想录训练营刷到图论章节、正准备做最小生成树题目的同学二是面试前想快速把图论高频考点补上的求职者三是工作中遇到网络布线、电路设计、任务分配这类需要“用最小代价连通所有节点”的场景想找个靠谱方案的开发者。我会把两个算法的原理、完整代码、复杂度分析、实战题目以及我踩过的坑一次性讲清楚保证你读完不光能AC题目还能在面试里把底层逻辑讲明白。1. 最小生成树到底在解决什么问题先不急着写代码咱们把概念捋顺。一个图里如果所有节点都能通过边连通而且边数恰好是节点数减一那这个子图就是一棵生成树。生成树不唯一因为你可以保留不同的边。而最小生成树就是所有生成树里边的权重总和最小的那一棵。这个问题的现实场景非常直观。你给一个园区规划网线有十几个办公楼需要互联楼与楼之间拉网线有不同的成本怎么布线才能让所有楼都通网、且总成本最低这就是一个标准的最小生成树问题。再比如城市里要修路连通所有乡镇每段路的造价不同怎么规划路线总造价最省还有电路板布线、水管网络设计本质上都是同一个模型。所以你在题目里看到“连接所有点的最小代价”“使所有点连通的最小花费”这类表述第一反应就应该是最小生成树。训练营把它安排在第六十二天是因为这属于图论里的进阶应用前边你肯定已经接触过深度优先遍历、广度优先遍历、拓扑排序、最短路径这些基础今天是在这些之上继续叠加贪心思想。从算法设计上来看最小生成树的解法明确分成两派一派是prim算法加点视角从图中某个点出发每次拉一个距离当前生成树最近的点进来另一派是kruskal算法加边视角把所有边按权重排序从小到大一条条往“森林”里加只要不成环就保留。两派各有各的优势也各有各的实现技巧。2. prim算法每次拉最近的点进圈prim算法的思路一句话就能概括从任意一个节点开始维护一个已加入生成树的节点集合每次从这个集合能直接到达的所有外部节点里挑一条权重最小的边把这个节点和边一起拉进生成树重复这个过程直到所有节点都被拉进来。别看这句话简单真正写代码的时候很多人会栽在“离生成树最近”这个表述上。注意它不是说离某个节点最近而是离整个已选集合最近这两个概念差别很大。2.1 prim的核心思想与三个关键数组实现prim算法你需要维护三个核心数据结构。第一个是图的存储通常用邻接矩阵grid因为prim算法更适合稠密图邻接矩阵写起来最直观grid[i][j]表示节点i到节点j的边权不连通就设一个很大的数。第二个是dist数组dist[j]表示节点j到当前生成树集合的最小距离这里特别容易和Dijkstra的dist搞混Dijkstra的dist是到源点的最短距离prim的dist是到生成树集合的距离含义不同更新逻辑也不同。第三个是visited数组标记哪些节点已经加入生成树。整个算法的执行过程可以拆成两层的循环。外层循环跑n次每次往里加一个节点。内层第一步先遍历所有未访问节点找出dist值最小的那个它就是本次要加入的点第二步更新该点所有邻接的未访问节点的dist值如果通过新加入的点能获得更小的距离就刷新dist。我当初学的时候有一个困惑为什么不直接从源点开始跑最短路径后来想明白了prim要的是“整个集合”的最小扩张而不是从单一点出发的最佳路径。你可以把生成树想象成一个雪球每次滚进一个新的节点然后这个节点又让雪球有了新的接触面下一轮就从这些接触面里选最近的。跟Dijkstra相比Dijkstra是每轮确定一个到源点最近的点prim是每轮确定一个到雪球最近的点。2.2 一步步手写prim代码代码实现我用的是训练营常用的C风格直接读入节点数v和边数e然后输出最小生成树的权值和。#include iostream #include vector #include climits using namespace std; int main() { int v, e; cin v e; // 邻接矩阵初始化为一个比较大的数 vectorvectorint grid(v 1, vectorint(v 1, 10001)); for (int i 0; i e; i) { int x, y, k; cin x y k; grid[x][y] k; grid[y][x] k; // 无向图 } vectorint dist(v 1, 10001); vectorbool visited(v 1, false); dist[1] 0; // 从节点1开始 int result 0; for (int i 0; i v; i) { int cur -1; int minDist 10001; // 第一步找未访问节点中dist最小的 for (int j 1; j v; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; cur j; } } if (cur -1) break; // 图不连通 visited[cur] true; result minDist; // 第二步用cur更新其他未访问节点的dist for (int j 1; j v; j) { if (!visited[j] grid[cur][j] dist[j]) { dist[j] grid[cur][j]; } } } cout result endl; return 0; }代码里有一个值得注意的细节dist[1]初始化为0其他都初始化成10001这样在第一个循环里找minDist时必然选中节点1。minDist初始值也要设成和grid一样的大数防止漏更新。if (cur -1) break是判断图不连通的情况如果某个节点根本没法到达生成树dist就会一直是无穷大cur不会被赋值。这种写法的时间复杂度是O(V^2)因为两层循环都是遍历所有节点。对于稠密图这个复杂度非常稳定不需要额外的堆结构代码最简单、最不容易出错。2.3 prim的复杂度与使用边界刚才说的O(V^2)是朴素prim的时间复杂度。如果面对的是节点非常多、但边还不算太离谱的图O(V^2)可能就扛不住了。这时可以用优先队列优化把“找dist最小节点”这个操作从O(V)降到O(log V)整体复杂度变成O(E log V)。但注意堆优化版写起来复杂不少而且要维护节点编号与dist的映射关系一不留神就写错所以训练营阶段以朴素版为主完全够用。从使用场景看prim更适合稠密图也就是边数接近V^2级别的图。因为在稠密图里邻接矩阵本身就非常紧凑而且每轮更新dist时总能覆盖到大量边整个算法几乎是线性地扫过整个矩阵。另外要说一个很多同学容易弄混的点prim算法能不能处理负权边这个其实天然支持。最小生成树不关心边的权重正负只关心连通所有节点后的总代价最小只要图是连通的哪怕出现负权边prim的贪心策略依然正确。我见过有人把负权边和Dijkstra的负权困境混淆那是两码事Dijkstra因为要维护“单源最短路径”负权会破坏它的贪心基础但prim要的是“总权值最小”负权不会造成问题。3. kruskal算法把边排好序再一条条选跟prim从点出发的思路完全相反kruskal算法是站在边的角度想问题的。它把图里所有边按权值从小到大排序然后从最小的边开始一条一条判断如果这条边的两个端点不在同一个集合里就把这条边加入生成树否则跳过。直到加入的边数达到v-1条为止。这个思路一开始听特别像“捡便宜”既然要总权值最小那肯定优先用最小边啊。但问题在于光选最小边不行你得保证不形成环。这里就衍生出一个关键问题怎么高效判断两个节点是否在同一个集合里3.1 kruskal为什么依赖并查集如果你把kruskal的选边过程在脑子里模拟一遍会发现它其实是在动态维护若干个连通分量。一开始每个节点自己是一个集合每次选中一条边就把两个集合合并成一个。这个过程天然就是并查集的主场。并查集有两个关键操作。第一个是find找到某个节点所在集合的根节点第二个是union代码里常写成join把两个集合合并。在kruskal里每次取出一条边先用find判断两个端点是否属于同一集合如果find(a) find(b)说明a和b已经连通了这条边再加进去就会形成环必须放弃如果不在同一集合就把它们join起来并把边的权值累加到结果里。判断两个端点是否已经连通这是并查集最经典的应用场景。如果你不用并查集每次选边都去遍历一遍已选边看看能不能从a走到b那复杂度就爆炸了。并查集通过路径压缩和按秩合并让所有操作近似O(1)这是kruskal能跑得飞快的基础。3.2 kruskal代码逐段拆解kruskal的C实现比prim多了几步但逻辑更线性反而更好记。#include iostream #include vector #include algorithm using namespace std; struct Edge { int from, to, val; bool operator(const Edge other) const { return val other.val; } }; vectorint father; void init(int n) { father.resize(n 1); for (int i 1; i n; i) father[i] i; } int find(int u) { return u father[u] ? u : father[u] find(father[u]); } bool isSame(int u, int v) { return find(u) find(v); } void join(int u, int v) { u find(u); v find(v); if (u ! v) father[v] u; } int main() { int v, e; cin v e; vectorEdge edges; for (int i 0; i e; i) { int x, y, k; cin x y k; edges.push_back({x, y, k}); } sort(edges.begin(), edges.end()); init(v); int result 0; int count 0; // 已选边数 for (Edge edge : edges) { if (!isSame(edge.from, edge.to)) { join(edge.from, edge.to); result edge.val; count; if (count v - 1) break; // 已构成生成树 } } cout result endl; return 0; }注意这里的find函数用了递归加路径压缩u father[u] ? u : father[u] find(father[u])。这行代码的意思是如果u不是根节点就递归找到根节点并且顺手把路径上的所有节点直接指向根节点。下次再find同样的节点时就是O(1)的时间。这个优化非常重要如果漏掉路径压缩数据量一大就会超时。join函数里先把u和v都find到根再把其中一个根挂在另一个根下面。这里我写的是father[v] u如果你想要更严谨一些可以按秩合并也就是把小树挂到大树下面避免树退化成链。不过在绝大多数题目里只做路径压缩就已经够快了。sorted边的操作是整个kruskal的核心。排序让整个算法有了贪心的基础排序之后从小到大扫描每次都选当前不成环的最小边。这个贪心策略的正确性可以用反证法证明但实操中你只要理解一个直觉每一步都选当前最小且不成环的边那么任何一步错误地选了大边都会导致最终总权值变大因为完全可以用一条更小的边替代它而不破坏连通性。3.3 kruskal的复杂度与场景kruskal的时间复杂度主要花在排序上是O(E log E)后面扫描边的过程几乎可以看作O(E)。这意味着kruskal的性能和节点数量关系不大只和边的数量相关所以它天然适合稀疏图也就是节点特别多、边相对少的场景。比如说一个图有10000个节点但只有12000条边用prim的O(V^2)就要跑1亿次操作kruskal只需要对12000条边排序加扫描速度完全不是一个量级。反过来一个图只有200个节点但边接近满的prim的O(V^2)只要4万次操作而kruskal要对近2万条边排序两者差距就不大了prim甚至更稳。kruskal还有一个隐藏优势它的实现思路非常“直球”不依赖图的具体存储方式。你只要能把边列表提取出来不管图是用邻接矩阵存的还是邻接表存的kruskal都不受影响。所以竞赛里我经常看到有人偏爱kruskal因为写起来不容易出错。4. prim与kruskal选哪个别靠感觉很多初学者学完这两个算法会陷入一个纠结到底什么时候用prim什么时候用kruskal这个问题如果在面试里被问到直接回答“稠密图用prim稀疏图用kruskal”只能算及格最好能把背后的复杂度推导说出来。4.1 从时间复杂度和实现成本对比咱们用一张表直接看对比对比维度prim算法kruskal算法核心思路加点法从点出发扩展生成树加边法按边权排序逐条选边依赖数据结构邻接矩阵/优先队列边列表 并查集时间复杂度O(V^2) 或 O(E log V)堆优化O(E log E)空间复杂度O(V^2)邻接矩阵O(E)适合场景稠密图V较小稀疏图E相对较小实现难度中等注意dist更新中等并查集写熟即可是否要排序不需要必须先对边排序从表里可以看出来prim的瓶颈是节点数kruskal的瓶颈是边数。所以在决定选哪个之前先数一下V和E的量级是E接近V^2的数量级还是E接近V的数量级这个判断只要十秒钟。再从实现成本看kruskal需要你熟练写对并查集尤其是路径压缩的递归写法prim需要你对dist数组的更新逻辑有清晰认识。如果你发现自己在写prim时总把dist含义搞混那不妨多练一练kruskal它的逻辑更线性排查bug更容易。4.2 典型题目里的选择逻辑在刷题场景里判断用哪个算法还有一条捷径看题目给的数据范围。如果V的范围很小比如100以内E再大也是白搭prim写起来最直观。如果E的范围很大几万甚至几十万V也很大那必须kruskal因为你连邻接矩阵都开不下。我遇到过一些训练营的同学一看到生成树就直接套prim模板结果在稀疏图的大数据范围下超时。不是prim写错了而是选错了算法。做题之前一定要先看数据范围养成这个习惯能省很多调试时间。面试中还有个隐藏考点让你求最小生成树的边的数量。这两算法都可以因为最小生成树一定有v-1条边。如果你发现最终选出的边数小于v-1那就说明图本身不连通这个判断在两种算法里都能自然体现出来prim里表现为cur -1kruskal里表现为边扫描完但count没到v-1。5. 训练营实战题目从0到1跑通最小生成树训练营第六十二天的配套题目通常就是一套完整的最小生成树模板题输入格式很统一先给节点数v和边数e接下来e行每行给三个数分别是边的两个端点编号和边的权值。要求输出最小生成树的边权总和。这种输入格式就是最经典的“裸题”它不绕弯子就是让你把prim或kruskal跑通。5.1 题目输入输出长什么样我随手构造一组数据模拟一下实战看到的样子4 5 1 2 1 1 3 3 2 3 1 2 4 5 3 4 24个节点5条边。你可以先在纸上画一画这个图理解一下拓扑结构。节点1连接节点2和3节点2连接节点1、3和4节点3连接节点1、2和4。边权比较分散有两条权值为1的边一条权值为2的剩下两条分别是3和5。显然最小生成树应该尽量选权值1和2的边而且不能成环。这种数据量非常适合手算。我经常建议初学者在写代码之前先手工推导一遍答案再去对代码输出这样能迅速发现自己对算法理解的偏差。5.2 手把手模拟一遍数据先用手推一下最小生成树。如果从节点1开始做prim第一步把节点1加入生成树dist[2]更新为1dist[3]更新为3dist[4]先不动保持无穷。第二步找dist最小节点2的1最小加入然后用节点2去更新dist[3]可以改成min(3, 1)1dist[4]可以改成5。第三步找dist最小节点3的1最小加入用节点3更新dist[4]变成min(5, 2)2。第四步加入节点4dist[4]为2。最终结果1124。如果写kruskal先把边按权重排序顺序是1-2(1)、2-3(1)、3-4(2)、1-3(3)、2-4(5)。然后一条条扫描1-2的两个端点不在同一集合合并2-3不在同一集合合并3-4不在同一集合合并。此时count已经等于3等于v-1直接退出循环结果同样是4。到这里两种算法殊途同归。这组数据虽然简单但它包含了一个重要细节权值为1的边有两条它们都是必须选的任何一条落选都会让总权值变大。而当权值为3的边扫到时节点1和3已经在同一个集合里了所以直接跳过这就避免了成环。5.3 两种写法都AC后的复盘做完题目之后我强烈建议你用同样的测试用例把两种算法都跑一遍然后重点观察它们的“中间状态”。prim可以看到每一轮dist数组的变化kruskal可以看到每一次合并集合前后的father数组变化。用调试器单步执行或者直接打印中间结果能让你把两个算法的本质看得透透的。我在训练营阶段做过一个很笨但很有效的练习把同一个图的边打乱顺序分别跑prim和kruskal确认输出一致再把图改成带重边的版本确认输出依然正确最后去掉一条关键边让图不连通确认代码能检测出来。这样练完一轮再遇到生成树变形题心里就有谱了。6. 最小生成树的常见坑我一个个踩给你看最后这部分是干货中的干货。代码随想录训练营里我见过太多人在最小生成树这个知识点上翻车很多坑不是算法思想的问题而是实现细节的问题。6.1 并查集路径压缩忘写kruskal算法里最常见的错误就是并查集的find函数没有写路径压缩。有些同学图省事直接写一个不带压缩的循环版本小数据跑得通数据量一上来就开始超时。为什么路径压缩这么重要因为不带压缩的并查集在极端情况下会退化成一个链表find一个节点可能要遍历很多层整体复杂度会退化到O(n)。而有了路径压缩find操作几乎是均摊O(1)的。我的建议是路径压缩这行代码背都要背下来它是并查集性能的灵魂。6.2 重边和自环的处理题目里经常出现两个节点之间有多条边的情况比如1到2有一条权值为3的边还有一条权值为7的边。如果你是做prim直接在邻接矩阵里取最小值就可以grid[1][2] min(grid[1][2], k)。如果你是做kruskal不需要特殊处理排序后小的那条会先被扫描到并生效大的那条后扫描到会发现两个端点已经连通自动跳过。自环就更简单了from等于to的边根本不会影响生成树在kruskal里它会因为isSame为true被跳过在prim里它更新dist[j]的条件是!visited[j] grid[cur][j] dist[j]自环的j就是cur本身已经visited了所以不会生效。6.3 图不连通时怎么判断题目通常会保证图是连通的但竞赛题偶尔不按套路出牌。如果图不连通最小生成树是不存在的你得在代码里优雅地处理。prim里通过cur -1来检测kruskal里通过对count v - 1的检测来发现。很多同学会忽略这个点直接输出一个错误的权值而这在测试用例里往往就是一个隐藏的扣分点。我的建议是不管题目有没有说图一定连通代码里都加上这个判断成本极低收益是避免稀里糊涂WA。6.4 关于负权边的迷思前边已经说过prim和kruskal都天然能处理负权边因为它们只关心总权值是否最小。但很多人在做练习题时看到负权边第一反应就是“这题不能用最小生成树解法”这是个很大的误解。我见过一个有意思的变形题给一组点点与点之间的“成本”是二维坐标下的曼哈顿距离求把这些点全部连通的最小总距离。这个问题的“边权”全是正数看起来不是典型最小生成树但实际上它就是一道裸的最小生成树你只需要先算出任意两点之间的距离再跑一遍prim或kruskal就行。这说明识别最小生成树问题的关键不是边权是否为正而是模型本身是不是“连通所有节点的最小代价”。还有一类常见题目是求“次小生成树”这类题目在prim基础上会额外引入路径上的最大值维护逻辑会复杂不少。训练营阶段先不管把基础的两个算法吃透后面自然能水到渠成。在最小生成树这个知识点上我的个人体会是prim和kruskal两个算法都要熟练掌握而不是只会一个。有些同学图省事只练kruskal结果遇到稠密图还硬用明明数据范围撑不住也要强上反过来有些同学执着于prim的模板面对稀疏图也傻乎乎开个大矩阵浪费空间还拖慢速度。真正的高手是能根据数据范围十秒钟定方案然后默写代码。你把这篇文章里的两个模板都背下来再自己去操作系统里跑几道题第六十二天的任务就算踏实完成了。