如何用最少的成本，把 n 个城市连接起来？如何铺设光纤、设计电路，既保证连通又成本最低？答案就在最小生成树中。
最小生成树（Minimum Spanning Tree, MST）是图论中至关重要的概念，广泛应用在网络设计、聚类分析、图像分割等领域。而 Kruskal 算法和 Prim 算法正是求解 MST 的两大经典算法。今天，我们就从原理到实践，把它们彻底搞懂。
一、什么是最小生成树？
1.1 定义
在无向连通图中，生成树是包含所有顶点的一个无环连通子图。如果图的每条边带有权重，那么最小生成树就是所有生成树中边权总和最小的那一棵。
性质：
- 包含 V 个顶点，恰好 V-1 条边。
- 无环，且连通。
- 最小生成树可能不唯一（当存在相同权重的边时）。
1.2 经典场景
- 设计一个光纤网络，连接 n 个城市，花费最小。
- 电路板布线，连接所有引脚，总长度最短。
- 在图中聚类，最小生成树的某些边作为簇间边界。
二、Kruskal 算法——选边法
2.1 核心思想
贪心策略：将所有边按权重从小到大排序，依次选择那些不会形成环的边，直到选中 V-1 条边为止。
“不形成环”的检测依赖并查集（Union-Find）数据结构。
2.2 算法步骤
- 对图中所有边按权重升序排序。
- 初始化并查集，每个顶点自成一个集合。
- 遍历排序后的边
(u, v, w)：- 如果
u和v不在同一个集合中（即连接它们不会形成环），则选择这条边，并将u和v合并。 - 否则跳过。
- 如果
- 重复步骤 3，直到已选边数 = V-1。
2.3 图解示例
假设有 4 个顶点：A、B、C、D，边的权重：
- A-B: 1
- B-C: 3
- A-D: 4
- C-D: 2
- B-D: 5
排序后：A-B(1), C-D(2), B-C(3), A-D(4), B-D(5)。
- 选 A-B（集合 {A,B}）
- 选 C-D（集合 {C,D}）
- 选 B-C（集合 {A,B,C,D}）边数=3，结束。
MST 总权重 = 1+2+3=6。
2.4 复杂度分析
| 操作 | 复杂度 |
|---|---|
| 边排序 | O(E log E) |
| 并查集合并/查找 | 近乎 O(1)（路径压缩+按秩合并） |
| 总复杂度 | O(E log E)，通常是 O(E log V) |
2.5 代码实现（Python）
classUnionFind:def__init__(self,n):self.parent=list(range(n))self.rank=[0]*ndeffind(self,x):ifself.parent[x]!=x:self.parent[x]=self.find(self.parent[x])returnself.parent[x]defunion(self,x,y):rx,ry=self.find(x),self.find(y)ifrx==ry:returnFalseifself.rank[rx]<self.rank[ry]:self.parent[rx]=ryelifself.rank[rx]>self.rank[ry]:self.parent[ry]=rxelse:self.parent[ry]=rx self.rank[rx]+=1returnTruedefkruskal(vertices,edges):""" vertices: 顶点数量 edges: [(u, v, weight), ...] u,v 为顶点索引 """edges.sort(key=lambdae:e[2])uf=UnionFind(vertices)mst=[]total_weight=0foru,v,winedges:ifuf.union(u,v):mst.append((u,v,w))total_weight+=wiflen(mst)==vertices-1:breakreturnmst,total_weight三、Prim 算法——加点法
3.1 核心思想
贪心策略：从任意一个顶点开始，每次选择连接已选集合与未选集合权重最小的边，将新顶点加入已选集合，直到所有顶点都被覆盖。
这听起来很像 Dijkstra 最短路径算法，但 Prim 维护的是到当前树的最小边权，而非源点的距离。
3.2 算法步骤
- 初始化：随机选一个起点
s，将其加入集合S。 - 维护一个数组
min_edge或优先队列，记录每个未选顶点到集合S的最小边权。 - 每次从优先队列中取出距离最小的顶点
v（即最小权重边对应的未选顶点），将该边加入 MST，并标记v加入S。 - 更新
v的邻居到集合S的边权（若比当前记录小）。 - 重复直到所有顶点都已加入。
3.3 图解示例
使用上例的图，从 A 开始：
- S={A}，邻接边：A-B(1), A-D(4)，选最小 A-B(1)，加入 B。
- S={A,B}，新增长边：B-C(3), B-D(5)，加上原来的 A-D(4)，最小的是 B-C(3)？等一等，C-D(2) 也连接到了 C 和 D，但 C 和 D 都不在 S 中，注意需要保证边一端在 S，一端不在。此时所有跨集合边：A-D(4), B-C(3), B-D(5), 还有 C-D? C 和 D 都不在 S，不跨集合。最小是 B-C(3)，加入 C。
- S={A,B,C}，跨集合边：A-D(4), B-D(5), C-D(2)，最小 C-D(2)，加入 D。
边：A-B(1), B-C(3), C-D(2)，权重和=6。
3.4 复杂度分析
| 实现方式 | 时间复杂度 |
|---|---|
| 邻接矩阵 + 遍历 | O(V²) |
| 二叉堆（优先队列）+ 邻接表 | O((V+E) log V) |
| 斐波那契堆 | O(E + V log V)（理论最优） |
实际竞赛和工程中，常用堆优化版本。
3.5 代码实现（二叉堆版本）
importheapqdefprim(adj,start=0):""" adj: 邻接表，adj[u] = [(v, weight), ...] start: 起始顶点 返回: mst_edges, total_weight """n=len(adj)visited=[False]*n# 优先队列存储 (weight, u, v) 其中 u 为已选集合中的顶点，v 为未选顶点pq=[]# 初始化：从 start 出发的所有边入队forv,winadj[start]:heapq.heappush(pq,(w,start,v))visited[start]=Truemst=[]total_weight=0whilepqandlen(mst)<n-1:w,u,v=heapq.heappop(pq)ifvisited[v]:continuevisited[v]=Truemst.append((u,v,w))total_weight+=w# 将 v 的邻边中未访问的顶点加入优先队列fornxt,nwinadj[v]:ifnotvisited[nxt]:heapq.heappush(pq,(nw,v,nxt))returnmst,total_weight四、Kruskal vs Prim 详细对比
| 维度 | Kruskal | Prim |
|---|---|---|
| 策略 | 按边权全局排序，选边 | 从一点出发，逐渐扩展 |
| 数据结构 | 并查集 | 优先队列（堆） |
| 时间复杂度 | O(E log E) | O((V+E) log V)（堆） |
| 适用图 | 稀疏图（E 远小于 V²）效果更好 | 稠密图（E 接近 V²）用邻接矩阵 O(V²) 更快 |
| 空间复杂度 | O(V+E) | O(V+E) |
| 对连通性要求 | 整体图必须连通 | 整体图必须连通 |
| 实现难度 | 较简单（并查集模板） | 稍复杂（优先队列维护） |
| 是否易于处理不连通图 | 可生成森林（最小生成森林） | 只对连通分量有效 |
| 典型应用 | 稀疏图，边数量可控，如道路规划 | 稠密图，或需要实时扩展的场景 |
实际选择建议：
- 如果图是稀疏图（E ≈ V），Kruskal 通常更简单高效。
- 如果图是稠密图（E ≈ V²），使用 Prim 的邻接矩阵版本（O(V²)）优于 Kruskal 的 O(E log V)。
- 如果图的边需要动态添加且需要维护 MST，Prim 更容易增量更新。
五、扩展：最小生成树的唯一性判断
如果图中所有边的权重互不相同，则最小生成树唯一。否则，可能存在多棵 MST。
判断方法：
- 应用 Kruskal，在边权相等时，尝试以不同顺序选择，看能否得到不同树。
- 检查：对于某条权重为 w 的边 e，如果存在一个割，使得 e 是该割中唯一的最小边，则 e 必在某个 MST 中；如果割中有多个等重的最小边，那么 MST 可能不唯一。
六、实际应用场景对比
| 场景 | 推荐算法 | 理由 |
|---|---|---|
| 城市间铺设电缆（几百个点，边数较少） | Kruskal | 边数可控，排序易 |
| 电路板布线（密集引脚） | Prim（矩阵版） | 稠密图，矩阵遍历简单 |
| 实时网络拓扑（动态添加节点） | Prim（堆） | 增量扩展方便 |
| 处理不连通图（多个孤岛） | Kruskal | 直接得到最小生成森林 |
| 大数据图（边超千万） | Kruskal（外部排序+并查集） | 内存友好 |
七、常见面试问题
Q1：Prim 算法和 Dijkstra 算法的区别？
- Dijkstra 求的是单源最短路径，累加的是从源点到当前点的路径长度。
- Prim 求的是 MST，累加的是当前树到新顶点的直接边权。
Q2：如果图不连通，Kruskal 和 Prim 会怎样？
- Kruskal 会输出最小生成森林（每个连通分量的 MST 合并）。
- Prim 只从起点开始，只能生成该连通分量内的 MST。
Q3：MST 是否可能含有图中最长的边？
- 不可能。MST 总是避免使用最长边，除非在环中其他边都更长（不可能，因为环中最长边可以被替换）。具体可用“回路性质”证明。
八、总结
- Kruskal 算法：全局选边，并查集防环。适合稀疏图。
- Prim 算法：局部扩展，优先队列取最小跨边。适合稠密图。
- 两者都是贪心算法，且都能保证全局最优解（贪心选择性质）。
- 掌握它们，你就掌握了最小生成树的全部基础。
思考题：如果图中存在负权边，Kruskal 和 Prim 还能正确工作吗？为什么？
（提示：最小生成树定义在无向图上，负权边不会导致环形成更小的树，算法依然正确，但一般不考虑负权，因为权值可以是负的，不影响贪心选择）。
如果觉得有帮助，欢迎点赞、收藏、转发～
本文首发于 CSDN，未经授权禁止转载。
