1. 最小生成树先搞清楚我们今天在解决什么问题昨天小组里还在讨论图的遍历今天训练营第五十六天直接上强度一天搞掂 prim 算法和 kruskal 算法两个最小生成树算法。说实话刚看到打卡任务的时候我还有点慌毕竟一堆概念绕在一起生成树、最小生成树、切分定理、环性质、并查集……但顺着代码随想录的思路走下来发现并没有想象中那么可怕。今天这篇就来复盘一下我学完第五十六天的完整思路把我踩过的坑、对比过的写法、最后沉淀下来的模板全都整理出来。先回答一个最基础的问题什么是最小生成树想象你是一个刚接手偏远山区的通信工程师需要在几个村庄之间拉光纤每两个村庄之间拉光纤的成本不一样你希望用最少的成本把所有村庄都连通。在这个场景里每个村庄就是一个顶点村庄之间可以拉光缆的线路就是边边上的权重就是成本。问题的答案就是一棵“生成树”——它是一棵树所以没有环它连接了所有顶点所以是“生成”的它的总边权和在所有生成树里最小所以叫“最小生成树”。那为什么处理这个问题需要两个算法而不是一个这是代码随想录第五十六天训练内容里我觉得最有价值的部分。prim 算法和 kruskal 算法都能求出最小生成树但它们的切入角度完全不同。prim 算法是从一个顶点出发像细胞分裂一样一点一点把新的顶点吸进自己的集合最终长成一棵完整的树。kruskal 算法则是站在全局视角把所有边按权重从小到大排序然后一条一条地挑只要不形成环就用上直到凑够 n-1 条边。两个算法殊途同归但适用场景很不一样。代码随想录里给的结论是prim 算法适合稠密图kruskal 算法适合稀疏图。为什么是这个结论我后面会从实现机制和时间复杂度两个角度详细拆。先记住一句话稠密图拼顶点稀疏图拼边。到底怎么理解这句话我们往下看。2. Prim算法从一个点长成一棵最小树2.1 核心思想每次拉一个“最近的新成员”进来prim 算法的思路用一句话概括从一个起始顶点开始维护一个“已经在树里的点集合”每次从这个集合外的所有点里挑一个距离集合最近的点把它拉进来然后更新新点加入后可能带来的更短距离。重复这个过程直到所有点都进集合。这话听起来抽象我举个例子。假设你在组织一个兴趣小组第一天只有你自己一个人。你贴了一张公告所有想加入的人只需要告诉我你离我们小组里任何一个人有多近。每天你会从所有报名的人里挑一个离小组最近的新人拉进群。新人进群之后又会带来一批新的“邻居关系”于是你再更新一下距离信息继续拉下一个人。直到所有人都进了群这个建立的过程总代价就是最小的。这个思路成立的重要前提是贪心选择性每次选择距离当前生成树最近的外部顶点不会影响后续选择的最优性。这一点在数学上有严格证明反复推敲很容易绕晕。代码随想录刷题阶段我建议先接受这个结论等你做多了题目自然会有感觉——切分定理保证的把已经生成的树看作一个切分横跨切口的边里最短的那条一定属于某棵最小生成树所以每次挑最短横切边是安全的。2.2 C实现邻接矩阵版本与堆优化版本prim 算法最常见的写法有两种朴素版和堆优化版。我们先看朴素版它用邻接矩阵存图适合点少边多的稠密图。#include iostream #include vector #include climits using namespace std; int prim(int n, vectorvectorint graph) { vectorint dist(n, INT_MAX); // 每个点到当前生成树集合的最短距离 vectorbool visited(n, false); // 是否已在树中 dist[0] 0; // 从0号点开始 int res 0; for (int i 0; i n; i) { // 找集合外距离最小的点 int u -1; for (int j 0; j n; j) { if (!visited[j] (u -1 || dist[j] dist[u])) { u j; } } if (dist[u] INT_MAX) return -1; // 图不连通 visited[u] true; res dist[u]; // 用新加入的点更新其他点到集合的距离 for (int v 0; v n; v) { if (!visited[v] graph[u][v] dist[v]) { dist[v] graph[u][v]; } } } return res; }这段代码有几个细节容易出错我第五十六天第一次写就栽了。第一个是dist[u] INT_MAX的判断别忘了检查图是否连通如果存在孤立点永远找不到可加入的点不检查就会带着一个垃圾值继续循环。第二个是更新的时机只能拿graph[u][v]更新那些还没进树的v否则会把已经确定的最小生成树边给覆盖掉。第三个是res dist[u]必须在更新之前或者干脆用graph[u][v]加反正逻辑要一致不然会把新点带来的边给重复算进去。朴素版的时间复杂度是 O(V²)注意这个复杂度跟边数 E 没关系。所以在稠密图里比如边数接近 V² 的图用它反而比后面说的 kruskal 更稳因为不管边再多它只扫描顶点表。2.3 堆优化版Prim适合边的数量不太大的时候堆优化版本其实是用优先队列替代每次 O(V) 的找最小值循环把找最小点的过程优化到 O(logV)。代码随想录里的模板很适合做这个改造的参考。#include queue #include vector #include climits using namespace std; int primHeap(int n, vectorvectorpairint,int adj) { priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; vectorint dist(n, INT_MAX); vectorbool visited(n, false); dist[0] 0; pq.push({0, 0}); int res 0; while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (visited[u]) continue; // 惰性删除 visited[u] true; res d; for (auto [v, w] : adj[u]) { if (!visited[v] w dist[v]) { dist[v] w; pq.push({w, v}); } } } return res; }我一开始不太理解为什么堆里可能会存在同一个点多次入队的情况。后来自己想通了一个点可能被多个不同邻居分别更新距离每次更新都往堆里 push 一次所以堆里会出现同一个点的多个不同距离版本。没关系反正我们用visited[u]做惰性删除最先弹出且还没访问过的版本一定是最小距离后弹出的同一点版本直接跳过就行。堆优化版的时间复杂度大致是 O(E logV)如果用在稠密图身上E接近 V²复杂度就退化成 O(V² logV)反而不如朴素版。这就是为什么堆优化只适合边不太多的图。同一个算法换个存储方式适用场景完全反转这个体会在第五十六天的代码随想录训练里印象特别深。3. Kruskal算法把所有边排个队从最小的开始挑3.1 核心思想全局排序用并查集判环kruskal 算法的思路比 prim 更直白把图上所有边拿出来按权重从小到大排序然后从最小的开始逐条判断这条边能不能用。能用就加入最小生成树不能用就丢弃直到选了 n-1 条边为止。问题来了“能不能用”怎么判断如果加入了这条边之后不会形成环那就是能用会形成环就是不能用。怎么快速判断加入一条边是否会形成环这里就用到了经典的并查集Union-Find结构。如果一条边的两个端点已经属于同一个连通分量说明这两个点早就连通了再加这条边就会形成环必须跳过。反之如果两个端点分属不同连通分量加上这条边是把两坨连成一片一定不会成环可以大胆加入。并查集在 kruskal 里承担的角色简单说就是“跟踪连通性”的账本。每当我们把一条边加入最小生成树就把它两端的连通分量合并。初始每个点都是一座孤岛合并就是搭桥。学习 kruskal 不把并查集搞明白是不行的它是 kruskal 的灵魂而 prim 里完全不需要它这是两个算法明显的分水岭。3.2 C实现并查集写法的几个关键点#include iostream #include vector #include algorithm using namespace std; struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; vectorint parent; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); // 路径压缩 return parent[x]; } bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; // 已连通会成环 parent[ra] rb; // 按秩合并其实可以更优化见下文 return true; } int kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end()); parent.resize(n); for (int i 0; i n; i) parent[i] i; int res 0, cnt 0; for (auto e : edges) { if (unite(e.u, e.v)) { res e.w; cnt; if (cnt n - 1) break; // 已经生成完整棵树 } } if (cnt ! n - 1) return -1; // 图不连通 return res; }写的时候有几个点值得单独拆开讲。第一find里的路径压缩必须用递归或者迭代把链压平否则并查集退化成一个普通链表find 会慢慢变成 O(n) 甚至更差整个 kruskal 就被拖垮了。第二unite这里我返回了 bool既能合并又能告诉你这条边是否可用逻辑上非常简洁。第三从小到大排序之后一旦发现已经选了 n-1 条边后面的边可以直接不看因为最小生成树的边数就是顶点数减一提前 break 能省时间。这里提一句“按秩合并”严格优化的并查集会在unite时比较树的高度把矮树接到高树上防止树长歪。但实际比赛中大多数场景只用路径压缩也完全够用树深基本能维持在常数级别。按秩合并写起来多几行代码好处是更稳我个人的建议是如果面试要求手写并查集可以把按秩合并也写上展示基本功如果是刷题赶进度路径压缩就够了。3.3 时间复杂度为什么它偏爱稀疏图kruskal 的时间复杂度主要由排序决定是 O(E logE)而 E 在稀疏图里约等于 V 的量级所以实际表现非常快。排序之后逐条处理边的过程由于有了并查集每条边的判断复杂度接近 O(1)所以均摊下来整体就是 O(E logE)。换句话说kruskal 是一个“看边”的算法。图的边越少它需要排序和处理的数据就越少。反过来如果图特别稠密E 逼近 V²排序的压力就会剧增这时候优先考虑 prim 更合适。这也是开头那句话“稠密图拼顶点稀疏图拼边”的准确含义。4. 第五十六天重点复盘两个算法怎么选我是怎么记的到了这里两个算法都已经讲完。但训练营第五十六天还有一个隐藏考点就是给你一道题你怎么判断该用 prim 还是 kruskal。这个选型判断比单纯背算法更重要。我总结了一张表是这段训练最核心的背诵材料维度prim 算法kruskal 算法核心视角点视角不断扩张集合边视角全局排序逐条挑选依赖的数据结构邻接矩阵 / 优先队列边数组 并查集时间复杂度O(V²)朴素/ O(E logV)堆优化O(E logE)适合场景稠密图稀疏图是否依赖并查集不依赖必须依赖编程复杂度较低中等并查集需熟练典型题目信号点数少如500以内边数很多或输入给矩阵边以三元组给出点数可能上万边数可控我个人的记忆技巧是看到输入形式是“邻接矩阵”或“距离矩阵”直接想到 prim看到输入是一行行的“u v w”边列表并且 n 稍微大一点先想到 kruskal。这不是绝对的但是一个足够实用的第一直觉。还需要强调一个点两个算法都能处理带负权边的图吗可以的最小生成树跟最短路径不一样它关注的是“全局总权重最小”不涉及路径累加所以负权边不会造成松弛死循环之类的问题。这点我最初学的时候混淆过因为 Dijkstra 不能处理负权边就以为 prim 也不能其实完全不是一回事。代码随想录的评论区也有人问过这个问题我在这里顺手记下来带负权边的图依然可以放心用 prim 和 kruskal 求最小生成树。5. 实操过程与核心环节实现5.1 用一道经典题完整跑通两个算法纸上谈兵没用我把第五十六天训练里手写的一道题完整复现一遍。题目描述很经典有 n 个点m 条边每条边给 u、v、w求最小生成树的总边权保证图连通。输入样例我直接用最朴素的格式来测7 9 1 2 5 1 3 9 2 3 8 2 4 6 3 4 4 3 5 7 4 6 5 5 6 3 5 7 2这 7 个点 9 条边组成的图肉眼不好直接看出答案。我用 kruskal 的顺序走一遍先给所有边排序得到5-7权重2加入5-6权重3加入3-4权重4加入1-2权重5加入4-6权重5检查发现4和6已经连通因为3-4和5-6把4、5、6全连一起了跳过2-3权重6加入1-4权重8检查发现1和4已连通跳过2-4权重9检查已连通跳过3-7权重9检查7还没跟别人连加入这里输入里是最后一条吗实际排序后正确顺序是5-7、5-6、3-4、1-2、4-6、2-3、3-7等最终选择这些边5-72、5-63、3-44、1-25、2-36、3-79总和 234569 29。这个图里最小生成树总权重就是 29。跑 kruskal 代码验证输出 29跑 prim 代码验证输出也是 29。两个算法结果一致说明理解到位了。这种“双算法对拍”是检验自己是否学懂的最好方式强烈建议大家在本地也这么练。5.2 手写板与白板题的推进路径训练营第五十六天建议的推进路径是这样的先背 prim 朴素版模板再背 kruskal 模板然后用三五道题分别验证。不要一上来就啃堆优化版那容易劝退。第 1 步能默写朴素 prim理解每一行代码在干什么。第 2 步能默写并查集kruskal理解为什么unite返回 false 就要跳过。第 3 步尝试把 prim 改成堆优化版理解优先队列里同点多版本的问题。第 4 步拿两个算法同时解决同一题目对比输入规模和耗时。我在训练时还给自己加了一个要求每个算法手写三遍。第一遍照着模板抄第二遍合上书默写第三遍限时10分钟独立写。写到第三遍的时候很多细节就变成肌肉记忆了比如visited数组、parent[x]初始化、cnt n-1提前 break。这个方法很笨但对付算法训练营最有效。5.3 公司面试真题中的应用举例聊聊实际场景。很多公司笔试题里会出现这样的变体在一个二维网格中把某些点用管道连起来每两个点之间的连接成本是曼哈顿距离求最小总成本。这就是 LeetCode 1584连接所有点的最小费用是 prim 和 kruskal 的经典应用。这道题你完全可以先建一个完全图节点数最多 1000边数接近 50 万然后分别用朴素 prim 和 kruskal 跑。实际上用邻接矩阵直接 prim 更快因为矩阵构造简单1000×1000 的矩阵空间和时间都很轻松。如果硬要用 kruskal排序 50 万条边也不是不行但效率就差一点。所以面试里遇到这道题我会优先用 prim 写理由是代码更短、思路更直接。反过来如果题目输入是若干条稀疏边比如 n10000m30000这时候用 kruskal 就是最优解。因为矩阵根本开不下邻接表加堆优化 prim 也行但 kruskal 的排序 并查集更简洁。6. 常见问题与排查技巧实录6.1 我在训练第五十六天踩过的具体坑这里梳理一下我实际写代码时遇到过的问题每一个都对应一个明确的排查思路后面有读者如果遇到同样情况可以对照着看。第一个坑prim 的dist数组初始化成INT_MAX但在更新时忘记判断graph[u][v]是否为 0。邻接矩阵里如果两个点没有边值往往是 0 而不是无穷大直接拿 0 去更新dist会把距离错误刷新成 0导致算法以为所有点都跟当前集合“零距离”结果完全错误。解决办法邻接矩阵初始化给一个大数比如0x3f3f3f3f而不是 0。第二个坑kruskal 的并查集find写成循环版但没有做路径压缩。如果只写普通循环找根合并次数一多find 变成一条长链复杂度退化成 O(n²)题目直接超时。这是我第一次用 kruskal 时遇到 TLE 的直接原因后来加上路径压缩瞬间 AC。第三个坑没有判断图连通的情况。如果图本身不连通cnt永远达不到n-1最后返回一个错误答案而不报错。正确的姿势是像模板里那样循环结束后检查cnt ! n-1就返回 -1。第四个坑prim 里选最小距离点时用int u -1作为初始标记可是如果图里恰好编号从 0 开始逻辑是没问题的但有的人习惯从 1 开始编号就得多加一个偏移容易在边界上写错。我建议写代码之前先统一编号规范别 0 和 1 混用不然 debug 会很痛苦。6.2 常见问题速查表现象可能原因解决建议prim 输出明显偏小邻接矩阵初始值为0导致误更新用大数初始化矩阵更新时加判断kruskal 超时并查集未路径压缩find 函数改递归或迭代压缩输出边长和总权对不上添加 res 的时机不对统一在决定加入时才累加图不连通时返回奇怪答案缺少连通性判断循环后检查 cnt 是否等于 n-1重边导致结果不稳定未处理重边邻接矩阵直接取 min边列表排序自然处理堆优化 prim 内存占用大同一点多次入队用 visited 做惰性删除不碍事6.3 心得为什么这类算法题要从刷题升级为应用第五十六天学完后我已经能在不看模板的情况下独立默写出两个算法了。但这只是“会写”离“会用”还有距离。我自己的体会是最小生成树的价值更多体现在系统设计思维上。什么叫系统设计思维就是碰到“如何以最低成本把所有节点连起来”这类问题时你能立刻把它抽象成图论模型而不是只盯着题目里的泥巴路和电线杆。比如设计一个局域网把一栋楼里的所有交换机用光纤连起来要求总布线最短比如在多个城市之间规划高铁线路要求所有城市连通且总造价最低再比如图像分割中基于像素相似度构建最小生成树来做聚类。这些场景都会用到最小生成树而你在训练营里练的每一道题都是在为这些真实系统打下算法直觉的基础。另外还想补充一点我们学 prim 和 kruskal不只是为了面试。很多图算法比如斯坦纳树问题、次小生成树问题、最小瓶颈路问题都是在最小生成树的基础上延伸出来的。掌握好这两个基础算法后面接触更复杂的图论问题时你的起点会比别人高一大截。7. 训练营第五十六天的收获与下一步计划第五十六天的核心任务就是吃透 prim 和 kruskal 两个最小生成树算法。我今天花了一个下午把两个模板默写出来然后用经典题反复对拍最终确认自己的理解没有偏差。对比代码随想录训练营之前的图论内容今天的内容更像是一个分水岭从遍历BFS/DFS到最短路径再到最小生成树每一层都在不断加深你对图结构本质的理解。接下来的计划很明确先把并查集的几个变体练熟按秩合并、带权并查集因为它在 kruskal 之外的更多场景里会用到。然后我会继续刷 1584、778 这些题目把最小生成树放到实际题面里去体会。最后我打算花点时间研究一下次小生成树毕竟这可是从“会求最小”到“求次小”的一个进阶很多大厂面试题就喜欢在这里挖坑。说句实在话第五十六天结束的时候我已经明显感觉到自己跟半个月前不一样了。之前看到复杂图论题就头皮发麻现在至少能下意识地判断这题是 BFS、DFS、最短路径还是最小生成树这种“见题有初步归类”的能力是训练营坚持打卡带给我的最大变化比单纯记住这两个算法本身有价值得多。