企业官网建设流程全解析

如果你在大学里学过数据结构，这门课里最容易被低估的内容之一，我猜是最小生成树。它的场景很直白：给一张连通的无向带权图，要在 n 个点之间选出 n-1 条边，把所有点连在一起，同时让这些边的总权重最小。这个问题的两个经典解法，就是 Prim 算法和 Kruskal 算法。我当时第一次看到它们的时候，觉得不过就是两套贪心规则而已；后来真正去手算、写代码、跑几个测试用例才发现，里面值得掰开揉碎讲的细节其实不少。

很多教材会把这两个算法放在同一节里，好像讲完就结束了。但实际上，它们一个是“从一个点慢慢长大成一棵树”，另一个是“把一堆碎片逐步拼成一棵树”，思考路径完全不同。你如果不搞清楚它们背后的依据，做题的时候会陷入一个很尴尬的状态：能默写下伪代码，但一变图就不知道错在哪。这篇文章我打算把算法背后的贪心依据、两种算法的完整过程、代码实现细节，还有我实际调试时踩过的坑，一次性说清楚。

1. 先把问题本身看透：最小生成树到底在求什么

1.1 从一个小场景引出图的模型

想象一下，现在有 6 个城市要通网络，已知任意两个城市之间拉光缆的造价，怎么选线路让总造价最低？这个问题抽象成图就是：顶点是城市，边是可能的线路，边权是造价。我们最后要留下的不是一个包含所有边的图，而是一个能连通所有顶点且总权重最小的边集。

为什么结果一定是一棵树？因为只要加了 n-1 条边就能连通 n 个顶点。如果你选了 n 条边，多出来的那一条必定会形成环；从环里删掉任意一条边，图依然是连通的，但总权重只会变小或不变。所以最终答案不可能是“带环的连通图”，只能是一棵树。这就是最小生成树这个名字的来源：一颗“连接全部顶点、总权重最小”的树。

这里有一个容易混淆的点：图本身可能带环，但我们选的边不能带环。Prim 和 Kruskal 每一步真正在做的事情，就是“在安全的前提下把一条边加入答案”。所谓安全，指加入后不会成环，且这条边必然存在于某棵最小生成树中。理解了“安全边”这个概念，再去读两种算法的步骤，会顺畅很多。

1.2 贪心策略凭什么正确：割定理

很多初学者会问：每一步都选当前看起来最小的边，最后结果能保证全局最优吗？这在图论里不是一个“感觉对就行”的问题，它有一个非常漂亮的支撑原理，一般叫割定理或者 cut property。

先把图中的所有顶点分成两组，比如左边一组 A，右边一组 B。这种分组方式就叫一个“割”，而两端分别落在两组里的边，叫“跨越这个割的边”。割定理说的是：在跨越某个割的所有边里，权重最小的那条边，一定存在于某棵最小生成树中。

证明思路不复杂。假设这条最小跨越边是 e，而某棵最小生成树 T 里没有 e。把 e 加入 T，T 里必然出现一个环。这个环要连通左右两组，因此环里一定还有另一条跨越割的边 e'。把 e' 从环里删掉，把 e 放回去，图依然是连通的，而且总权重不会变大。所以必然存在一棵包含 e 的最小生成树。

Prim 算法做的就是：始终把当前生成树看成 A 组，剩下的顶点看成 B 组，每次选跨越这两组的最小边。Kruskal 做的则是：每时每刻都有多个等价类，每个等价类是一组；某条边如果连接两个不同的组，这条边就在“这两个组形成的割”里是最小的跨越边之一。两个算法都不过是在反复使用割定理而已。

2. Prim 算法：像水波纹一样，从一点向外扩

2.1 算法步骤拆解

Prim 算法的思路很容易记住：随便选一个起点，把它当成一棵只有一个节点的树；然后每次找一条“一端在这棵树里、另一端不在树里”的边，选权重最小的，把新的顶点加进树里；重复直到所有顶点都进来。

伪代码可以写成这样：

visited[1] = true while 生成树里的顶点数 < n: 从所有 (u, v, w) 中找满足 u 已访问、v 未访问的最小 w 对应的边 visited[v] = true ans += w 更新所有从 v 出发、指向未访问顶点的边

注意，它和 Dijkstra 长得非常像，但含义完全不同。Dijkstra 维护的是“从起点到各个点的最短距离”，更新时是dist[v] = min(dist[v], dist[u] + w)；Prim 维护的是“生成树边界到各个外部点的最短连接边”，更新时是key[v] = min(key[v], w)，不加前缀距离。如果你按 Dijkstra 的写法把距离累加起来，结果必错。

2.2 手算一个完整例子

光看伪代码不够，我实际算一遍给你看。考虑下面这个 6 个顶点的图：

• 顶点编号 1 到 6
• 边和权重如下：
  • (1,2)=6
  • (1,3)=1
  • (1,4)=5
  • (2,3)=5
  • (2,5)=3
  • (3,4)=5
  • (3,6)=4
  • (4,6)=2
  • (5,6)=6

从顶点 1 开始，每一轮选边如下：

最终选出的边是：(1,3)、(3,6)、(6,4)、(3,2)、(2,5)，总权重 1+4+2+5+3=15。这个结果是不是唯一的最小生成树？在这里刚好是 15，但如果有同权边，可能会有多个不同的最小生成树总数相同。这不影响算法正确性，你随便选哪条合法最小边都行。

为什么起点选哪个都无所谓？因为初始时“割”就是 {起点} 和其余顶点，Prim 选的是这个割的最小跨越边。下一步，生成树集合扩大后，又是新的一组割。每一步都符合割定理，所以起点只是改变选边顺序，不会改变最终最优总权重。

2.3 两种实现姿势：邻接矩阵和优先队列

Prim 有两种常见实现方式。当图比较稠密，比如 n 只有几百、上千，边数接近 n²，可以直接用邻接矩阵和 O(n²) 的扫描法。每次找一个未访问顶点中 key 最小的点，然后更新邻接矩阵里的边。

当图比较稀疏，比如 n 很大但每条边都很少，再用 O(n²) 扫描就会很亏，这时应该用邻接表加优先队列。实现时有几个容易出错的点：

• 优先队列里可能同时存在同一个点的多个旧记录，因为一条边可能被重复 push 多次。
• 堆顶弹出的点如果已经访问过，要直接跳过，不能把这个权重累加到答案里。
• 只有在visited[v] == false时才需要把邻居边 push 进堆。

复杂度上，邻接矩阵版是 O(n²)，优先队列版是 O(E log V)，其中 E 是边数。实际刷题时，题目给的图是稠密还是稀疏，基本上决定了你该写哪种。

3. Kruskal 算法：把边从小到大一条条捡起来

3.1 先把所有边排序，再决定要不要

Kruskal 的思路比 Prim 更“暴力”：把图中所有边按权重从小到大排序，然后从最小的开始，一条条尝试加入答案。加入的唯一条件是，这条边的两个端点当前不在同一个连通分量里；如果在同一个分量里，说明加进去会成环，直接丢掉。

所以整个算法的骨架特别简单：

把 edges 按权重从小到大排序 初始化并查集 ans = 0 for (u, v, w) in edges: if find(u) != find(v): union(u, v) ans += w 如果已经选了 n-1 条边，提前结束

还是用刚才那张图。所有边排序后是：

(1,3)=1, (4,6)=2, (2,5)=3, (3,6)=4, (1,4)=5, (2,3)=5, (3,4)=5, (1,2)=6, (5,6)=6。

逐条处理：

最后选中的边是 (1,3)、(4,6)、(2,5)、(3,6)、(2,3)，总权重也是 15。可以看到，Kruskal 和前面对 Prim 手算选出的边并不完全一样，但总权重一致。这也是最小生成树“结果可能不唯一”的一个具体体现。

3.2 并查集优化：Kruskal 的核心支柱

Kruskal 如果不配合并查集，每处理一条边都去遍历当前森林判断连通性，复杂度会非常高。并查集要解决的核心问题是：动态维护若干个不相交集合，支持查询两个元素是否同属一个集合，以及合并两个集合。

标准做法有两个优化：路径压缩和按秩合并。路径压缩让 find 过程中一路把节点直接挂到根上；按秩合并则用集合大小或树高决定谁挂到谁下面，避免并查集退化成一条长链。二者配合后，每次 find/union 的均摊代价几乎可以看成常数，也就是常说的反阿克曼函数量级。在普通竞赛题和面试题里，你写一个带路径压缩和按 size 合并的并查集就足够了。

另外注意一个细节：算法不需要一开始就把边权相同的边分个先后。如果两条边权重一样，先处理哪条都行，最终总权重一样。前提是并查集逻辑正确，并且真的按权重非降序处理。

3.3 图不连通时怎么办

最小生成树的前提是图连通。如果图本身是断开的，Kruskal 处理完所有边后，选中的边数一定小于 n-1。这时应该返回“不存在最小生成树”，或者返回 -1。很多人第一次写这题时会漏掉这个判断，直接在循环里 break，最后输出 0，这就会在断开图上出大问题。

Prim 也一样。优先队列版本里，如果堆空了但cnt < n-1，说明从起点出发根本连不全所有顶点，应当返回不存在。邻接矩阵版本里，如果某一轮找不到 key 值有限的未访问点，同样说明图不连通。

4. 两个算法放在一起对比，才知道什么时候选谁

4.1 核心差异对比

光看复杂度，Prim 用堆是 O(E log V)，Kruskal 是 O(E log E)。当 E 很大时，Kruskal 的排序开销会凸显出来；当图很稠密、E 接近 V² 时，Prim 的邻接矩阵版 O(V²) 常常比 Kruskal 更稳。

4.2 稠密图和稀疏图的选择逻辑

实际做题或者写工程代码时，我不会只看最坏复杂度，还会看实现难度和常数。如果 n 范围是 1000 以内，并且题目直接用邻接矩阵给你，那写 Prim 矩阵版是最省心的，循环两遍就完事。如果 n 是 10⁵，边是 10⁶ 级别的稀疏图，肯定用 Kruskal，因为只需要一个边数组和一个并查集，内存可控。

还有一种情况：题目给的边已经排好序，那几乎不用犹豫，直接 Kruskal，排序成本直接省掉。反过来，如果题目给的是邻接矩阵，你又不想再单独建边数组，那 Prim 矩阵版更顺手。

关于“稠密图用 Prim、稀疏图用 Kruskal”这句口诀，我用过很久，总体来说是对的。但注意 Prim 的堆优化版本并不适合所有稠密图，因为稠密图里 push 到堆里的边会非常多，反而比 O(V²) 扫描慢。所以具体问题还是要看数据规模，不能只背结论。

4.3 一个容易被忽略的工程问题：排序是 Kruskal 的大头

Kruskal 的“把所有边排序”这一步，往往比并查集本身更耗时。如果 E 是 10⁶，排序时间几乎占整个算法的一半以上。所以在某些需要极致的场景里，可以先看看数据结构里有没有“边权范围很小”这个条件；如果有，可以考虑计数排序的思路，按边权分桶，这样能把 O(E log E) 的排序优化成近似 O(E + W)。

不过这只是竞赛题里的优化方向。普通项目里直接使用语言自带的排序，然后配合并查集，已经足够稳定了。我在实际写代码时，更关心的是别让并查集退化，排序本身反而是最不需要担心出错的部分。

5. 代码落地：从伪代码到能跑的 Python 版本

5.1 Prim 的优先队列实现

下面这份代码处理顶点编号 1 到 n 的情况。adj[u]是 u 的邻居列表，元素为(v, w)。

import heapq def prim_mst(n, adj): visited = [False] * (n + 1) heap = [] visited[1] = True for v, w in adj[1]: heapq.heappush(heap, (w, v)) ans = 0 cnt = 0 while heap and cnt < n - 1: w, u = heapq.heappop(heap) if visited[u]: continue visited[u] = True ans += w cnt += 1 for v, nw in adj[u]: if not visited[v]: heapq.heappush(heap, (nw, v)) return ans if cnt == n - 1 else -1

这里最关键的防御性写法是if visited[u]: continue。因为同一个点可能被 push 多次，第一次弹出时标记访问，后面再弹出旧记录就必须直接跳过。如果你在堆里弹出节点后不检查 visited，很容易把同一条边重复算进答案。

5.2 Prim 的邻接矩阵实现

当 n 不大且图较稠密时，用矩阵版 O(n²) 会比堆更好写，也更快：

def prim_dense(n, cost): visited = [False] * n dist = [float('inf')] * n dist[0] = 0 ans = 0 for _ in range(n): t = -1 for i in range(n): if not visited[i] and (t == -1 or dist[i] < dist[t]): t = i if dist[t] == float('inf'): return -1 visited[t] = True ans += dist[t] for i in range(n): if not visited[i] and cost[t][i] < dist[i]: dist[i] = cost[t][i] return ans

这个版本里，dist[v]表示“当前生成树到顶点 v 的最小连接边权”，不是从源点到 v 的总路径长度。初始化时dist[0] = 0，所以第一个顶点会先被选中，这是正常的。

5.3 Kruskal 的并查集版本

class DSU: def __init__(self, n): self.parent = list(range(n + 1)) self.size = [1] * (n + 1) def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] x = self.parent[x] return x def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] return True def kruskal_mst(n, edges): edges.sort(key=lambda e: e[2]) dsu = DSU(n) ans = 0 cnt = 0 for u, v, w in edges: if dsu.union(u, v): ans += w cnt += 1 if cnt == n - 1: break return ans if cnt == n - 1 else -1

这里的find我用了迭代写法加路径压缩，而不是递归。递归写法在链很长的时候有可能撑爆栈，迭代版更稳。union永远把 size 小的集合挂到 size 大的集合下面，这样并查集树高能始终保持很低。

6. 常见问题与避坑实录

6.1 为什么 Prim 的结果总不对：问题多半出在更新那一步

我见过最多的错误，是把 Prim 的key[v]更新写成了dist[v] + w，这本质上是在算最短路径而不是最小生成树。还有一种错误是，堆里弹出旧记录时没有跳过 visited 节点，把重复的边权也累加了。每次调试这种问题，我都会在选边循环里临时打印(u, v, w)，看选出来的边是不是成环。如果发现答案比预期大，优先检查这两处。

6.2 Kruskal 的并查集优化：不是锦上添花，是核心

如果不加路径压缩、也不按 size 合并，只用一个简单的parent数组，Kruskal 在某些测试数据下会非常慢。比如一条链状并查集，每次 find 都要走到头，复杂度可能退化。按 size 合并和路径压缩一起用后，几乎可以认为是常数时间。另外一个细节：union返回True/False可以让代码很干净，但返回值一定要判断，不能盲目累加答案。

6.3 带负权边和零权边怎么处理

Prim 和 Kruskal 对正负权重没有特殊要求。你可以在图上加权值为负的边，算法依然成立，因为割定理不依赖权重为正。这和大名鼎鼎的“最短路径里负权边需要小心”是两回事，别混淆。最小生成树选的是边的总权重尽量小，所以负权边越多越会被优先选中，这是正常的。

6.4 自环、重边和断开的图

自环在 Kruskal 里会被并查集自动忽略，因为find(u)和find(v)相等。在 Prim 里，用邻接矩阵时要注意cost[i][i]不能设成 0，最好设成无穷大，否则可能把自环当成一条合法边界边。重边则完全不用处理，Kruskal 排序后自然处理，Prim 的更新也只会保留更小权重。

断开的图是个隐蔽的坑。很多模板代码在循环结束后直接返回 ans，如果没有检查已选边数是不是 n-1，断开图会输出一个不正确的偏小答案。我在写代码时习惯把返回结果写成ans if cnt == n-1 else -1，这样接口不会骗人。

6.5 一个小习惯：用两个算法互相验证

我练题的时候有个习惯：同一道题先写 Kruskal，再写 Prim，跑随机小图对拍。这样既能验证自己对两种算法理解的正确性，也能在写法上形成肌肉记忆。事实上我后来很多次重构自己代码，都是靠两个实现互相查错才定位到问题所在的。min-cut 和 union-find 这类细节，你光看是看不出来的，必须亲手写一遍，再故意制造几个边界用例，比如只有一个顶点、图完全断开、所有边权相等，才能真正放心。