企业官网建设流程全解析

今天训练营打卡到第五十六天，内容来到了最小生成树，主角是prim算法和kruskal算法。前面刚啃完Dijkstra、Bellman-Ford这些最短路问题，现在换成另一个经典场景：有若干个点，怎么用总代价最小的边把它们全部连通。如果你正在跟代码随想录，或者刷图论刷到瓶颈期，这篇文章可以完整看一遍。我不只讲两个算法的模板，还会把第五十六天配套练习的完整复盘、常见报错、以及我实际踩过的坑一起写出来，希望能帮你真正把这块知识焊死在脑子里。

很多人在这个阶段容易卡住，原因不在于算法有多难，而在于思维还没从“单源最短路”切换过来。最短路求的是从一个点到另一个点怎么走最近，最小生成树求的却是把整张图连成一个整体最少要多少代价。一个是局部路径问题，一个是全局连通问题。脑子转不过这个弯，后面看代码就会总觉得眼熟，但一写就错。

1. 为什么第五十六天要同时啃下prim算法和kruskal算法

1.1 先搞清楚最小生成树到底解决什么问题

最小生成树的定义可以概括为：在一张带权无向图里，选出 n-1 条边，把所有 n 个节点连通，并且选出的边权总和最小。

听起来有点像“连通图的最短方案”，但注意这里没有指定起点终点，目标是整体连通。生活里最典型的例子就是农村通网线：每个村子是一个节点，村子之间拉光缆需要成本，怎么设计线路才能让所有村子都通网，同时总造价最低？这就是一个标准的最小生成树问题。

为什么叫“树”？因为你最后选出来的 n-1 条边必然不会成环。有环意味着有一条边是多余的，去掉它照样连通，代价还能更小。所以最优解一定满足树的结构。这个“无环”性质看起来很朴素，但它是后面kruskal算法用并查集判环的根基，也是prim算法里“不断扩张集合”的逻辑支撑。

很多初学者会把最小生成树和最短路混在一起，我建议你在入门阶段就把两者彻底分开：最短路关心“点到点”，最小生成树关心“整张图”。想清楚这个区别，后面所有代码都顺了。

1.2 两种思路，两个复杂度维度

Prim算法和Kruskal算法是求解最小生成树的两种经典策略，它们都是贪心，但贪的角度完全不同：

• Prim算法从点出发。先随便选一个起点，把这个点看作一个集合，然后每次从集合外找一个离集合最近的点拉进来，同时把对应的边加入答案，直到所有点都在集合里。
• Kruskal算法从边出发。把所有边按权值从小到大排序，然后从最小的边开始试，如果这条边连接的两个点还没有被连通，就选它，否则跳过，直到选出 n-1 条边。

这个差异直接决定了它们的复杂度和使用场景。朴素Prim的时间复杂度是 O(V²)，这里的 V 是节点数，它和边的数量无关，所以特别适合稠密图；Kruskal的时间复杂度主要花在排序上，是 O(E log E)，E 是边数，在稀疏图里表现更好。堆优化Prim的复杂度是 O(E log V)，但实际工程里极少用，因为Kruskal写起来更短，也更难出错。

我在训练营里看到很多同学问“到底学哪个”，我的建议是：两个都必须会，但心里要有一把尺子，看到题目先判断图的规模，再决定用哪个。这也是面试官最喜欢考察的点，后面我会专门展开。

1.3 同一天学，对比着记忆效率更高

这两个算法放在同一天学不是巧合，因为它们的对照价值太强了。Prim的核心难点在于维护“点到已选集合的最近距离”，很多人这里会跟Dijkstra搞混；Kruskal的核心难点在于并查集判环，写不熟就会在合并操作上翻车。两者各有各的易错点，同一天反复对照，反而记得牢。

我有一次给朋友讲这块内容，用了个特别直白的类比：Prim像装修新家，已经装修好的房间算一个整体，然后每次挑一个离这个整体最近的房间来装；Kruskal像拼乐高，所有零件按价格标签排好队，从最便宜的开始，只要不拼成环就往上装。两个思路一个是“向内扩张”，一个是“向外拼装”，本质都是在做贪心选择。

这种对照记忆特别适合应付笔试和面试。笔试里直接考模板题，你要能快速写出两种解；面试里考思路题，你要能说出“稠密图用Prim、稀疏图用Kruskal”以及背后的复杂度原因。把两个算法放在同一天理解透，绝对比分开学效率高。

2. prim算法模板：从点开始生长的贪心

2.1 朴素版Prim的完整流程与生活类比

朴素版Prim的过程可以用一个例子讲清楚。假设有 1 到 5 共五个节点，你先选择节点 1 作为起点，把它标记为“已在生成树中”。接下来看所有从节点 1 出发的边，挑一条最短的，假设是 1-2，把节点 2 也拉进来。现在已选集合是 {1,2}，下一步再看这个集合里所有点能够到的外部点，取距离最近的那个，不断重复，直到所有节点都被拉进来。

具体到代码，我们需要一个关键数组 minDist，它的语义是：每个未加入集合的节点，到当前已选集合的最短距离。注意“到集合”这三个字，不是到某个固定点的距离。这一点是我认为整个Prim算法最容易理解错的地方，后面我会专门对比一下Dijkstra。

流程可以总结成三步：

1. 初始化 minDist 数组为无穷大，选择一个起点，将起点到集合的距离设为 0。
2. 循环 n 次，每次从“未加入集合的节点”中找出 minDist 最小的节点 u，把它加入集合，并累计边权。
3. 用刚加入的节点 u 去更新其他未加入节点到集合的距离。

为什么要循环 n 次而不是 n-1 次？因为第一次循环把起点加入集合时，累计的边权是 0，如果写 n-1 次就会漏掉起点。很多模板里写 n 次，或者写 n-1 次但把起点特殊处理，效果一样，看个人习惯。

2.2 和Dijkstra的同与不同

Prim和Dijkstra的代码结构看起来几乎一模一样：都是维护一个距离数组，每轮找一个最小的未访问点，然后用它去更新其他点。但它们的距离定义有本质区别。Dijkstra里的 dist[v] 表示节点 v 到起点的最短距离，所以更新时是dist[v] = min(dist[v], dist[u] + w)；Prim里的 minDist[v] 表示节点 v 到已选集合的最近距离，更新时是minDist[v] = min(minDist[v], w)，根本没有起点距离什么事。

这个不同导致了一个特别常见的错误：有人图省事，把之前写过的Dijkstra模板直接改两行就拿来当Prim用，结果更新公式没换，算出来的答案完全不对。我在训练营答疑区看过好几个这样的问题，都是把dist[start]+w带进了Prim的更新里。

你一定要记住一个口诀：Dijkstra算距离用的是累加，Prim算距离用的是直连边权。前者是路径的叠加，后者是集合到点的最小边。这个点想通了，Prim的代码不会再跟Dijkstra混淆。

2.3 朴素版代码模板

下面是一份可以直接用的C++模板，适用于邻接矩阵存图的稠密图场景：

#include <bits/stdc++.h> using namespace std; const int MAXN = 505; const int INF = 0x3f3f3f3f; int n, m; int grid[MAXN][MAXN]; int prim() { vector<int> minDist(n + 1, INF); vector<bool> inTree(n + 1, false); minDist[1] = 0; int total = 0; for (int i = 0; i < n; i++) { // 找未加入集合且距离最小的点 int u = -1, best = INF; for (int v = 1; v <= n; v++) { if (!inTree[v] && minDist[v] < best) { best = minDist[v]; u = v; } } // 如果找不到，说明图不连通 if (u == -1) return -1; inTree[u] = true; total += best; // 用 u 更新其他未加入点到集合的距离 for (int v = 1; v <= n; v++) { if (!inTree[v] && grid[u][v] < minDist[v]) { minDist[v] = grid[u][v]; } } } return total; } int main() { memset(grid, 0x3f, sizeof(grid)); cin >> n >> m; while (m--) { int u, v, w; cin >> u >> v >> w; // 无向图，对称存储，重边只保留最小权值 grid[u][v] = grid[v][u] = min(grid[u][v], w); } cout << prim() << endl; return 0; }

这份模板里我特别加了两个处理：一是无向图要对称赋值grid[u][v] = grid[v][u]；二是重边要取最小值。前者忘记写会导致半边图完全无法更新，后者会让答案被重复边干扰。这两个点都是我在实际刷题时踩过的坑。

2.4 什么时候必须用堆优化Prim

朴素Prim在节点少、边多的稠密图里非常好用，因为不管边有多少条，内层两层循环都是 O(n²)。但一旦节点数到了几万，图的边数又没多到“完全图”的程度，O(n²) 就会超时，这时要么Kruskal，要么堆优化Prim。

堆优化Prim的思路是：用一个优先队列维护“候选边”，每次从堆顶弹出最小权值的边，如果边的终点还没加入集合，就加入。它的代码比朴素版长，而且很容易在“重复入堆”的处理上出bug。我个人的倾向是，如果场景需要堆优化，直接换Kruskal，因为Kruskal的代码更短、逻辑更直观。但如果是稠密图且边数极大，朴素Prim的 O(n²) 反而比Kruskal的 O(E log E) 快，这个时候Prim是正解。

3. kruskal算法模板：从边开始筛选的贪心

3.1 并查集为什么是Kruskal的地基

Kruskal算法的核心操作是：每来一条边，判断它的两个端点是否已经被当前选出的边连通。如果已经连通，再选这条边就会成环；如果没有连通，就放心地选它。

这个“判断是否连通”的操作，如果每次都用DFS或BFS重新搜索一遍，代价太高。所以我们需要并查集。并查集维护的是“哪些节点属于同一个集合”，每次新加一条边时，看这条边的两个端点find(u)和find(v)是否相等，相等说明它们已经在一个连通分量里，这条边必须跳过；不相等就执行合并，把两个集合union起来。

为什么选边时要优先考虑小边？这要用贪心思想来解释。想象一下，如果最小的那条边 e 不在某个最小生成树里，那我们把它加进去，一定会形成一个环，环上至少有一条边比 e 大，把那条大边删掉，生成树依然连通，且总代价更小。所以最小边一定出现在某个最优解里。不断重复这个推理，就得到了“从小到大尝试每条边”的Kruskal策略。

3.2 排序加扫描的两步式流程

Kruskal的过程可以压缩成两句话：边按权值从小到大排序，然后从头扫到尾。

扫描时，对每条边(u, v, w)执行以下判断：

1. 找出 u 的根节点和 v 的根节点；
2. 如果两个根相同，说明 u 和 v 已经连通，这条边会造成环，跳过；
3. 如果根不同，说明这是连接两个不同连通分量的桥，选中它，累加 w，并合并两个集合；
4. 每选中一条边，计数加一，直到选中了 n-1 条边，提前结束。

这个流程有个天然的好处：只要图是连通的，你一定能选出 n-1 条边。如果扫描完所有边，选中的边数还不到 n-1，说明图本身不连通，不存在最小生成树，此时要输出特定值，比如 -1。

3.3 Kruskal代码模板

我常用的Kruskal模板如下，并查集部分采用路径压缩写法：

#include <bits/stdc++.h> using namespace std; struct Edge { int u, v, w; bool operator<(const Edge& other) const { return w < other.w; } }; vector<int> parent; int findParent(int x) { if (parent[x] != x) parent[x] = findParent(parent[x]); return parent[x]; } int main() { int n, m; cin >> n >> m; vector<Edge> edges(m); for (int i = 0; i < m; i++) { cin >> edges[i].u >> edges[i].v >> edges[i].w; } sort(edges.begin(), edges.end()); parent.resize(n + 1); for (int i = 1; i <= n; i++) parent[i] = i; int total = 0, cnt = 0; for (Edge& e : edges) { int ru = findParent(e.u); int rv = findParent(e.v); if (ru != rv) { parent[ru] = rv; total += e.w; cnt++; if (cnt == n - 1) break; } } if (cnt < n - 1) cout << -1 << endl; else cout << total << endl; return 0; }

这段代码里值得注意的地方有三个。一是parent[ru] = rv这行，我见过有人写成parent[u] = v，那样就绕过了find，压缩路径失效，严重时会导致判环错误。二是排序结构体一定要重载小于号，或者自定义比较函数，忘了会让边乱序。三是提前退出的条件cnt == n - 1，如果忽略这个剪枝，边多的时候后面的遍历全是无用功。

3.4 两个算法的横向对比速查表

我把两个算法的关键差异整理成一张表，方便你随时翻阅：

这张表在面试前扫一眼就行，能帮你迅速定位用哪种算法。如果你在实际做题时不知道图是稠密还是稀疏，可以先看一眼输入的数据范围，V 小 E 大用Prim，V 大 E 小用Kruskal，这个判断基本不会错。

4. 训练营第五十六天配套题目的完整复盘

4.1 先看清楚这道题的输入输出陷阱

第五十六天训练营的配套练习，拿来做两个算法落地的是一道典型的最小生成树板子题，题目内容大概是这样的：给定 n 个节点和 m 条带权无向边，求把这些节点连通的最小总代价。题目要求自己处理输入输出，节点编号从 1 开始，可能包含重边，图可能不连通。

这类题的难点不在算法本身，而在于工程细节。比如节点编号从 1 开始，意味着你的数组要开 n+1 大小，循环要从 1 到 n；比如可能有重边，如果用邻接矩阵存图必须取最小值；再比如图不连通时，两个算法要分别返回什么值。这些细节在模板题里就是区分“水题高手”和“模板默写机器”的地方。

我当时第一遍写的时候，就因为在邻接矩阵初始化时用了memset(grid, 0x3f, sizeof(grid))却忘了注意输入的节点编号从 1 开始，导致 grid[0] 被某条异常数据污染，调了半天才发现。所以你看，算法会了不代表题能过，工程细节才是真正拉分的地方。

4.2 用Prim解法完整过一遍

拿这道题来跑Prim，我会直接采用第2节那份邻接矩阵模板，因为它节点数通常不大，O(n²) 完全能过。整个提交的思考过程大概是这样的：

1. 读入 n、m，初始化邻接矩阵为一个很大的值；
2. 对每条边，取min存入对称位置，解决重边问题；
3. 调用 prim()，如果返回 -1，说明图不连通，否则输出总代价；
4. 提交时把样例输入粘进去，确认输出符合预期。

我用这份代码跑完样例后，又额外构造了一组数据自测：一个三角形，三条边权分别是 1、2、3，最小生成树应该是 1+2=3。如果输出不是 3，那一定是prim更新逻辑写错了。这个自测习惯强烈建议你也养成，因为它能在一分钟内定位大量低级错误。

下面是完整可提交的解答代码：

#include <bits/stdc++.h> using namespace std; const int MAXN = 505; const int INF = 0x3f3f3f3f; int main() { int n, m; cin >> n >> m; vector<vector<int>> grid(n + 1, vector<int>(n + 1, INF)); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; grid[u][v] = min(grid[u][v], w); grid[v][u] = min(grid[v][u], w); } vector<int> minDist(n + 1, INF); vector<bool> inTree(n + 1, false); minDist[1] = 0; int total = 0; for (int i = 0; i < n; i++) { int u = -1, best = INF; for (int v = 1; v <= n; v++) { if (!inTree[v] && minDist[v] < best) { best = minDist[v]; u = v; } } if (u == -1) { cout << -1 << endl; return 0; } inTree[u] = true; total += best; for (int v = 1; v <= n; v++) { if (!inTree[v] && grid[u][v] < minDist[v]) { minDist[v] = grid[u][v]; } } } cout << total << endl; return 0; }

这份代码有一个我很喜欢的设计：把“图不连通”的判断直接放在找最小点的地方，如果 u 还是 -1，就说明剩余未加入的点全部不可达，立刻输出 -1。这比循环结束后再判断更直接，也更好理解。

4.3 用Kruskal解法完整过一遍

Kruskal解这道题的过程也很顺。我当时的做法：

1. 把边的输入全部存到一个 vector 里；
2. 调用 sort 按权值升序排序；
3. 初始化并查集，每个节点的父亲是自己；
4. 遍历边数组，进行判断和合并，统计cnt；
5. 结束后看 cnt 是否等于 n-1，不是则输出-1。

这里有个小坑我要特别强调：题目说可能不连通，如果你只写了total += e.w却忘了统计 cnt，那么图不连通时你可能会输出一个看似正确的错误答案。一定要统计cnt，并且最后判断cnt < n - 1就输出-1。

完整代码如下：

#include <bits/stdc++.h> using namespace std; struct Edge { int u, v, w; }; vector<int> parent; int findParent(int x) { if (parent[x] != x) parent[x] = findParent(parent[x]); return parent[x]; } int main() { int n, m; cin >> n >> m; vector<Edge> edges(m); for (int i = 0; i < m; i++) { cin >> edges[i].u >> edges[i].v >> edges[i].w; } sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; }); parent.resize(n + 1); for (int i = 1; i <= n; i++) parent[i] = i; int total = 0; int cnt = 0; for (Edge& e : edges) { int ru = findParent(e.u); int rv = findParent(e.v); if (ru != rv) { parent[ru] = rv; total += e.w; cnt++; if (cnt == n - 1) break; } } if (cnt == n - 1) cout << total << endl; else cout << -1 << endl; return 0; }

这段代码用C++11的lambda表达式写排序比较器，就不用再给结构体重载小于号了，代码看起来更清爽。如果你想更稳一点，也可以给Edge加operator<，两种写法都可以。

4.4 一次提交后，怎么对照两份代码做复盘

我强烈建议你把Prim和Kruskal两种解法都跑同一组输入，然后比较输出。如果两个答案不一致，那不是Prim写错了，就是Kruskal写错了，或者两个都写错了。这种“双模自检法”特别适合训练阶段，它能逼着你去思考两份代码之间的对应关系，而不是背完模板就完事。

我实际跑题时还做过一个更极端的测试：把Kruskal的排序改成逆序，预期答案一定变差或者不变。如果逆序排序后输出的总代价反而变小了，说明我的判环逻辑有bug。这个技巧听起来有点野，但对于排查并查集合并方向是否正确非常有效。

5. 常见问题与排查技巧实录

5.1 高频问题速查表

我在训练营答疑和刷题过程中，总结出大家最常踩的五个坑，直接列给你：

这张表建议收藏一下，做题遇到诡异输出时先过一遍，经常能省下半小时调试时间。这些问题几乎没有一个是算法逻辑不懂造成的，全是细节。

5.2 真正的避坑经验

第一，Prim里的 minDist 数组在每一轮更新时，只更新未加入集合的点。我见过有同学在更新时不判!inTree[v]，导致已经加入的点反复被刷新，虽然答案偶尔能对，但完全依赖数据恰好不触发问题，属于隐患很大的写法。每次更新前判断一下，条件加一行不用一秒钟，能省一堆问题。

第二，Kruskal的并查集初始化千万不能忘。我早期写代码时习惯性地认为全局变量默认是0，结果忘了给 parent 做初始化，然后 find 一调用就死循环或者返回错值。这块建议背模板时连初始化代码一起背，形成肌肉记忆。

第三，不要迷信所谓“Prim一定比Kruskal简单”。Prim的朴素版确实代码短，但它的距离语义太容易出错了；Kruskal只是并查集多写一点，但每一步都清晰。两个都练熟，考试时选自己最有把握的那个，比临时临场切换要稳得多。

5.3 面试和笔试里的提分小技巧

面试时如果被问到最小生成树，不要一上来就背模板。可以先停顿一下，把题目条件梳理一遍：图是稠密还是稀疏？节点数多大？边数多大？然后再决定说用哪种算法。你能主动说出“这张图看起来边数很多，用朴素Prim的O(n²)更合适”这种话，面试官会立刻判断你有实战经验，而不是只会背代码。

笔试里数据范围是最大的提示。遇到 n 小于 1000、m 很大，直接用Prim；遇到 n 很大、m 跟 n 一个量级，用Kruskal。还有一个小经验：如果题目数据允许你用任意一种，优先写Kruskal，因为它的判环逻辑是独立的，不容易受到图存储方式影响，调试起来更顺手。

另外我强烈建议你准备一套“并查集+带权边结构体”的模板，因为它不止用于Kruskal，在很多图论题里都会重复出现。模板不用太长，能支持路径压缩和合并即可，真的遇到题目时，你会发现这套东西的复用率奇高。

第五十六天刷完之后，我个人最大的感受是：Prim和Kruskal虽然听起来高大上，但本质都是贪心，区别只在于从点下手还是从边下手。你在前面学Dijkstra时花了多少时间，在这里至少能省一半，因为思维模型是相通的。最后再分享一个我自用的自查技巧：一道MST题如果用Prim写，提交前我一定把同一组输入跑一遍Kruskal，两次结果一致才敢交。这两个算法互为校验，真的能筛掉大部分低级错误。打卡到第五十六天，进度已经不是最重要的，能不能把每个算法背后的贪心逻辑内化成自己的判断力，才是后半个月刷题的关键。