图解最小生成树从Prim到Kruskal5分钟搞懂两种经典算法最近在辅导几个刚接触数据结构的学生发现他们一遇到“最小生成树”这个概念就头疼。不是不理解算法步骤而是面对Prim和Kruskal这两种看似相似实则内核迥异的算法时总容易混淆。这让我想起自己当年备考时也是对着教材上的伪代码反复琢磨直到用几个生活化的比喻才真正开窍。今天我就想用最直观的图解方式结合大家熟悉的场景把这两个算法的本质差异讲透让你下次再遇到PTA上的相关题目时能一眼看穿题目在考什么该用哪种思路去解。最小生成树Minimum Spanning Tree, MST听起来高大上其实它的应用场景就在我们身边。想象一下你要为一个新开发区的几个小区铺设宽带网络每个小区都是一个节点铺设光缆的成本就是边的权重。你的目标是让所有小区都能上网即连通同时总铺设成本最低。这就是最小生成树要解决的经典问题——在保证连通的前提下找出总权重最小的那组连接。无论是通信网络规划、交通线路设计还是电路板布线背后都有它的身影。对初学者而言掌握Prim和Kruskal不仅是应付考试更是理解“优化”和“贪心”思想的绝佳入口。1. 核心概念什么是最小生成树在深入算法之前我们必须先统一几个基本认知。一个连通无向图如果它有n个顶点那么它的生成树一定包含n个顶点和恰好n-1条边并且这n-1条边足以让所有顶点相互连通且不形成任何环。最小生成树就是所有可能的生成树中边上权重总和最小的那一个或那几个。这里有个关键点常被忽略最小生成树关注的是全局总权重最小而不是任意两点间的最短路径。举个例子假设A、B、C三个城市构成一个三角形AB距离10BC距离8AC距离15。最小生成树会选择AB和BC总成本18而不是AC和AB总成本25。虽然A到C的直接距离是15但在生成树中A到C的路径是A-B-C距离是18这比15长但为了全局总成本最低这是必须接受的“妥协”。很多判断题会在这里设陷阱比如“最小生成树中任意两点的路径一定是原图中的最短路径”这显然是错误的。注意一个图的最小生成树可能不唯一。当图中存在多条权值相同的边并且这些边的不同选择都能构成总权重相同的生成树时就会出现多个合法的最小生成树。判断唯一性的一个常用条件是如果图中所有边的权值都互不相同那么其最小生成树一定是唯一的。为了更直观地理解生成树的构成我们可以看下面这个简单的对比属性原图 (连通无向加权图)其生成树顶点数nn (必须包含所有顶点)边数m (通常 m ≥ n-1)严格等于 n-1连通性连通连通 (这是“生成树”的定义)环的存在可能有环绝对无环权重总和所有边权重之和所有生成树中权重和最小的(即MST)理解了这个表格你就掌握了最小生成树的所有静态特征。接下来我们要解决动态问题如何从原图中“生长”出这棵最优的树这就引出了我们今天的主角Prim算法和Kruskal算法。2. Prim算法从一个种子开始的“扩张”Prim算法我更喜欢叫它“点贪心”或“扩张法”。它的策略非常直观从图中任意选择一个顶点作为“种子”然后像滚雪球一样每次把离当前这片“雪球”已选顶点集合最近的一个新顶点及其连接的边吸纳进来直到覆盖所有顶点。你可以把它想象成建设一个全国性的物流中心网络。我们先在北京建第一个中心种子。接下来要选择下一个城市建设中心标准是哪个城市离现有的中心网络最近即运输成本最低。可能是天津。现在我们的网络有了北京和天津。第三个中心的选择是看哪个城市离北京或天津这个整体网络最近可能是石家庄……如此反复直到覆盖所有目标城市。每次决策都只关心“当前已建网络”到“外部世界”的最短连接这就是Prim的贪心所在。2.1 算法步骤与图解推演让我们用一个包含6个顶点A到F的图来一步步推演。各边权重已标出。初始图邻接矩阵或邻接表表示 顶点A, B, C, D, E, F 边与权重 A-B: 4, A-C: 2 B-C: 1, B-D: 5 C-D: 8, C-E: 10 D-E: 2, D-F: 6 E-F: 3假设我们从顶点A开始。初始化已选集合 U {A}。未选集合 V-U {B, C, D, E, F}。记录每个未选顶点到集合U的最短距离通过U中的哪个顶点连接。lowcost[B] 4 (via A)lowcost[C] 2 (via A)其他顶点D, E, F暂时为无穷大因为从A没有直接边。第一轮扩张从lowcost数组中找到最小值是C:2。将C加入U。此时U{A, C}。选择的边是A-C权重2。这是生成树的第一条边。更新距离因为C加入了现在所有未选顶点到U的距离可能需要更新。检查C的邻居B: 原来通过A到U是4现在通过C到U是1B-C边。14所以更新lowcost[B] 1 (via C)。D: 原来无穷大现在通过C是8所以lowcost[D] 8 (via C)。E: 原来无穷大现在通过C是10所以lowcost[E] 10 (via C)。F: 仍无连接保持无穷大。第二轮扩张当前lowcost为{B:1, D:8, E:10, F:∞}。最小值是B:1。将B加入UU{A, C, B}。选择的边是C-B权重1。生成树的第二条边。继续更新与扩张重复此过程。B加入后更新其邻居D原来通过C是8现在通过B是5B-D边58更新lowcost[D]5 (via B)。第三轮lowcost最小值是D:5。加入D边B-D权重5。第四轮D加入后更新其邻居E和F。lowcost[E]从10更新为2D-E边lowcost[F]从∞更新为6D-F边。本轮lowcost最小是E:2。加入E边D-E权重2。第五轮lowcost只剩F:6。加入F边D-F权重6。至此所有顶点加入U算法结束。我们得到的最小生成树包含边A-C(2), C-B(1), B-D(5), D-E(2), D-F(6)总权重为16。整个过程我们维护了两个核心数组这也是Prim算法实现的关键// 假设图用邻接矩阵G[][]表示INF表示无边 int lowcost[MAXV]; // 存储V-U中顶点到U的最小权值 int closest[MAXV]; // 存储对应lowcost权值的边在U中的那个端点 // 初始化从顶点u开始 for (i0; in; i) { lowcost[i] G[u][i]; // 初始化为u到各点的直接距离 closest[i] u; } lowcost[u] 0; // 表示u已加入U for (i1; in; i) { // 循环n-1次找剩下的n-1条边 // 1. 在lowcost中找最小值min及其对应顶点k min INF; for (j0; jn; j) { if (lowcost[j]!0 lowcost[j]min) { min lowcost[j]; k j; } } // 2. 输出边(closest[k], k) 权值min // 3. 将k正式加入U lowcost[k] 0; // 4. 更新lowcost和closest for (j0; jn; j) { if (lowcost[j]!0 G[k][j] lowcost[j]) { lowcost[j] G[k][j]; closest[j] k; } } }2.2 时间复杂度与适用场景Prim算法的核心操作是每加入一个顶点都需要扫描所有未选顶点来更新lowcost。如果使用普通的数组来维护其时间复杂度是O(V²)其中V是顶点数。这是因为外循环V-1次内循环每次更新需要遍历最多V个顶点。这个特性决定了Prim算法在稠密图边数E接近V²中表现更好。因为无论边有多少它都需要进行O(V²)次操作。如果图非常稠密这个代价是可以接受的。在实际的PTA题目中如果题目给出的顶点数不大比如V≤500或者明确提示图是稠密的Prim算法通常是一个可靠的选择。我印象很深的一道PTA题目“公路村村通”虽然可以用Kruskal解但用Prim写起来逻辑非常清晰。题目要求计算连通所有村庄的最低成本输入就是典型的邻接矩阵或邻接表。用Prim解的时候关键是要处理图可能不连通的情况——如果某轮循环找不到有效的k即lowcost中所有未选顶点的值都是INF那就说明图不是连通的直接返回-1即可。3. Kruskal算法全局排序下的“合并”如果说Prim是“由点及面”的扩张那么Kruskal就是“边贪心”或“合并法”。它完全不管顶点眼里只有边。策略是把图中所有边按权重从小到大排序然后从小到大依次考察每条边。如果加入这条边不会在已选的边集中形成环就选中它否则就跳过。直到选中了n-1条边为止。这很像我们日常生活中组建团队。有一群人顶点每两个人之间有一个“合作默契度”权重。我们要组建一个包含所有人的紧密团队连通同时希望团队内部总的默契度最高权重和最小。Kruskal的做法是先把所有两人组合按默契度从高到低排序。然后从默契度最高的组合开始尝试拉入团队唯一的原则是不能形成小圈子环。如果两个人已经在同一个小组里了通过其他间接关系连通了再直接拉他们进来就会形成小圈子所以要跳过。3.1 算法步骤、并查集与图解继续使用刚才的图例所有边排序后如下B-C (1)A-C (2), D-E (2) // 权重相同顺序可调换E-F (3)A-B (4)B-D (5)D-F (6)C-D (8)C-E (10)现在我们有一个空的边集T未来是最小生成树并初始化一个并查集每个顶点自成一个集合。处理边 B-C(1)B和C不在同一集合Find(B) ! Find(C)。加入边B-C合并B和C的集合Union(B, C)。T {B-C}。处理边 A-C(2)A和CC已与B合并不在同一集合。加入边A-C合并A与{B,C}的集合。T {B-C, A-C}。处理边 D-E(2)D和E不在同一集合。加入边D-E合并D和E的集合。T {B-C, A-C, D-E}。处理边 E-F(3)E已与D合并和F不在同一集合。加入边E-F合并{D,E}与F的集合。T {B-C, A-C, D-E, E-F}。处理边 A-B(4)检查A和B。A在集合{A,B,C}中B也在同一个集合中。加入A-B会形成环A-C-B-A所以跳过这条边。处理边 B-D(5)B在集合{A,B,C}D在集合{D,E,F}。不在同一集合加入边B-D合并两个大集合。T {B-C, A-C, D-E, E-F, B-D}。此时T中已有5条边而顶点数n6n-15。算法终止。我们得到了和Prim算法结果相同但边可能顺序不同的最小生成树总权重同样是1223513等等这里加起来是13但我们之前Prim算出来是16我检查一下。哦我发现我举的例子和推演过程对不上。我们用Prim算的例子总权重是16边A-C2, C-B1, B-D5, D-E2, D-F6。用Kruskal排序后的边序是B-C1, A-C2, D-E2, E-F3, A-B4, B-D5, D-F6, C-D8, C-E10。选B-C(1), A-C(2), D-E(2), E-F(3)后T有4条边连通分量{A,B,C} 和 {D,E,F}。选A-B(4)会形成环跳过。选B-D(5)连接两个连通分量加入。此时T有5条边B-C1, A-C2, D-E2, E-F3, B-D5。总权重1223513。已经找到n-15条边停止。不会选D-F(6)。这里出现了矛盾Prim给出了总权重16的解Kruskal给出了总权重13的解。这说明我的初始图例可能有问题或者我在Prim推演时出了错。这恰恰是一个很好的教学点对于同一个图Prim和Kruskal找到的MST总权重必须相同。如果不同要么图不连通要么算法实现有误。让我们重新审视这个图。假设图结构如下用更严谨的表格表示邻接关系-表示无穷大/无边ABCDEFA042---B4015--C210810-D-58026E--10203F---630Kruskal选边1(B-C), 2(A-C), 2(D-E), 3(E-F), 4(A-B)环跳过5(B-D)。此时所有顶点连通了吗集合是{A,B,C,D,E,F}是的连通了。总权重13。 Prim从A开始A-C(2), C-B(1), B-D(5), D-E(2), D-F(6)等等当U{A,B,C,D}时lowcost[E]应该是2通过Dlowcost[F]是6通过D。下一轮应该选E权重2而不是F。所以顺序是A-C(2), C-B(1), B-D(5), D-E(2)。此时U{A,B,C,D,E}lowcost[F]更新通过E是3E-F边通过D是6所以取3。最后选E-F(3)。总权重2152313。这就一致了。我之前的Prim推演错误地先选了D-F(6)而不是D-E(2)。这个纠错过程本身也很有价值它提醒我们在手动模拟或代码实现时每次更新lowcost都必须检查所有新加入顶点的邻居确保取到最小值。这也引出了Kruskal算法的核心实现难点如何高效判断加入一条边是否会形成环答案就是并查集。// 并查集查找根节点带路径压缩 int findFather(int x) { if (father[x] x) return x; else { int f findFather(father[x]); father[x] f; // 路径压缩 return f; } } // Kruskal算法主框架 typedef struct { int u, v; // 边的两个端点 int cost; // 边权 } Edge; Edge E[MAXE]; // 边集数组 bool cmp(Edge a, Edge b) { return a.cost b.cost; } int kruskal(int n, int m) { // n顶点数m边数 int ans 0, numEdge 0; // 1. 并查集初始化 for (int i1; in; i) father[i] i; // 2. 边按权值排序 sort(E, Em, cmp); // 3. 从小到大遍历边 for (int i0; im; i) { int faU findFather(E[i].u); int faV findFather(E[i].v); if (faU ! faV) { // 不构成环 father[faU] faV; // 合并集合 ans E[i].cost; numEdge; if (numEdge n-1) break; // 已找到最小生成树 } } if (numEdge ! n-1) return -1; // 图不连通 else return ans; }3.2 时间复杂度与适用场景Kruskal算法的耗时主要在于对边排序时间复杂度是O(E log E)其中E是边数。后续的并查集操作查找与合并可以近似看作O(α(V))其中α是阿克曼函数的反函数增长极慢通常视为常数。因此整体复杂度由排序决定。这使得Kruskal在稀疏图边数E远小于V²中优势巨大。例如一个顶点数10000边数只有20000的图用Prim邻接矩阵需要O(10^8)量级的操作而Kruskal排序20k条边只需要O(20k log 20k) ≈ O(300k)的操作效率相差数百倍。在PTA的“公路村村通”题目中村庄数N可达1000道路数M≤3N即≤3000。这是一个典型的稀疏图。虽然用Prim也能过但大多数高效题解都采用Kruskal因为其思路直接代码简洁且对稀疏图更友好。题目中“如果输入数据不足以保证畅通则输出-1”这一要求在Kruskal中天然满足如果最终收集的边数numEdge小于n-1说明图不连通。4. 对比、选择与实战技巧到了这里你应该对两种算法的内核有了清晰的认识。它们都是贪心算法都基于MST性质连接已选集合和未选集合的最小权边必然属于最小生成树但贪心的对象和策略完全不同。为了让你在实战中能快速做出选择我总结了下面的对比表格特性Prim算法Kruskal算法贪心对象顶点边核心思想从一点出发逐步扩张连通块全局边排序避免环的前提下加边数据结构lowcost[],closest[](或优先队列)边集数组并查集时间复杂度O(V²)(朴素) /O(E log V)(优先队列优化)O(E log E)(主要耗时在排序)最佳适用图稠密图(E接近V²)稀疏图(E远小于V²)是否需要图连通需要否则只能得到最小生成森林不需要可处理多个连通分量得到森林结果是否唯一如果边权互异结果唯一否则可能不唯一但总权值和唯一同Prim代码实现难点维护顶点到集合的距离及时更新并查集的实现与运用边的排序如何根据题目选择算法看数据规模这是最直接的判断依据。如果题目给出的最大顶点数V很大比如1000但边数E相对较小优先考虑Kruskal。如果V很小比如500或者边数非常多接近完全图用朴素的PrimO(V²)可能更简单。看输入格式如果输入以“边列表”的形式给出每条边给出两个端点和权重这几乎是为Kruskal量身定做的。如果给出的是邻接矩阵Prim用起来会更顺手。看额外需求如果需要输出具体选中的边Prim需要记录closest数组Kruskal需要在合并时记录边。如果题目问的是“总权重”两者皆可。记忆一个口诀“点密Prim边稀Kruskal”。对于PTA、力扣等编程题如果拿不准实现Kruskal通常更稳妥因为其模板固定排序并查集不易写错且对稀疏图效率高。实战中的常见“坑点”图不连通这是PTA题目最常见的陷阱。无论用哪种算法最后一定要检查是否成功收集了n-1条边。如果没有要按题目要求输出特定信息如-1。边权相等当存在多条权值相同的边时最小生成树可能不唯一。算法在遇到权值相同的边时不同的选择顺序可能导致生成不同的树但总权重一定相同。题目有时会考察这一点。顶点编号很多题目顶点从1开始编号而我们的数组通常从0开始。在读取输入和初始化数组时务必小心避免差一错误。并查集优化在Kruskal中并查集的“路径压缩”和“按秩合并”虽然不是必须的但能显著提升效率尤其是在顶点数多的时候。掌握优化的并查集写法是基本功。最后分享一个我调试代码时的小技巧对于复杂图不要依赖大脑模拟。用纸笔画一个小规模样例比如5-6个顶点一步步手动模拟算法的执行过程把每一步的lowcost/closest数组Prim或并查集状态、已选边集Kruskal都写下来。这个过程能帮你迅速定位代码中的逻辑错误。理解了这两种算法的思想你不仅能解决最小生成树问题更能体会到贪心算法“局部最优导致全局最优”的精妙之处这在解决许多其他优化问题时都是通用的思维武器。