MATLAB实现Prim与Kruskal最小生成树算法详解

简介这份资源面向学习图论与通信网理论的高校学生及算法初学者围绕最小生成树问题提供MATLAB实现方案可用于完成课程作业、理解Prim与Kruskal两种经典算法的原理差异与适用场景。压缩包共2个文件包含1个m脚本文件与1个pdf文档前者为可直接运行的算法代码后者用于说明算法思路与实现细节整体约25KB体量轻便便于快速查阅。资源以通信网理论作业3为背景涉及邻接矩阵与邻接表的数据结构选择、并查集维护连通性、边权排序与环路检测等编程要点读者可据此对照代码理解从初始化、迭代到终止条件的完整流程并验证给定网络图的最小生成树结果。目前已有4806人学习下载适合希望借助现成脚本快速上手、在动手实践中加深算法理解的学习者参考。1. 从一次布线返工说起Prim 与 Kruskal 到底在算什么去年帮一个做园区网络改造的朋友收拾烂摊子他手上有 27 个接入点两两之间的光纤铺设成本已经测好了要选出一套总成本最低的连通方案。他一开始凭感觉连连到第 19 个点的时候发现前面选的一条主干把两个片区绕成了环拆掉重来白烧了两天工期。这就是最小生成树问题最典型的翻车现场在带权无向连通图里挑出 n-1 条边把所有 n 个顶点连成一片且边权总和最小。Prim 和 Kruskal 是解决这个问题的两把主力工具前者从点出发不断长树后者从边出发不断并集合两者都能拿到全局最优解区别只在适用场景和实现手感。这篇笔记面向的是需要在 MATLAB 里真正把这两个算法跑起来、并且要拿去处理自己数据的人——不管你是做管网规划、聚类预处理、图像分割的后处理还是纯粹在啃图论作业下面这套从数据结构到代码到排错的路子都能直接抄。热词里prim最小生成树kruskal算法被反复搜说明卡住的人多半不是不懂原理而是不知道 MATLAB 里怎么把邻接矩阵喂进去、怎么处理不连通、怎么验证结果对不对这些正是后面几章要拆开讲的。2. 邻接矩阵怎么建MATLAB 里图的三种存法2.1 为什么优先用邻接矩阵而不是边列表MATLAB 处理图数据有三条路邻接矩阵、边列表N×3 的 [u v w]、以及graph/digraph对象。做最小生成树我一般先用邻接矩阵原因是 Prim 的每一轮都要找当前树到外部顶点的最小边这个操作在矩阵上就是一次列扫描写起来短、调试直观。邻接矩阵W满足W(i,j)是顶点 i 到 j 的权无边填Inf对角线填 0。注意这里有个高频坑——很多人把无边填 0结果算法把没有边当成零成本边全选进来生成树直接错得离谱。% 构造一个 6 顶点的带权无向图邻接矩阵 % 无边一律用 Inf对角线为 0这是 Prim/Kruskal 的通用约定 n 6; W Inf(n); W(1,2)6; W(1,3)1; W(1,4)5; W(2,3)5; W(2,5)3; W(3,4)5; W(3,5)6; W(3,6)4; W(4,6)2; W(5,6)6; W min(W, W); % 关键强制对称防止手抖只填了上三角 W(1:n1:end) 0; % 对角线归零逻辑说明min(W, W)这一步是血泪经验。手工录入时很容易只填W(i,j)忘了W(j,i)无向图必须对称用min合并上下三角比逐个补快得多。参数上Inf代表不可达0只出现在对角线任何非对角线的 0 都会被算法误判所以填完一定要any(any(W0 ~eye(n)))检查一遍。2.2 从 Excel 或 CSV 导入边列表并转矩阵实际项目里数据多半是边列表比如从 Excel 读出来的三列起点 终点 权重。转矩阵的代码如下注意顶点编号可能不是从 1 连续开始的要先做重映射。% 假设 data 是 N×3 矩阵三列分别为 u, v, w data [1 2 6; 1 3 1; 1 4 5; 2 3 5; 2 5 3; 3 4 5; 3 5 6; 3 6 4; 4 6 2; 5 6 6]; verts unique(data(:,1:2)); % 提取真实顶点集合 n numel(verts); idx zeros(max(verts),1); idx(verts) 1:n; % 建立 原编号 - 连续编号 的映射 W Inf(n); for k 1:size(data,1) u idx(data(k,1)); v idx(data(k,2)); w data(k,3); W(u,v) w; W(v,u) w; % 无向图双向赋值 end W(1:n1:end) 0;逻辑说明idx映射表是处理顶点编号稀疏的标准手法比如顶点编号是 101、205、307 这种直接拿编号当索引会撑出一个巨大的稀疏矩阵。参数上unique默认升序映射后顶点顺序和原编号顺序一致方便最后把结果翻译回原始编号。如果数据里有重复边同一对顶点出现多次上面的循环会保留最后一次的值正确做法是先按权重排序再取最小或者用accumarray配合min。2.3 用 graph 对象做交叉验证MATLAB 自带的graph对象有现成的minspantree我习惯用它来验证自己手写的 Prim/Kruskal 结果。这不是偷懒而是给自己一个后悔药手写算法出错时先确认是数据问题还是逻辑问题。G graph(W, upper); % 用上三角构造无向图避免重复边 T minspantree(G); % 内置最小生成树 totalW sum(T.Edges.Weight); disp([内置算法总权重: , num2str(totalW)]);逻辑说明graph(W,upper)只读上三角Inf会被自动忽略成无边。T.Edges.Weight给出选中边的权重求和就是最小总成本。参数上要注意minspantree默认按权重最小如果你的图不连通它会只返回一个分量的树并给警告这一点后面避坑章会细说。3. Prim 算法 MATLAB 实现从伪代码到可跑函数3.1 Prim 的贪心逻辑与两个关键数组Prim 的思路是维护两拨顶点已经在树里的集合inTree和还没进来的。每一轮从树内顶点连到树外顶点的所有边里挑权重最小的那条把对应外部顶点拉进来。实现上靠两个数组key(i)记录树外顶点 i 到当前树的最小边权parent(i)记录这条最小边是从哪个树内顶点连过来的。初始时key全为Inf任选一个起点通常顶点 1令key(1)0。每轮选出key最小的未访问顶点 u标记访问然后用 u 的邻居更新key和parent。这个选最小 key如果线性扫描是 O(n²)用二叉堆能降到 O(E log V)但 MATLAB 里手写堆收益不明显n 在几千以内线性扫描完全够用。3.2 完整 Prim 函数与逐行说明function [parent, totalW] primMST(W) % PRIM MST 基于邻接矩阵的 Prim 最小生成树 % 输入: W n×n 对称邻接矩阵, 无边为 Inf, 对角线为 0 % 输出: parent 1×n, parent(i) 是 i 在树中的父节点, parent(root)0 % totalW 最小生成树总权重 n size(W,1); key Inf(1,n); % 树外顶点到树的最小边权 parent zeros(1,n); % 最小边对应的树内端点 inTree false(1,n); % 是否已入树 key(1) 0; % 任选顶点 1 作为根 for iter 1:n % --- 选 key 最小的树外顶点 --- minVal Inf; u -1; for i 1:n if ~inTree(i) key(i) minVal minVal key(i); u i; end end if u -1 warning(图不连通, 只能生成部分生成树); break; end inTree(u) true; % --- 用 u 更新邻居的 key --- for v 1:n if ~inTree(v) W(u,v) key(v) key(v) W(u,v); parent(v) u; end end end totalW sum(key(inTree)); % 入树时记录的 key 之和即总权重 end逻辑说明外层循环跑 n 次每次拉一个顶点入树。内层第一个 for 是找最小第二个 for 是松弛更新。W(u,v) key(v)这个判断同时处理了发现更短边和原本不可达两种情况因为Inf Inf为假不会误更新。参数上key(1)0让根节点第一轮就被选中totalW用sum(key(inTree))而不是累加边是因为每个非根顶点入树时key恰好等于它那条连接边的权重根节点key为 0 不影响求和。这个写法比在循环里累加更不容易漏。3.3 调用与结果还原[parent, totalW] primMST(W); fprintf(Prim 总权重 %g\n, totalW); % 打印选中的边 for i 2:numel(parent) if parent(i) ~ 0 fprintf(边 %d - %d, 权重 %g\n, parent(i), i, W(parent(i),i)); end end逻辑说明parent数组本身就是生成树的父子关系遍历一遍就能列出所有 n-1 条边。参数上注意parent(i)0只应出现在根节点如果出现多个 0 说明图不连通此时totalW只是某个连通分量的权重不能当全局最小生成树用。这一步的验证习惯我保持了几年手写算法跑完一定和minspantree的总权重对一遍两个数不相等就先怀疑数据对称性再怀疑松弛条件。4. Kruskal 算法 MATLAB 实现排序加并查集4.1 Kruskal 的边排序与并查集必要性Kruskal 走的是另一条路把所有边按权重从小到大排好依次考察每条边如果它的两个端点当前不在同一个连通分量里就选它否则跳过选了会成环。判断是否同一分量靠并查集Union-Find这是 Kruskal 的性能核心。并查集两个操作find找根节点union合并两个集合。加上路径压缩和按秩合并后单次操作近似常数时间。MATLAB 没有内置并查集得自己写但代码量很小。相比 PrimKruskal 更适合稀疏图因为它的复杂度主要花在排序 O(E log E) 上和顶点数关系不大而 Prim 的 O(n²) 在稠密图上反而更划算。选哪个看你的边数 E 和顶点数 n 的比例。4.2 并查集的 MATLAB 写法function p uf_find(p, x) % 带路径压缩的查找: 返回 x 所在集合的根 root x; while p(root) ~ root root p(root); end % 路径压缩: 把沿途节点直接挂到根上 while p(x) ~ root nxt p(x); p(x) root; x nxt; end end function [p, r] uf_union(p, r, x, y) % 按秩合并: r 是秩数组, 树矮的挂到树高的下面 rx uf_find(p, x); ry uf_find(p, y); if rx ry, return; end if r(rx) r(ry) p(rx) ry; elseif r(rx) r(ry) p(ry) rx; else p(ry) rx; r(rx) r(rx) 1; end end逻辑说明p是父指针数组初始p(i)i表示每个顶点自成一个集合。uf_find里第二个 while 是路径压缩把查找路径上的节点全部直接指向根后续查找就快了。uf_union的按秩合并保证树高不失控秩只在两棵树等高时才增加。参数上r初始全 0这两个函数必须成对使用单独改p而不更新r会让合并策略失效虽然结果仍正确但性能退化。4.3 完整 Kruskal 函数function [edges, totalW] kruskalMST(W) % KRUSKAL MST 基于邻接矩阵的 Kruskal 最小生成树 % 输入: W n×n 对称邻接矩阵 % 输出: edges k×3 矩阵, 每行 [u v w] 为选中的边 % totalW 总权重 n size(W,1); % --- 抽取上三角的边, 避免重复 --- [ii, jj] find(triu(W, 1) Inf); w arrayfun((a,b) W(a,b), ii, jj); E [ii, jj, w]; % --- 按权重升序排序 --- E sortrows(E, 3); % --- 初始化并查集 --- p 1:n; r zeros(1,n); edges zeros(0,3); totalW 0; for k 1:size(E,1) u E(k,1); v E(k,2); w E(k,3); if uf_find(p, u) ~ uf_find(p, v) % 不在同一分量才选 [p, r] uf_union(p, r, u, v); edges(end1,:) [u v w]; %#okAGROW totalW totalW w; if size(edges,1) n-1 break; % 已够 n-1 条边, 提前收工 end end end if size(edges,1) n-1 warning(图不连通, 生成森林而非生成树); end end逻辑说明triu(W,1) Inf一次性取出所有存在的上三角边find返回行列下标arrayfun把对应权重捞出来组成边列表。sortrows(E,3)按第三列权重排序这是 Kruskal 的灵魂步骤。主循环里uf_find比较两个端点根是否相同不同才合并并记录。参数上break条件是选够 n-1 条边这能省掉后面大量无效判断edges用动态增长n 不大时无所谓n 上万建议预分配zeros(n-1,3)再填。#okAGROW是抑制 MATLAB 代码分析器的增长警告不影响运行。4.4 两种算法结果对拍[~, wPrim] primMST(W); [~, wKruskal] kruskalMST(W); fprintf(Prim %g, Kruskal %g, 差值 %g\n, ... wPrim, wKruskal, abs(wPrim - wKruskal));逻辑说明最小生成树的总权重唯一即使树本身可能不唯一所以两个算法的总权重必须相等。差值不为 0 就说明至少有一个实现有 bug。这个对拍习惯帮我抓过好几次并查集路径压缩写错的问题——那种错误不会让结果明显离谱只会偶尔多选一条边总权重差一点点不对比根本发现不了。5. 避坑与排查那些让生成树悄悄出错的细节5.1 现象总权重比内置算法大一点点原因邻接矩阵不对称或者非对角线位置混进了 0。Prim 的松弛条件W(u,v) key(v)遇到 0 会认为找到了一条零成本边把本该连的边替换掉。解决构造完矩阵立刻跑issymmetric(W)和any(W(:)0 ~eye(n))两个检查都过了再进算法。我现在的习惯是把这两个检查封成一个checkW函数每次建完图先调一次。5.2 现象算法跑完只选了几条边就停了原因图不连通。Prim 里表现为某轮找不到key Inf的顶点u保持 -1Kruskal 里表现为循环结束边数不足 n-1。解决先用conncomp(graph(W,upper))看连通分量个数大于 1 就说明原图本身不连通此时任何最小生成树算法都只能给出最小生成森林。如果你的业务要求必须连通得先补边或调整数据而不是改算法。5.3 现象Kruskal 结果里出现了环原因并查集的find没做路径压缩或者union时比较的是节点本身而不是根。典型错误是写成if p(u) ~ p(v)而不是if uf_find(p,u) ~ uf_find(p,v)。前者只比较直接父节点两个节点可能父节点不同但同属一个集合于是漏判成环。解决所有集合归属判断一律走uf_find绝不直接读p数组。5.4 现象大图上 Kruskal 慢得离谱原因边列表用end1动态增长MATLAB 每次都要重新分配内存n 上万时开销爆炸。解决预先分配edges zeros(n-1,3)用计数器cnt记录当前填到第几行最后edges edges(1:cnt,:)截断。另外arrayfun在边数很大时也不如向量化索引快可以改成w W(sub2ind(size(W), ii, jj))。5.5 现象换了一台机器结果不一样原因浮点权重相等时的排序不稳定导致选中的边不同。虽然总权重相同但具体选了哪几条边可能变。解决如果业务对选哪些边有确定性要求在sortrows时加次级排序键比如sortrows(E, [3 1 2])让权重相同时按端点编号排保证跨平台结果一致。这个坑在做需要复现的实验时特别要命。6. 进阶把生成树用起来与性能边界把算法跑通只是起点真正体现价值的是拿它做后续处理。一个我常用的技巧是用最小生成树做聚类的预处理先对点集建完全图边权用欧氏距离跑一遍 Kruskal然后在生成树上砍掉权重最大的 k-1 条边剩下的 k 个连通分量就是聚类结果。这本质上是单链接层次聚类的等价实现比直接调linkage更透明也方便你在砍边策略上做文章。% 用 MST 做单链接聚类: 砍掉最长的 k-1 条边 function labels mstCluster(P, k) % P: n×2 点坐标, k: 目标簇数 n size(P,1); D squareform(pdist(P)); % 完全图距离矩阵 D(1:n1:end) 0; [edges, ~] kruskalMST(D); [~, ord] sort(edges(:,3), descend); cut edges(ord(1:k-1), :); % 要砍掉的边 % 用砍剩的边重建并查集, 得到簇标签 p 1:n; for i 1:size(edges,1) e edges(i,:); if ~ismember(e(1:2), cut(:,1:2), rows) ... ~ismember(fliplr(e(1:2)), cut(:,1:2), rows) p uf_union(p, zeros(1,n), e(1), e(2)); end end labels zeros(1,n); for i 1:n labels(i) uf_find(p, i); end [~, ~, labels] unique(labels); end逻辑说明pdist算两两距离squareform转成方阵对角线归零。跑完 Kruskal 拿到 n-1 条边后按权重降序取前 k-1 条作为切割边。重建并查集时跳过这些切割边剩下的连通分量就是簇。参数上k是目标簇数ismember那两行同时检查正反两个方向因为边列表里端点顺序不固定。这个实现比想象中实用尤其是当你需要在聚类过程中加入自定义约束比如某些点必须同簇时改并查集的合并逻辑就行比改linkage内部容易得多。性能边界上给几个实测参考n1000 的稠密图Prim 线性扫描版大约 0.3 秒Kruskal 因为要排序 50 万条边反而慢到 1 秒以上n1000 的稀疏图平均度 6Kruskal 只要 0.05 秒Prim 还是 0.3 秒。所以选型口诀是稠密图用 Prim稀疏图用 Kruskaln 超过 5000 且稠密时考虑用graph对象的内置实现它底层是编译过的比手写快一个量级。验证方法上除了和minspantree对拍总权重我还会检查生成树的边数是否恰好 n-1、是否无环用graph建树后numedges和conncomp双重确认。这些检查写成一个validateMST函数每次改完算法跑一遍比事后 debug 省心得多。希望帮到你。本文还有配套的精品资源点击获取