简介面向图论学习与网络优化实践的MATLAB版克鲁斯卡尔算法实现聚焦加权无向图最小生成树的构建与验证。压缩包共4个文件均为m函数文件整体约2KB轻量易读可直接在MATLAB中调用调试。已有409人学习适合课程设计、算法练习及小规模图数据实验参考。内容围绕边权升序排序、并查集判环与生成树合并展开包含主算法入口及连通性判断、环路检测等辅助函数可将邻接矩阵输入转化为最小生成树结果。读者可理解贪心选择与并查集的配合方式掌握Find/Union操作、边集提取与排序实现并借助连通性检查验证结果是否覆盖全部顶点。代码结构简洁便于替换数据、对比不同图规模下的运行表现也可作为网络设计与最优化问题求解的实验起点。1. 从一张布线图说起克鲁斯卡尔算法在 MATLAB 里的真实用武之地去年帮某实验室做机位布线成本估算十几个候选点位两两之间都能走线要在保证全网连通的前提下把线缆总长度压到最低。这种题看着像运筹学作业真落到 MATLAB 里最省事的做法不是把 Prim 和克鲁斯卡尔都撸一遍而是先把克鲁斯卡尔算法跑通——它只要一张边表加一个并查集几十行就能出结果还方便后面往上加约束。这份 MATLAB 克鲁斯卡尔算法代码包干的就是这件事把节点坐标或距离矩阵丢进去输出最小生成树的边集和总权重顺手把树画回原图上。它适合三类人课程设计要交最小生成树作业的学生、做网络布线或路径规划仿真需要快速出数的工程师、以及把 MATLAB 当算法验证平台、后面还要改算法的开发者。整套代码是纯 .m 文件不依赖专门的图论工具箱读得懂也改得动。2. 工程骨架与技术选型目录分层、边表结构和并查集的取舍拿到一份 MATLAB 算法包第一步不是急着 run是先看它怎么切文件。切得粗主函数几百行改一个地方要通读全文切得细一堆只被调用一次的小函数跳转跳得人烦。这份代码的切法算是中间路线值得拿出来说。2.1 目录怎么分三层结构比单文件好改按照常见做法仓库会分成主函数、并查集辅助函数、示例脚本、可视化脚本四个层次目录大致长这样kruskal-matlab/ ├── kruskal_mst.m % 主函数输入校验 边表构建 排序 主循环 ├── uf_find.m % 并查集查找带路径压缩 ├── uf_union.m % 并查集合并按秩合并 ├── demo_city_grid.m % 示例一二维坐标点建完全图 ├── demo_sparse_graph.m % 示例二已有边表稀疏图场景 ├── plot_mst.m % 可视化底图灰线 生成树红线高亮 └── verify_against_ref.m % 交叉验证与 graph/minspantree 对答案为什么不干脆写成一个巨型 .m 文件MATLAB 从 R2016b 开始支持脚本里定义局部函数单文件确实能跑但局部函数对外不可见verify_against_ref.m就拿不到uf_find单独做单元测试。把并查集拆出来以后你可以脱离整张图只造几个节点单独验证uf_find的路径压缩有没有写错这在排查「结果偶尔对偶尔错」这类玄学问题时特别省时间。另一条经验是demo_*.m不要写成函数写成脚本。脚本的工作区变量会留在 base workspace跑完之后X、T、W都还在可以直接在命令行里接着plot、disp、切片检查。如果写成function demo_city_grid()跑完变量全回收想看中间结果还得加disp来回改。2.2 边表与邻接矩阵两个都要但以边表为主克鲁斯卡尔的核心动作是「按权重从小到大挑边能加就加」所以算法的天然数据结构是边表而不是邻接矩阵。但 MATLAB 用户手上最常见的数据形式恰恰是邻接矩阵或坐标矩阵所以代码里必须有一次「矩阵 → 边表」的转换。结构空间适合的图在算法里的角色n×n 邻接矩阵WmatO(n²)稠密图、坐标两两可达输入形式转成边表后基本不再用k×3 边表[u v w]O(k)稀疏图、只给部分边排序和主循环的工作结构parent/rank数组O(n)无所谓稀疏稠密并查集状态只跟节点数有关选型的实际影响体现在 n 的规模上。n50 时邻接矩阵才 2500 个元素怎么存都无所谓n5000 时邻接矩阵是 2500 万个数光find一遍就吃掉几百 MB而真实路网、通信网这类图边数往往只有节点的几倍边表能把内存压下去两个数量级。所以比较稳的写法是对外接口收邻接矩阵用户方便对内一律转边表算法高效并额外提供一个直接吃边表的入口给稀疏图场景用。还有一点要注意转换的时候只取上三角[ii, jj] find(triu(Wmat, 1)); % triu(...,1) 只保留主对角线以上如果整张矩阵扫无向图的每条边会算两次边数翻倍。边数翻倍本身不致命但后面排序多了近一倍元素主循环也多跑一轮属于白白浪费更麻烦的是输出结果里可能出现(3,7)和(7,3)同时被打印出来看起来像算法出了 bug。2.3 并查集为什么不能省每次做连通性检查会怎样新手最容易写出的版本是每挑一条边就用 BFS 或者连通分量矩阵判断两个端点是不是已经连通。n 个点、k 条边每判断一次要 O(nk)总体复杂度 O(k·(nk))完全图下 kn²直接退化成 O(n³) 以上。n200 的完全图就要跑上千万次操作MATLAB 这种解释执行环境下会明显感觉到卡。并查集把这一步压到近似 O(α(n))α 是阿克曼函数的反函数n 在现实规模内几乎不超过 4。代价是多维护两个长度 n 的数组几乎可以忽略。所以这不是「优化技巧」而是这个算法的标准配置——没有并查集的克鲁斯卡尔只能叫「按边排序的贪心尝试」。这里有个 MATLAB 特有的坑必须提前说清楚MATLAB 函数参数是按值传递函数内部改parent数组调用方的parent一个字节都不会变。所以并查集的find必须写成[root, parent] uf_find(parent, x)把压缩后的数组返回出去。第一次写的人十个里有八个会漏返回值然后发现路径压缩完全没生效跑得比预期慢还找不到原因。2.4 输入输出接口约定先把契约写死接口约定清楚了后面二次开发才不会互相打架。这份代码的约定是参数方向类型说明Wmat入n×n double对称权重矩阵0或Inf表示两点之间无边T出k×3 double选中边表每行[u v w]k ≤ n-1W出double生成树或森林总权重flag出logicaltrue表示图连通false表示只得到最小生成森林用0而不是Inf表示无边是因为 MATLAB 里Inf参与排序会和数值混在一起容易写错判断用0更直观但必须记得先做「0 → 剔除」的过滤否则权重 0 的边会被当成最短边全部塞进树里这就是最典型的翻车场景之一第 5 章展开。3. 核心模块拆解从边表排序到并查集合并的完整链路主函数一共四个动作校验输入、构建边表、升序排序、并查集主循环。除了排序那一行是 MATLAB 自带的其余都得自己写逐段看代码比较实在。3.1 输入校验与边表构建function [T, totalW, flag] kruskal_mst(Wmat) % KRUSKAL_MST 用克鲁斯卡尔算法求无向图的最小生成树 % 输入 Wmat : n x n 对称权重矩阵0 或 Inf 表示两点之间无边 % 输出 T : k x 3 边表 [u v w]k n-1 % totalW: 生成树总权重 % flag : true 表示图连通 n size(Wmat, 1); if size(Wmat, 2) ~ n error(kruskal:notSquare, 权重矩阵必须是方阵); end if ~isequal(Wmat, Wmat) % 无向图必须对称 error(kruskal:notSymmetric, 权重矩阵必须对称); end if any(diag(Wmat) ~ 0) % 不支持自环从对角线入手检查 error(kruskal:selfLoop, 对角线必须为 0); end % 只取上三角避免同一条边被当成两条 valid triu(Wmat ~ 0 isfinite(Wmat), 1); [ii, jj] find(valid); w Wmat(sub2ind([n n], ii, jj)); % 线性索引取值比 arrayfun 快这段代码的逻辑说明triu(Wmat ~ 0 isfinite(Wmat), 1)先把「权重不为 0 且不是 Inf/NaN」的位置标出来再取上三角得到的逻辑矩阵里每个true正好对应一条无向边。sub2ind那一行是把行列下标拼成线性下标一次性从矩阵里取值比for循环或者arrayfun((a,b) Wmat(a,b), ii, jj)快一个量级。参数说明Wmat必须是 n×n 的 double 方阵对角线上如果填了非零值会直接报错——自环在最小生成树里恒为无用边提前拦住比事后调试划算。isequal(Wmat, Wmat)这个检查看起来啰嗦但它拦住的是最麻烦的一类错误有人从 CSV 里读数据只填了下三角上三角是全零跑出来的结果会缺一大半边而算法本身不报错只是结果偏小。加了对称性检查这种数据问题会在入口就暴露。3.2 并查集路径压缩与按秩合并function [root, parent] uf_find(parent, x) % 查找 x 所在树的根顺便做路径压缩 root x; while parent(root) ~ root root parent(root); % 一路向上找根 end % 第二趟把沿途节点全部挂到根上下次查找就是一步到位 while parent(x) ~ root nxt parent(x); parent(x) root; x nxt; end endfunction [parent, rank] uf_union(parent, rank, ra, rb) % 合并两棵树ra、rb 必须是已经找到的根节点 if ra rb return; % 同根合并无意义 end if rank(ra) rank(rb) parent(ra) rb; % 矮树挂到高树下面 elseif rank(ra) rank(rb) parent(rb) ra; else parent(rb) ra; rank(ra) rank(ra) 1; % 同高度才需要抬高秩 end end逻辑说明uf_find用了两趟循环第一趟找根第二趟从原来的x开始往上走把路径上每个节点的父指针直接改成根。写成两趟而不是递归是因为 MATLAB 的递归深度限制和函数调用开销都不友好几千个节点链状结构很容易触发递归上限。nxt这个临时变量不能省先存后改否则parent(x)被覆盖之后就找不到下一跳了。参数说明parent是长度 n 的整数数组初始化为1:n即每个节点自成一棵树rank初始化为全零用来记录树高的上界。uf_union传的是根不是节点这一点必须在注释里写死否则调用方很容易传进未压缩的节点编号导致parent结构被破坏症状是后面find出现死循环——这是排查起来最费劲的一类问题因为循环体看起来完全正常。按秩合并的价值在数据规模大时才显现。只有路径压缩、不做按秩合并单次find的均摊复杂度是 O(log n)两者都做才是 O(α(n))。日常几百个节点的课程作业感觉不出来几万个节点的路网数据就有差距了。3.3 主循环挑边、判环、提前退出% 按权重升序排列order 是原下标 [~, order] sort(w, ascend); parent 1:n; rank zeros(1, n); T zeros(n-1, 3); % 预分配最多 n-1 条边 cnt 0; totalW 0; for k 1:numel(order) e order(k); u ii(e); v jj(e); [ru, parent] uf_find(parent, u); [rv, parent] uf_find(parent, v); if ru rv continue; % 已经连通加了就成环 end [parent, rank] uf_union(parent, rank, ru, rv); cnt cnt 1; T(cnt, :) [u v w(e)]; totalW totalW w(e); if cnt n - 1 break; % 生成树已满后面的边不用看 end end T T(1:cnt, :); flag (cnt n - 1); end逻辑说明外层按权重从小到大遍历边每取一条边先查两个端点是否同根同根说明加上去会成环直接跳过不同根就合并、记账。cnt n - 1时提前break这是克鲁斯卡尔里最容易被忽略但收益最明显的一步——完全图有 n(n-1)/2 条边而生成树只要 n-1 条正常数据下循环跑到很靠前的位置就能结束后面的边根本不用碰。参数说明T用zeros(n-1, 3)预分配再截断比每轮T(end1,:) ...快得多后者每次扩容都要重新分配内存节点数上千时差距明显。flag同时承担两个信息图是否连通以及T是生成树还是生成森林。sort的稳定性值得提一句。权重相等的边排序后谁在前谁在后不影响总权重但会影响最终选出的边集。做作业无所谓做工程就可能出问题两次运行结果边集不一样用户会以为代码有随机性。想固定下来可以在排序时加次级排序键比如按u再按v或者干脆接受这个不确定性在文档里写清楚「等权情况下结果不唯一」——最小生成树本来就不唯一这一点说清楚能省掉很多解释成本。3.4 结果封装与连通性判断返回之前还有一件事值得做把完全孤立、一条边都没有的节点标出来。flag为false时只说明图不连通但用户往往还想知道是哪几个点没连上。if ~flag % 找出最终仍是孤岛或属于其他连通分量的节点供调用方判断 roots zeros(1, n); for i 1:n [roots(i), parent] uf_find(parent, i); end comps unique(roots); fprintf(图不连通共 %d 个连通分量\n, numel(comps)); end这段是辅助输出不带返回值只打印。真实项目里我更习惯把roots作为第四个大可选输出让调用方能拿到分量标签去做后续处理比如分别给每个分量做布线方案。MATLAB 的nargout可以判断调用方要不要实现成本很低。4. 跑起来两种输入格式、函数调用与生成树可视化代码放在当前工作目录下或者addpath加进来就能在命令行直接调用。这一章给两个能直接抄的示例一个稠密一个稀疏覆盖大部分使用场景。4.1 输入一节点坐标现场建完全图% demo_city_grid.m rng(7); % 固定随机种子结果可复现 n 12; X rand(n, 2) * 100; % 12 个候选点位坐标落在 100x100 区域 D zeros(n); for i 1:n for j i1:n D(i, j) norm(X(i,:) - X(j,:)); % 欧氏距离作为布线成本 end end D D D; % 补成对称矩阵主对角线为 0 [T, W, flag] kruskal_mst(D); fprintf(连通%d, 树边数%d, 总权重%.2f\n, flag, size(T,1), W); plot_mst(X, T, D, W);逻辑说明先造坐标再算两两距离得到完全图的邻接矩阵。rng(7)是关键不固定种子的话每次跑出来的点位不同跟别人对不上话讨论「为什么我的总权重是 486」时会很尴尬。norm(X(i,:) - X(j,:))是 MATLAB 里算欧氏距离最直接的方式不需要pdist也就避开了对统计工具箱的依赖。参数说明n就是节点数改大改小都可以但完全图边数是 n(n-1)/2n200 就是将近两万条边排序和主循环会开始有感。100是坐标范围改成实际图纸尺寸即可。4.2 输入二稀疏图只给部分边现实中的图往往不是两两可达比如路网里很多路口之间根本没有直连。这时候邻接矩阵大部分位置都是 0% demo_sparse_graph.m mask triu(rand(n) 0.3, 1); % 30% 的边留下 mask mask | mask; % 对称化保证无向 D2 D .* mask; % 没留下的边权重变 0即「无边」 [T2, W2, flag2] kruskal_mst(D2); if ~flag2 warning(图不连通返回的是最小生成森林); end逻辑说明triu(rand(n) 0.3, 1)生成一个上三角的逻辑掩码mask | mask把它对称化D .* mask完成筛选。这种写法比for循环逐条删边短得多也更好读。参数说明0.3是保留边的概率调小就更容易出现不连通是测试flag分支的好办法。0.3时 12 个节点大概率还连通想稳定复现「不连通」把概率压到 0.15 左右。plot_mst的实现思路很简单先画所有边的灰色细线当底图再把T里的边用红粗线盖上去最后画节点圆圈和编号。function plot_mst(X, T, Wmat, W) figure(Color, w); hold on; box on; n size(Wmat, 1); [ii, jj] find(triu(Wmat ~ 0 isfinite(Wmat), 1)); for k 1:numel(ii) plot(X([ii(k) jj(k)],1), X([ii(k) jj(k)],2), -, Color, [0.82 0.82 0.82]); end for k 1:size(T,1) plot(X(T(k,1:2),1), X(T(k,1:2),2), -, LineWidth, 2, Color, [0.85 0.2 0.2]); end plot(X(:,1), X(:,2), o, MarkerSize, 6, ... MarkerFaceColor, w, MarkerEdgeColor, k); text(X(:,1)0.8, X(:,2)0.8, string(1:n), FontSize, 8); title(sprintf(MST 总权重 %.2f, W)); hold off; end参数说明X是 n×2 的坐标矩阵T是主函数返回的边表Wmat用来画底图。text加了个0.8的偏移避免编号压在节点圆圈上坐标范围不同可以按比例调。4.3 用自带的 minspantree 对答案较新版本的 MATLABR2015b 及以后自带graph对象和minspantree不依赖额外工具箱。它不能替代手写实现因为你要改算法但拿来做交叉验证非常合适G graph(D2); % 0 表示无边符合 graph 的约定 [Tref, Wref] minspantree(G); fprintf(参考解总权重 %.4f自写解 %.4f差 %.2e\n, ... Wref, W2, abs(Wref - W2));逻辑说明graph(D2)把邻接矩阵变成图对象minspantree求最小生成树。两个总权重在浮点误差范围内相等基本可以认为实现正确。参数说明graph的邻接矩阵里0会被当成「无边」这一点和我们的约定刚好一致但如果你的真实数据里存在权重为 0 的合法边这里就会静默丢边两边结果都对不上——第 5 章会专门讲这个。5. 避坑与排查连不通、成环、索引错位这五类翻车现场算法本身只有二十几行出问题的往往在数据准备和边界处理上。下面五条是实际调试里反复出现的按「现象 → 原因 → 解决」写遇到对得上的直接照方抓药。5.1 现象结果里出现了环或者边数超过 n-1现象很直观把T画出来能看到闭合回路或者size(T,1)打印出 15 而 n 只有 10。原因基本只有一个并查集的uf_find没有返回压缩后的parent调用方用的还是旧的数组压缩等于没做但更严重的是如果连uf_union的返回值也漏了parent在函数外完全没被修改每次find都返回节点自己判环逻辑彻底失效。解决办法是把接口检查一遍[ru, parent] uf_find(parent, u);和[parent, rank] uf_union(parent, rank, ru, rv);两处都必须接住返回值。排查时可以在主循环里打印sum(parent ~ 1:n)如果一直是 0说明合并根本没生效问题就定位到并查集了。5.2 现象总权重比手算大而且大得离谱先怀疑0的语义。用0表示「无边」是个方便但危险的约定如果真实数据里存在权重正好为 0 的边Wmat ~ 0这个过滤会把它当成不存在导致某些本该连通的点被判成孤岛最后返回的是森林而不是树总权重自然对不上。解决方式有两种一是数据准备阶段把合法零权边改成一个极小正数比如1e-9视觉上不影响结果二是把约定改成「Inf表示无边」过滤条件改成isfinite(Wmat)代价是所有 0 都要写成Inf再传入。我在项目里一般选第一种改数据比改约定风险小。5.3 现象图不连通时函数不报错返回的 T 少了边这是设计如此不是 bug。克鲁斯卡尔跑到边遍历完如果cnt n-1说明原图本来就不连通只能给出最小生成森林。问题在于很多调用方不看flag直接拿T去做后续计算结果算出一堆孤立点。解决办法是别只依赖返回值在flag false时至少warning一次把连通分量数量打出来。更稳的做法是把分量标签也返回让调用方自己决定是补边、拆分处理还是直接报错退出。这个后悔药提前吃比事后追数据便宜得多。5.4 现象稀疏图上结果正确率忽高忽低概率性出现的错误最难查。常见原因是边表构建时用find(Wmat)而不是find(triu(Wmat, 1))无向边被算了两次。两次本身不影响正确性但如果你在边表之外还维护了一个「已选边」的计数器或者去重逻辑重复边就会让计数错位导致提前break漏掉本该加入的边。另一种情况是手动造边表时节点编号从 0 开始受其他语言习惯影响而 MATLAB 索引从 1 开始parent(0)直接报错或者被当成非法索引静默处理。解决办法是在入口加一句if any([ii; jj] 1), error(...)拦住比在循环里崩掉好定位得多。5.5 现象n 到几百就明显变慢如果n300的完全图要跑好几秒先看三处。一是T(end1,:) ...有没有改成预分配这是最常见的性能黑洞二是uf_find是不是写成了递归MATLAB 的函数调用开销在深链上很难看三是边表构建有没有用arrayfun改用sub2ind一次性取下标能快一个数量级。还有一处容易被忽略sort排的是w但主循环里每次要用order(k)反查ii、jj、w如果w是从矩阵里临时算出来的比如每次循环重算距离开销会翻倍。正确做法是排序前就把w固化成数组循环里只做下标访问。6. 二次开发换算法、加约束和随机对照验证的三个改造方向代码跑通只是起点多数人拿到它是要改的。三个方向最常用。换算法做对比。稠密图场景下 Prim 往往更快因为它是按点扩展不需要对全部边排序。改造位置很集中保留kruskal_mst.m的输入校验和输出封装把中间的排序和主循环换成「维护一个已选点集 一个候选边最小堆」。MATLAB 没有原生堆用sort每次取最小也行n 不大时够用。改完拿同一份D分别喂给两个函数比总权重和运行时间。改造点修改位置注意换 Prim主循环整体替换输出格式保持k×3不变方便对比脚本复用加「必须包含某条边」约束主循环前预先把该边合并进并查集记得把这条边的权重计入总数加「禁止某些边」边表构建后过滤过滤后要重新检查连通性可能直接变成森林支持有向图uf_find换成拓扑排序有向图的最小生成树是另一个问题最小树形图加约束是克鲁斯卡尔最舒服的地方。比如布线场景要求某两个机房之间必须直连做法不是改算法而是在主循环之前先把这条边uf_union掉、计入totalW然后正常跑。禁止某些边同理在valid triu(...)之后加一层掩码就行。这种「预处理 原算法」的模式比改算法体面得多出问题也容易回滚到无约束版本做对照。如果是「每个节点度数不超过 k」这类约束贪心就不保证了得换思路这时候别硬改直接上整数规划更省时间。随机对照验证是我现在的固定动作。手写图算法最容易在边界上翻车靠几个手算例子根本盖不住。我的做法是写一个循环随机生成不同规模、不同稀疏度的图把自写实现和minspantree的结果逐一比对function ok verify_kruskal(trials) % 随机图批量对照自写 kruskal_mst vs MATLAB 自带 minspantree ok true; for t 1:trials n randi([5, 60]); X rand(n, 2) * 100; D zeros(n); for i 1:n for j i1:n D(i,j) norm(X(i,:) - X(j,:)); end end D D D; keep triu(rand(n) 0.4, 1); % 随机稀疏化制造不连通场景 keep keep | keep; D D .* keep; [~, W1, f1] kruskal_mst(D); G graph(D); [~, W2] minspantree(G); if f1 abs(W1 - W2) 1e-8 fprintf(第 %d 轮不一致自写 %.10f参考 %.10f\n, t, W1, W2); ok false; end end end这段的价值在于把「不连通」「单节点」「两条边等权」这些边角情况用随机数自动覆盖掉。跑 200 轮能过基本就稳了过不了把rng固定到出问题那一轮单独复现比盯着代码瞎猜快得多。我踩过最深的一个坑是早期版本为了省事在D .* keep之后又手动把对角线补了一遍非零值结果自环混进边表排序后排在最前面主循环一上来就把每个点自己和并了一次parent结构直接乱掉而算法还不报错——只是结果偏小。那之后我每次改图算法的入口不管多小的例子都强制先跑一遍随机对照再手算一两个小图确认输出格式两关都过了才往下写。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/30 10:29:47 · 阅读 1.2k MATLAB克鲁斯卡尔算法：最小生成树与并查集实现
简介面向图论学习与网络优化实践的MATLAB版克鲁斯卡尔算法实现聚焦加权无向图最小生成树的构建与验证。压缩包共4个文件均为m函数文件整体约2KB轻量易读可直接在MATLAB中调用调试。已有409人学习适合课程设计、算法练习及小规模图数据实验参考。内容围绕边权升序排序、并查集判环与生成树合并展开包含主算法入口及连通性判断、环路检测等辅助函数可将邻接矩阵输入转化为最小生成树结果。读者可理解贪心选择与并查集的配合方式掌握Find/Union操作、边集提取与排序实现并借助连通性检查验证结果是否覆盖全部顶点。代码结构简洁便于替换数据、对比不同图规模下的运行表现也可作为网络设计与最优化问题求解的实验起点。1. 从一张布线图说起克鲁斯卡尔算法在 MATLAB 里的真实用武之地去年帮某实验室做机位布线成本估算十几个候选点位两两之间都能走线要在保证全网连通的前提下把线缆总长度压到最低。这种题看着像运筹学作业真落到 MATLAB 里最省事的做法不是把 Prim 和克鲁斯卡尔都撸一遍而是先把克鲁斯卡尔算法跑通——它只要一张边表加一个并查集几十行就能出结果还方便后面往上加约束。这份 MATLAB 克鲁斯卡尔算法代码包干的就是这件事把节点坐标或距离矩阵丢进去输出最小生成树的边集和总权重顺手把树画回原图上。它适合三类人课程设计要交最小生成树作业的学生、做网络布线或路径规划仿真需要快速出数的工程师、以及把 MATLAB 当算法验证平台、后面还要改算法的开发者。整套代码是纯 .m 文件不依赖专门的图论工具箱读得懂也改得动。2. 工程骨架与技术选型目录分层、边表结构和并查集的取舍拿到一份 MATLAB 算法包第一步不是急着 run是先看它怎么切文件。切得粗主函数几百行改一个地方要通读全文切得细一堆只被调用一次的小函数跳转跳得人烦。这份代码的切法算是中间路线值得拿出来说。2.1 目录怎么分三层结构比单文件好改按照常见做法仓库会分成主函数、并查集辅助函数、示例脚本、可视化脚本四个层次目录大致长这样kruskal-matlab/ ├── kruskal_mst.m % 主函数输入校验 边表构建 排序 主循环 ├── uf_find.m % 并查集查找带路径压缩 ├── uf_union.m % 并查集合并按秩合并 ├── demo_city_grid.m % 示例一二维坐标点建完全图 ├── demo_sparse_graph.m % 示例二已有边表稀疏图场景 ├── plot_mst.m % 可视化底图灰线 生成树红线高亮 └── verify_against_ref.m % 交叉验证与 graph/minspantree 对答案为什么不干脆写成一个巨型 .m 文件MATLAB 从 R2016b 开始支持脚本里定义局部函数单文件确实能跑但局部函数对外不可见verify_against_ref.m就拿不到uf_find单独做单元测试。把并查集拆出来以后你可以脱离整张图只造几个节点单独验证uf_find的路径压缩有没有写错这在排查「结果偶尔对偶尔错」这类玄学问题时特别省时间。另一条经验是demo_*.m不要写成函数写成脚本。脚本的工作区变量会留在 base workspace跑完之后X、T、W都还在可以直接在命令行里接着plot、disp、切片检查。如果写成function demo_city_grid()跑完变量全回收想看中间结果还得加disp来回改。2.2 边表与邻接矩阵两个都要但以边表为主克鲁斯卡尔的核心动作是「按权重从小到大挑边能加就加」所以算法的天然数据结构是边表而不是邻接矩阵。但 MATLAB 用户手上最常见的数据形式恰恰是邻接矩阵或坐标矩阵所以代码里必须有一次「矩阵 → 边表」的转换。结构空间适合的图在算法里的角色n×n 邻接矩阵WmatO(n²)稠密图、坐标两两可达输入形式转成边表后基本不再用k×3 边表[u v w]O(k)稀疏图、只给部分边排序和主循环的工作结构parent/rank数组O(n)无所谓稀疏稠密并查集状态只跟节点数有关选型的实际影响体现在 n 的规模上。n50 时邻接矩阵才 2500 个元素怎么存都无所谓n5000 时邻接矩阵是 2500 万个数光find一遍就吃掉几百 MB而真实路网、通信网这类图边数往往只有节点的几倍边表能把内存压下去两个数量级。所以比较稳的写法是对外接口收邻接矩阵用户方便对内一律转边表算法高效并额外提供一个直接吃边表的入口给稀疏图场景用。还有一点要注意转换的时候只取上三角[ii, jj] find(triu(Wmat, 1)); % triu(...,1) 只保留主对角线以上如果整张矩阵扫无向图的每条边会算两次边数翻倍。边数翻倍本身不致命但后面排序多了近一倍元素主循环也多跑一轮属于白白浪费更麻烦的是输出结果里可能出现(3,7)和(7,3)同时被打印出来看起来像算法出了 bug。2.3 并查集为什么不能省每次做连通性检查会怎样新手最容易写出的版本是每挑一条边就用 BFS 或者连通分量矩阵判断两个端点是不是已经连通。n 个点、k 条边每判断一次要 O(nk)总体复杂度 O(k·(nk))完全图下 kn²直接退化成 O(n³) 以上。n200 的完全图就要跑上千万次操作MATLAB 这种解释执行环境下会明显感觉到卡。并查集把这一步压到近似 O(α(n))α 是阿克曼函数的反函数n 在现实规模内几乎不超过 4。代价是多维护两个长度 n 的数组几乎可以忽略。所以这不是「优化技巧」而是这个算法的标准配置——没有并查集的克鲁斯卡尔只能叫「按边排序的贪心尝试」。这里有个 MATLAB 特有的坑必须提前说清楚MATLAB 函数参数是按值传递函数内部改parent数组调用方的parent一个字节都不会变。所以并查集的find必须写成[root, parent] uf_find(parent, x)把压缩后的数组返回出去。第一次写的人十个里有八个会漏返回值然后发现路径压缩完全没生效跑得比预期慢还找不到原因。2.4 输入输出接口约定先把契约写死接口约定清楚了后面二次开发才不会互相打架。这份代码的约定是参数方向类型说明Wmat入n×n double对称权重矩阵0或Inf表示两点之间无边T出k×3 double选中边表每行[u v w]k ≤ n-1W出double生成树或森林总权重flag出logicaltrue表示图连通false表示只得到最小生成森林用0而不是Inf表示无边是因为 MATLAB 里Inf参与排序会和数值混在一起容易写错判断用0更直观但必须记得先做「0 → 剔除」的过滤否则权重 0 的边会被当成最短边全部塞进树里这就是最典型的翻车场景之一第 5 章展开。3. 核心模块拆解从边表排序到并查集合并的完整链路主函数一共四个动作校验输入、构建边表、升序排序、并查集主循环。除了排序那一行是 MATLAB 自带的其余都得自己写逐段看代码比较实在。3.1 输入校验与边表构建function [T, totalW, flag] kruskal_mst(Wmat) % KRUSKAL_MST 用克鲁斯卡尔算法求无向图的最小生成树 % 输入 Wmat : n x n 对称权重矩阵0 或 Inf 表示两点之间无边 % 输出 T : k x 3 边表 [u v w]k n-1 % totalW: 生成树总权重 % flag : true 表示图连通 n size(Wmat, 1); if size(Wmat, 2) ~ n error(kruskal:notSquare, 权重矩阵必须是方阵); end if ~isequal(Wmat, Wmat) % 无向图必须对称 error(kruskal:notSymmetric, 权重矩阵必须对称); end if any(diag(Wmat) ~ 0) % 不支持自环从对角线入手检查 error(kruskal:selfLoop, 对角线必须为 0); end % 只取上三角避免同一条边被当成两条 valid triu(Wmat ~ 0 isfinite(Wmat), 1); [ii, jj] find(valid); w Wmat(sub2ind([n n], ii, jj)); % 线性索引取值比 arrayfun 快这段代码的逻辑说明triu(Wmat ~ 0 isfinite(Wmat), 1)先把「权重不为 0 且不是 Inf/NaN」的位置标出来再取上三角得到的逻辑矩阵里每个true正好对应一条无向边。sub2ind那一行是把行列下标拼成线性下标一次性从矩阵里取值比for循环或者arrayfun((a,b) Wmat(a,b), ii, jj)快一个量级。参数说明Wmat必须是 n×n 的 double 方阵对角线上如果填了非零值会直接报错——自环在最小生成树里恒为无用边提前拦住比事后调试划算。isequal(Wmat, Wmat)这个检查看起来啰嗦但它拦住的是最麻烦的一类错误有人从 CSV 里读数据只填了下三角上三角是全零跑出来的结果会缺一大半边而算法本身不报错只是结果偏小。加了对称性检查这种数据问题会在入口就暴露。3.2 并查集路径压缩与按秩合并function [root, parent] uf_find(parent, x) % 查找 x 所在树的根顺便做路径压缩 root x; while parent(root) ~ root root parent(root); % 一路向上找根 end % 第二趟把沿途节点全部挂到根上下次查找就是一步到位 while parent(x) ~ root nxt parent(x); parent(x) root; x nxt; end endfunction [parent, rank] uf_union(parent, rank, ra, rb) % 合并两棵树ra、rb 必须是已经找到的根节点 if ra rb return; % 同根合并无意义 end if rank(ra) rank(rb) parent(ra) rb; % 矮树挂到高树下面 elseif rank(ra) rank(rb) parent(rb) ra; else parent(rb) ra; rank(ra) rank(ra) 1; % 同高度才需要抬高秩 end end逻辑说明uf_find用了两趟循环第一趟找根第二趟从原来的x开始往上走把路径上每个节点的父指针直接改成根。写成两趟而不是递归是因为 MATLAB 的递归深度限制和函数调用开销都不友好几千个节点链状结构很容易触发递归上限。nxt这个临时变量不能省先存后改否则parent(x)被覆盖之后就找不到下一跳了。参数说明parent是长度 n 的整数数组初始化为1:n即每个节点自成一棵树rank初始化为全零用来记录树高的上界。uf_union传的是根不是节点这一点必须在注释里写死否则调用方很容易传进未压缩的节点编号导致parent结构被破坏症状是后面find出现死循环——这是排查起来最费劲的一类问题因为循环体看起来完全正常。按秩合并的价值在数据规模大时才显现。只有路径压缩、不做按秩合并单次find的均摊复杂度是 O(log n)两者都做才是 O(α(n))。日常几百个节点的课程作业感觉不出来几万个节点的路网数据就有差距了。3.3 主循环挑边、判环、提前退出% 按权重升序排列order 是原下标 [~, order] sort(w, ascend); parent 1:n; rank zeros(1, n); T zeros(n-1, 3); % 预分配最多 n-1 条边 cnt 0; totalW 0; for k 1:numel(order) e order(k); u ii(e); v jj(e); [ru, parent] uf_find(parent, u); [rv, parent] uf_find(parent, v); if ru rv continue; % 已经连通加了就成环 end [parent, rank] uf_union(parent, rank, ru, rv); cnt cnt 1; T(cnt, :) [u v w(e)]; totalW totalW w(e); if cnt n - 1 break; % 生成树已满后面的边不用看 end end T T(1:cnt, :); flag (cnt n - 1); end逻辑说明外层按权重从小到大遍历边每取一条边先查两个端点是否同根同根说明加上去会成环直接跳过不同根就合并、记账。cnt n - 1时提前break这是克鲁斯卡尔里最容易被忽略但收益最明显的一步——完全图有 n(n-1)/2 条边而生成树只要 n-1 条正常数据下循环跑到很靠前的位置就能结束后面的边根本不用碰。参数说明T用zeros(n-1, 3)预分配再截断比每轮T(end1,:) ...快得多后者每次扩容都要重新分配内存节点数上千时差距明显。flag同时承担两个信息图是否连通以及T是生成树还是生成森林。sort的稳定性值得提一句。权重相等的边排序后谁在前谁在后不影响总权重但会影响最终选出的边集。做作业无所谓做工程就可能出问题两次运行结果边集不一样用户会以为代码有随机性。想固定下来可以在排序时加次级排序键比如按u再按v或者干脆接受这个不确定性在文档里写清楚「等权情况下结果不唯一」——最小生成树本来就不唯一这一点说清楚能省掉很多解释成本。3.4 结果封装与连通性判断返回之前还有一件事值得做把完全孤立、一条边都没有的节点标出来。flag为false时只说明图不连通但用户往往还想知道是哪几个点没连上。if ~flag % 找出最终仍是孤岛或属于其他连通分量的节点供调用方判断 roots zeros(1, n); for i 1:n [roots(i), parent] uf_find(parent, i); end comps unique(roots); fprintf(图不连通共 %d 个连通分量\n, numel(comps)); end这段是辅助输出不带返回值只打印。真实项目里我更习惯把roots作为第四个大可选输出让调用方能拿到分量标签去做后续处理比如分别给每个分量做布线方案。MATLAB 的nargout可以判断调用方要不要实现成本很低。4. 跑起来两种输入格式、函数调用与生成树可视化代码放在当前工作目录下或者addpath加进来就能在命令行直接调用。这一章给两个能直接抄的示例一个稠密一个稀疏覆盖大部分使用场景。4.1 输入一节点坐标现场建完全图% demo_city_grid.m rng(7); % 固定随机种子结果可复现 n 12; X rand(n, 2) * 100; % 12 个候选点位坐标落在 100x100 区域 D zeros(n); for i 1:n for j i1:n D(i, j) norm(X(i,:) - X(j,:)); % 欧氏距离作为布线成本 end end D D D; % 补成对称矩阵主对角线为 0 [T, W, flag] kruskal_mst(D); fprintf(连通%d, 树边数%d, 总权重%.2f\n, flag, size(T,1), W); plot_mst(X, T, D, W);逻辑说明先造坐标再算两两距离得到完全图的邻接矩阵。rng(7)是关键不固定种子的话每次跑出来的点位不同跟别人对不上话讨论「为什么我的总权重是 486」时会很尴尬。norm(X(i,:) - X(j,:))是 MATLAB 里算欧氏距离最直接的方式不需要pdist也就避开了对统计工具箱的依赖。参数说明n就是节点数改大改小都可以但完全图边数是 n(n-1)/2n200 就是将近两万条边排序和主循环会开始有感。100是坐标范围改成实际图纸尺寸即可。4.2 输入二稀疏图只给部分边现实中的图往往不是两两可达比如路网里很多路口之间根本没有直连。这时候邻接矩阵大部分位置都是 0% demo_sparse_graph.m mask triu(rand(n) 0.3, 1); % 30% 的边留下 mask mask | mask; % 对称化保证无向 D2 D .* mask; % 没留下的边权重变 0即「无边」 [T2, W2, flag2] kruskal_mst(D2); if ~flag2 warning(图不连通返回的是最小生成森林); end逻辑说明triu(rand(n) 0.3, 1)生成一个上三角的逻辑掩码mask | mask把它对称化D .* mask完成筛选。这种写法比for循环逐条删边短得多也更好读。参数说明0.3是保留边的概率调小就更容易出现不连通是测试flag分支的好办法。0.3时 12 个节点大概率还连通想稳定复现「不连通」把概率压到 0.15 左右。plot_mst的实现思路很简单先画所有边的灰色细线当底图再把T里的边用红粗线盖上去最后画节点圆圈和编号。function plot_mst(X, T, Wmat, W) figure(Color, w); hold on; box on; n size(Wmat, 1); [ii, jj] find(triu(Wmat ~ 0 isfinite(Wmat), 1)); for k 1:numel(ii) plot(X([ii(k) jj(k)],1), X([ii(k) jj(k)],2), -, Color, [0.82 0.82 0.82]); end for k 1:size(T,1) plot(X(T(k,1:2),1), X(T(k,1:2),2), -, LineWidth, 2, Color, [0.85 0.2 0.2]); end plot(X(:,1), X(:,2), o, MarkerSize, 6, ... MarkerFaceColor, w, MarkerEdgeColor, k); text(X(:,1)0.8, X(:,2)0.8, string(1:n), FontSize, 8); title(sprintf(MST 总权重 %.2f, W)); hold off; end参数说明X是 n×2 的坐标矩阵T是主函数返回的边表Wmat用来画底图。text加了个0.8的偏移避免编号压在节点圆圈上坐标范围不同可以按比例调。4.3 用自带的 minspantree 对答案较新版本的 MATLABR2015b 及以后自带graph对象和minspantree不依赖额外工具箱。它不能替代手写实现因为你要改算法但拿来做交叉验证非常合适G graph(D2); % 0 表示无边符合 graph 的约定 [Tref, Wref] minspantree(G); fprintf(参考解总权重 %.4f自写解 %.4f差 %.2e\n, ... Wref, W2, abs(Wref - W2));逻辑说明graph(D2)把邻接矩阵变成图对象minspantree求最小生成树。两个总权重在浮点误差范围内相等基本可以认为实现正确。参数说明graph的邻接矩阵里0会被当成「无边」这一点和我们的约定刚好一致但如果你的真实数据里存在权重为 0 的合法边这里就会静默丢边两边结果都对不上——第 5 章会专门讲这个。5. 避坑与排查连不通、成环、索引错位这五类翻车现场算法本身只有二十几行出问题的往往在数据准备和边界处理上。下面五条是实际调试里反复出现的按「现象 → 原因 → 解决」写遇到对得上的直接照方抓药。5.1 现象结果里出现了环或者边数超过 n-1现象很直观把T画出来能看到闭合回路或者size(T,1)打印出 15 而 n 只有 10。原因基本只有一个并查集的uf_find没有返回压缩后的parent调用方用的还是旧的数组压缩等于没做但更严重的是如果连uf_union的返回值也漏了parent在函数外完全没被修改每次find都返回节点自己判环逻辑彻底失效。解决办法是把接口检查一遍[ru, parent] uf_find(parent, u);和[parent, rank] uf_union(parent, rank, ru, rv);两处都必须接住返回值。排查时可以在主循环里打印sum(parent ~ 1:n)如果一直是 0说明合并根本没生效问题就定位到并查集了。5.2 现象总权重比手算大而且大得离谱先怀疑0的语义。用0表示「无边」是个方便但危险的约定如果真实数据里存在权重正好为 0 的边Wmat ~ 0这个过滤会把它当成不存在导致某些本该连通的点被判成孤岛最后返回的是森林而不是树总权重自然对不上。解决方式有两种一是数据准备阶段把合法零权边改成一个极小正数比如1e-9视觉上不影响结果二是把约定改成「Inf表示无边」过滤条件改成isfinite(Wmat)代价是所有 0 都要写成Inf再传入。我在项目里一般选第一种改数据比改约定风险小。5.3 现象图不连通时函数不报错返回的 T 少了边这是设计如此不是 bug。克鲁斯卡尔跑到边遍历完如果cnt n-1说明原图本来就不连通只能给出最小生成森林。问题在于很多调用方不看flag直接拿T去做后续计算结果算出一堆孤立点。解决办法是别只依赖返回值在flag false时至少warning一次把连通分量数量打出来。更稳的做法是把分量标签也返回让调用方自己决定是补边、拆分处理还是直接报错退出。这个后悔药提前吃比事后追数据便宜得多。5.4 现象稀疏图上结果正确率忽高忽低概率性出现的错误最难查。常见原因是边表构建时用find(Wmat)而不是find(triu(Wmat, 1))无向边被算了两次。两次本身不影响正确性但如果你在边表之外还维护了一个「已选边」的计数器或者去重逻辑重复边就会让计数错位导致提前break漏掉本该加入的边。另一种情况是手动造边表时节点编号从 0 开始受其他语言习惯影响而 MATLAB 索引从 1 开始parent(0)直接报错或者被当成非法索引静默处理。解决办法是在入口加一句if any([ii; jj] 1), error(...)拦住比在循环里崩掉好定位得多。5.5 现象n 到几百就明显变慢如果n300的完全图要跑好几秒先看三处。一是T(end1,:) ...有没有改成预分配这是最常见的性能黑洞二是uf_find是不是写成了递归MATLAB 的函数调用开销在深链上很难看三是边表构建有没有用arrayfun改用sub2ind一次性取下标能快一个数量级。还有一处容易被忽略sort排的是w但主循环里每次要用order(k)反查ii、jj、w如果w是从矩阵里临时算出来的比如每次循环重算距离开销会翻倍。正确做法是排序前就把w固化成数组循环里只做下标访问。6. 二次开发换算法、加约束和随机对照验证的三个改造方向代码跑通只是起点多数人拿到它是要改的。三个方向最常用。换算法做对比。稠密图场景下 Prim 往往更快因为它是按点扩展不需要对全部边排序。改造位置很集中保留kruskal_mst.m的输入校验和输出封装把中间的排序和主循环换成「维护一个已选点集 一个候选边最小堆」。MATLAB 没有原生堆用sort每次取最小也行n 不大时够用。改完拿同一份D分别喂给两个函数比总权重和运行时间。改造点修改位置注意换 Prim主循环整体替换输出格式保持k×3不变方便对比脚本复用加「必须包含某条边」约束主循环前预先把该边合并进并查集记得把这条边的权重计入总数加「禁止某些边」边表构建后过滤过滤后要重新检查连通性可能直接变成森林支持有向图uf_find换成拓扑排序有向图的最小生成树是另一个问题最小树形图加约束是克鲁斯卡尔最舒服的地方。比如布线场景要求某两个机房之间必须直连做法不是改算法而是在主循环之前先把这条边uf_union掉、计入totalW然后正常跑。禁止某些边同理在valid triu(...)之后加一层掩码就行。这种「预处理 原算法」的模式比改算法体面得多出问题也容易回滚到无约束版本做对照。如果是「每个节点度数不超过 k」这类约束贪心就不保证了得换思路这时候别硬改直接上整数规划更省时间。随机对照验证是我现在的固定动作。手写图算法最容易在边界上翻车靠几个手算例子根本盖不住。我的做法是写一个循环随机生成不同规模、不同稀疏度的图把自写实现和minspantree的结果逐一比对function ok verify_kruskal(trials) % 随机图批量对照自写 kruskal_mst vs MATLAB 自带 minspantree ok true; for t 1:trials n randi([5, 60]); X rand(n, 2) * 100; D zeros(n); for i 1:n for j i1:n D(i,j) norm(X(i,:) - X(j,:)); end end D D D; keep triu(rand(n) 0.4, 1); % 随机稀疏化制造不连通场景 keep keep | keep; D D .* keep; [~, W1, f1] kruskal_mst(D); G graph(D); [~, W2] minspantree(G); if f1 abs(W1 - W2) 1e-8 fprintf(第 %d 轮不一致自写 %.10f参考 %.10f\n, t, W1, W2); ok false; end end end这段的价值在于把「不连通」「单节点」「两条边等权」这些边角情况用随机数自动覆盖掉。跑 200 轮能过基本就稳了过不了把rng固定到出问题那一轮单独复现比盯着代码瞎猜快得多。我踩过最深的一个坑是早期版本为了省事在D .* keep之后又手动把对角线补了一遍非零值结果自环混进边表排序后排在最前面主循环一上来就把每个点自己和并了一次parent结构直接乱掉而算法还不报错——只是结果偏小。那之后我每次改图算法的入口不管多小的例子都强制先跑一遍随机对照再手算一两个小图确认输出格式两关都过了才往下写。希望帮到你。本文还有配套的精品资源点击获取