最小生成树的 Kruskal 与 Prim 算法：从连通到最优，一篇文章彻底掌握

如何用最少的成本把 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: 1B-C: 3A-D: 4C-D: 2B-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 总权重 1236。2.4 复杂度分析操作复杂度边排序O(E log E)并查集合并/查找近乎 O(1)路径压缩按秩合并总复杂度O(E log E)通常是 O(E log V)2.5 代码实现PythonclassUnionFind:def__init__(self,n):self.parentlist(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,ryself.find(x),self.find(y)ifrxry: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(keylambdae:e[2])ufUnionFind(vertices)mst[]total_weight0foru,v,winedges:ifuf.union(u,v):mst.append((u,v,w))total_weightwiflen(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((VE) log V)斐波那契堆O(E V log V)理论最优实际竞赛和工程中常用堆优化版本。3.5 代码实现二叉堆版本importheapqdefprim(adj,start0): adj: 邻接表adj[u] [(v, weight), ...] start: 起始顶点 返回: mst_edges, total_weight nlen(adj)visited[False]*n# 优先队列存储 (weight, u, v) 其中 u 为已选集合中的顶点v 为未选顶点pq[]# 初始化从 start 出发的所有边入队forv,winadj[start]:heapq.heappush(pq,(w,start,v))visited[start]Truemst[]total_weight0whilepqandlen(mst)n-1:w,u,vheapq.heappop(pq)ifvisited[v]:continuevisited[v]Truemst.append((u,v,w))total_weightw# 将 v 的邻边中未访问的顶点加入优先队列fornxt,nwinadj[v]:ifnotvisited[nxt]:heapq.heappush(pq,(nw,v,nxt))returnmst,total_weight四、Kruskal vs Prim 详细对比维度KruskalPrim策略按边权全局排序选边从一点出发逐渐扩展数据结构并查集优先队列堆时间复杂度O(E log E)O((VE) log V)堆适用图稀疏图E 远小于 V²效果更好稠密图E 接近 V²用邻接矩阵 O(V²) 更快空间复杂度O(VE)O(VE)对连通性要求整体图必须连通整体图必须连通实现难度较简单并查集模板稍复杂优先队列维护是否易于处理不连通图可生成森林最小生成森林只对连通分量有效典型应用稀疏图边数量可控如道路规划稠密图或需要实时扩展的场景实际选择建议如果图是稀疏图E ≈ VKruskal 通常更简单高效。如果图是稠密图E ≈ V²使用 Prim 的邻接矩阵版本O(V²)优于 Kruskal 的 O(E log V)。如果图的边需要动态添加且需要维护 MSTPrim 更容易增量更新。五、扩展最小生成树的唯一性判断如果图中所有边的权重互不相同则最小生成树唯一。否则可能存在多棵 MST。判断方法应用 Kruskal在边权相等时尝试以不同顺序选择看能否得到不同树。检查对于某条权重为 w 的边 e如果存在一个割使得 e 是该割中唯一的最小边则 e 必在某个 MST 中如果割中有多个等重的最小边那么 MST 可能不唯一。六、实际应用场景对比场景推荐算法理由城市间铺设电缆几百个点边数较少Kruskal边数可控排序易电路板布线密集引脚Prim矩阵版稠密图矩阵遍历简单实时网络拓扑动态添加节点Prim堆增量扩展方便处理不连通图多个孤岛Kruskal直接得到最小生成森林大数据图边超千万Kruskal外部排序并查集内存友好七、常见面试问题Q1Prim 算法和 Dijkstra 算法的区别Dijkstra 求的是单源最短路径累加的是从源点到当前点的路径长度。Prim 求的是 MST累加的是当前树到新顶点的直接边权。Q2如果图不连通Kruskal 和 Prim 会怎样Kruskal 会输出最小生成森林每个连通分量的 MST 合并。Prim 只从起点开始只能生成该连通分量内的 MST。Q3MST 是否可能含有图中最长的边不可能。MST 总是避免使用最长边除非在环中其他边都更长不可能因为环中最长边可以被替换。具体可用“回路性质”证明。八、总结Kruskal 算法全局选边并查集防环。适合稀疏图。Prim 算法局部扩展优先队列取最小跨边。适合稠密图。两者都是贪心算法且都能保证全局最优解贪心选择性质。掌握它们你就掌握了最小生成树的全部基础。思考题如果图中存在负权边Kruskal 和 Prim 还能正确工作吗为什么提示最小生成树定义在无向图上负权边不会导致环形成更小的树算法依然正确但一般不考虑负权因为权值可以是负的不影响贪心选择。如果觉得有帮助欢迎点赞、收藏、转发本文首发于 CSDN未经授权禁止转载。