简介围绕克鲁斯卡尔算法整理的 MATLAB 代码包面向正在学习图论、最小生成树及网络优化练习的初、中级用户。压缩包共 4 个文件全部为 .m 脚本或函数文件大小约 2KB体积轻便适合直接查阅、运行与二次修改内容涉及邻接矩阵建图、边集提取、按权重排序、并查集初始化与路径压缩、环路判断以及最小生成树构建等环节。已有 409 人学习可作为课堂实验、课程设计或算法复现的参考。读者能够据此理清 Kruskal 算法的模块拆分与调用关系对照输入、排序、并查集和结果输出梳理完整实现思路并在调试、改写和扩展测试中加深对最小生成树问题的理解对于需要快速复现算法流程或为后续图算法实验打基础的读者也提供了较直观的入口。1. 一个布线预算表MATLAB 克鲁斯卡尔算法到底在算什么去年帮一个做园区管网的团队看预算表发现他们手工排的管线比理论最优多出将近两成成本原因很朴素谁都按“就近连”的思路拍脑袋没人真去算一遍最小生成树。这份 MATLAB 克鲁斯卡尔Kruskal算法实现解决的就是这类问题——给一堆节点和节点之间带权重的候选连接挑出一组总权重最小、又保证所有节点连通的边。它适合两类人一是在课程设计或论文里需要一份能跑、能画图、能改的最小生成树代码的同学二是手里有真实距离矩阵、想快速验证“最优布线能省多少”的工程开发。代码本身不复杂但并查集在 MATLAB 里的值传递写法、邻接矩阵转边表的重边问题都是要踩过才知道的地方下面按目录、代码、运行、改造一路拆下去。2. 工程骨架拆解边表、排序、并查集三件套怎么分文件克鲁斯卡尔算法的思路可以压缩成一句话把所有边按权重从小到大排好依次尝试加入只要这条边的两个端点当前不在同一个连通分量里就收下它直到收满 n-1 条为止。真正决定代码质量的不是这句话而是“怎么判断两个端点是否同属一个分量”——这就是并查集的位置。在 MATLAB 里如果只用一个几百行的大脚本从头写到尾跑通没问题但只要你想换一份输入数据或者想把它塞进别的流程里就会立刻难受。常见做法是按职责拆成主函数、边表转换、并查集查找、并查集合并、演示脚本五个部分输入输出都用普通矩阵不依赖任何工具箱。2.1 目录与文件职责拆完之后的目录大致长这样每个文件只干一件事文件名就是它的职责说明kruskal_mst/ ├── kruskal.m % 主求解排序 主循环 结果回填 ├── adj2edges.m % 邻接矩阵 - 边表去重去自环 ├── uf_find.m % 并查集查找带路径压缩 ├── uf_union.m % 并查集合并按秩合并 ├── build_random_graph.m % 造随机连通图用于演示和压力测试 ├── demo_random.m % 随机图演示求解 画图 ├── demo_coords.m % 坐标图演示欧氏距离当权重 └── verify_against_builtin.m % 对拍脚本和内置 minspantree 比结果这里没有graph包、没有 classdef就是一组平铺的函数文件。理由很实际这套代码最常被拿去当教学材料或者嵌进别人已有的脚本里平铺函数用addpath一挂就能调比包和类都省事。verify_against_builtin.m是个容易被忽略但特别值得留的文件——自己实现的算法最怕“看起来对”有个能对拍的内置实现改完代码跑一遍就知道有没有把结果改坏。如果你的 MATLAB 版本较老、没有graph对象这个文件可以删掉不影响主流程。需要提醒的是主函数签名。常见做法是让kruskal接收“边表 节点数”两个参数而不是直接接收邻接矩阵。原因是邻接矩阵到边表的转换有坑重边、自环、不连通时 0 值怎么处理把它单独拆成adj2edges.m之后这个坑只在一个文件里出现改起来也只改一处。反过来说如果你拿到的是坐标而不是距离也只要写个几行的距离计算把坐标变成边表主函数完全不用动。2.2 数据入口邻接矩阵、边表、坐标三种输入怎么统一实际用起来输入数据基本就三种形态处理方式不一样输入形态典型来源转换方式注意点邻接矩阵 n×n距离表、相似度矩阵triu取上三角后find必须去自环、去重边边表 m×3数据库导出的连线清单直接用列顺序要固定为 u,v,w坐标 n×2传感器、站点位置先算两两距离再转边表全连接图边数是 n(n-1)/2统一到边表之后主函数就只认一种格式一个 m 行 3 列的数值矩阵第一列起点编号、第二列终点编号、第三列权重节点编号必须是 1 到 n 的连续正整数。这个约定听起来啰嗦但它是整套代码能复用的前提。我见过太多版本直接在函数体里写A(i,j)的下标运算结果想换成边表输入就得重写一遍。坐标输入这一路值得多说一句如果节点数是几百个两两算距离得到全连接图边数会到几万条排序完全扛得住但如果节点数上千边数就是几十万MATLAB 里一个 double 矩阵存三列也就几 MB还是能跑只是画图会卡。这时候通常的做法是先做一遍 k 近邻裁剪只保留每个点最近的若干个邻居图仍然连通但边数大幅下降。这一步不是克鲁斯卡尔本身的要求是喂数据之前的预处理放到build_random_graph.m或者独立的预处理脚本里更合适。2.3 主流程函数的调用链把调用链画成文字就是一条直线没有回调、没有递归demo_*.m └─ build/读取数据 └─ adj2edges.m如果是矩阵输入 └─ kruskal.m ├─ sort按第三列升序 ├─ uf_find.m 每次尝试边时调用两次 └─ uf_union.m 端点不同分量时调用一次 └─ 返回 Tn-1×3与 totalW这条链上有两个地方是性能热点。第一处是排序m条边排序是 O(m log m)在 MATLAB 里sort走的是编译好的底层实现几万条边毫秒级就完了不用优化。第二处是并查集查找主循环里每条边要查两次最坏情况接近 O(m α(n))α 是反阿克曼函数实际上近似常数。真正拖慢速度的往往不是算法本身而是把uf_find写成递归函数、或者在循环里反复edges [edges; newrow]这样增长数组——后者每次都要重新分配内存边数一多就是灾难。所以主函数的结构刻意写成“先预分配、再填坑”结果矩阵T zeros(n-1, 3)一次分配到位循环里只做T(cnt,:) ...的赋值cnt记录已经收下几条边收满n-1就直接break。这个提前退出的判断很重要它让算法在稀疏图上远早于遍历完所有边就结束。如果忘了写结果不会错但会白跑掉后面所有边在大图上差别很明显。3. 核心实现逐段读并查集与边排序的 MATLAB 写法这一章是整份代码里最值得逐行看的部分。三个函数加起来不到六十行但每一行都有它存在的理由尤其是并查集在 MATLAB 里的写法——它和 C、Python 的直觉完全不一样直接照搬会得到一个“看起来改了、实际没改”的幽灵 bug。3.1 并查集的 parent/rank 数组实现并查集用两个一维数组表示parent(i)是节点 i 的父节点编号根节点的父节点指向自己rank(i)是以 i 为根的树的高度上界只在合并时用来决定谁挂到谁下面。初始化就是把parent设成1:n。function [parent, rank] uf_init(n) % 并查集初始化每个节点自成一个集合 parent 1:n; % 父节点指向自己 rank zeros(1, n); % 秩从 0 开始 end查找函数带路径压缩把沿途所有节点直接挂到根上后续查询就变成一次跳转function [parent, root] uf_find(parent, x) % 并查集查找返回根节点并把路径上所有点压缩到根 root x; while parent(root) ~ root % 一路向上找根 root parent(root); end cur x; while parent(cur) ~ root % 第二趟把路径压平 nxt parent(cur); parent(cur) root; cur nxt; end end这里最关键的一点是函数必须把parent作为返回值吐出来。MATLAB 的函数参数是值传递写时复制函数内部对parent做的任何修改都不会影响到调用方的那个数组。所以调用时必须写成[parent, ru] uf_find(parent, u);把返回的新parent覆盖回原变量。如果偷懒只写ru uf_find(parent, u);路径压缩就白做了更严重的是后面的合并会基于旧状态结果直接错掉。这是这份代码里最容易翻车的一处几乎每个第一次用 MATLAB 写并查集的人都会中招。合并函数按秩来秩小的树挂到秩大的树下面避免退化成一条链function [parent, rank] uf_union(parent, rank, ru, rv) % 并查集合并把 ru 所在的树挂到 rv 下面或反过来 if rank(ru) rank(rv) parent(ru) rv; elseif rank(ru) rank(rv) parent(rv) ru; else parent(rv) ru; % 秩相同随便挂一个 rank(ru) rank(ru) 1; % 新根秩加一 end end两个优化叠加之后单次操作的均摊代价近似常数。单用路径压缩不用按秩合并复杂度也能到 O(log n) 级别在几千个节点的规模上其实感觉不出差别但按秩合并只多三行代码没有理由省。注意这里的rank是“秩”不是真实树高路径压缩之后真实高度会变小但秩只会增不会减作为合并的启发式依据依然成立。3.2 边表构建与排序triu 和 sort 的配合从邻接矩阵转边表这一段坑全在“重复”和“自环”上。稠密对称矩阵如果直接find(A)每条边会被取到两次(i,j)和(j,i)对角线上还会带出自环。正确做法是先取上三角function edges adj2edges(A) % 邻接矩阵转边表只取上三角天然去掉重复边和对角线 n size(A, 1); [I, J, W] find(triu(A, 1)); % triu(A,1) 保留严格上三角 edges [I, J, W]; endtriu(A, 1)把主对角线及以下全部清零find对稀疏存储的矩阵逐个返回非零元素的行列下标和值一次就拿到不重复、无自环的边表。如果你的A本身就是sparse类型这一步会更快而且内存占用只和边数有关和 n² 无关——大图上这一点差别巨大。排序这一步用sort取索引再重排比sortrows稳[~, order] sort(edges(:, 3), ascend); % 只按权重列排 edges edges(order, :); % 整行跟着重排为什么不用sortrows(edges, 3)两者结果都对但sort在这里更明确地表达了“我只关心权重列的顺序其他列跟着走”。还有一个隐性好处sort是稳定排序权重相同的边保持原来的相对顺序这样同样的输入每次跑出来的生成树是同一棵方便对拍和复现问题。sortrows在旧版本里对稳定性的保证没那么明确虽然实际行为也稳定但既然有更直接的写法就没必要给自己留疑问。3.3 主循环为什么收满 n-1 条边就能提前退出主函数把上面几块拼起来逻辑很短function [T, totalW] kruskal(edges, n) % 克鲁斯卡尔最小生成树 % edges: m×3列为 [起点 终点 权重]节点编号 1..n % n: 节点总数 % T: 生成树的边(n-1)×3图不连通时行数小于 n-1 % totalW: 生成树总权重 [~, order] sort(edges(:, 3), ascend); edges edges(order, :); parent 1:n; rank zeros(1, n); T zeros(n - 1, 3); % 预分配避免循环里增长数组 cnt 0; totalW 0; for k 1:size(edges, 1) u edges(k, 1); v edges(k, 2); w edges(k, 3); [parent, ru] uf_find(parent, u); % 注意接住返回的 parent [parent, rv] uf_find(parent, v); if ru ~ rv % 分属两个连通块这条边要了 [parent, rank] uf_union(parent, rank, ru, rv); cnt cnt 1; T(cnt, :) [u, v, w]; totalW totalW w; if cnt n - 1 % 收满即停后面不用看了 break; end end end T T(1:cnt, :); % 图不连通时把预分配多出来的零行砍掉 endcnt n - 1这个判断的依据是一条图论事实n 个节点的树恰好有 n-1 条边。因为算法每次都只在“端点不同分量”时才收边所以收下的边一定不会成环收到的边集合始终是一片森林当森林里有 n-1 条边时它必然已经覆盖全部 n 个节点此时再往后看任何一条边端点一定在同一分量里全部会被拒绝。提前退出省下的是“剩下那些边还要各查两次并查集”的开销在边数远大于 n 的稠密图上能省掉一大半时间。最后那行T T(1:cnt, :)处理的是不连通图。如果图本身不连通循环跑完也不会有cnt n-1此时T里后面那些预分配的行还是全零直接返回会让调用方以为存在一条0-0-0的边。砍掉之后调用方拿到的是“森林的边集”长度小于 n-1一眼就能看出图不连通。这种做法比抛异常温和也方便调用方自己决定是报错还是补边。提示如果你的输入保证连通可以省掉这行但建议保留——它几乎不花时间却能在数据出问题时给你一个明确的信号。3.4 结果回填与可视化拿到T之后画图通常用graph对象一步到位G graph(T(:,1), T(:,2), T(:,3), n); % 用生成树的边建图 p plot(G, EdgeLabel, G.Edges.Weight, Layout, force); highlight(p, EdgeColor, [0.85 0.33 0.10], LineWidth, 2); title(sprintf(MST 总权重 %.2f, sum(T(:,3))));graph的第四个参数是节点数一定要显式传n否则孤立节点会被自动丢弃画出来的图和原问题对不上。Layout选force是省事做法如果有真实坐标改成plot(G, XData, pos(:,1), YData, pos(:,2))更直观节点位置和实际地理位置对应给非技术同事看的时候说服力强很多。高亮那一步用highlight比重新plot一遍省事也不会把节点位置抖乱。边标签在边数超过三四十条时就会挤成一团这时候建议关掉EdgeLabel改成在图标题里写总权重——读者关心的是“省了多少”不是每条边的具体数值。4. 跑起来MATLAB 与开源替代环境的两条实操路径代码写完只是第一步能不能在别人机器上跑通是另一回事。这一章按“最少步骤跑出结果”和“跑出来怎么验”两条线走顺手把随机数据生成也讲了方便你自己造测试用例。4.1 最小可运行脚本把前面几个文件放在同一个目录新建一个脚本五行就能看到结果% demo_min.m —— 最小可运行示例 n 6; A zeros(n); % 手工构造一个带权无向图0 表示无边 A(1,2)4; A(2,1)4; A(1,3)1; A(3,1)1; A(2,3)2; A(3,2)2; A(2,4)5; A(4,2)5; A(3,5)8; A(5,3)8; A(4,5)3; A(5,4)3; A(4,6)7; A(6,4)7; A(5,6)6; A(6,5)6; edges adj2edges(A); [T, w] kruskal(edges, n); disp(T); fprintf(总权重 %.2f\n, w);adj2edges把对称矩阵削成 9 条候选边kruskal从中挑 5 条作为生成树总权重应该是 12367 19。如果你的输出不是这个数先别怀疑算法去检查A是不是严格对称——只要有一处只写了一边triu就会把它丢掉或者读错。手工构造这种小例子看着笨但它是唯一能让你在没有对拍工具时确认“算法真在按预期走”的办法。4.2 输入数据怎么造随机图与坐标图真实数据不好找的时候随机图是最省事的压力测试来源function [A, pos] build_random_graph(n, p, seed) % 生成 n 个点的随机连通图边存在概率 p if nargin 2, rng(seed); end pos rand(n, 2) * 100; % 随机坐标仅用于画图 D squareform(pdist(pos)); % 欧氏距离矩阵 A zeros(n); for i 1:n for j i1:n if rand p A(i,j) D(i,j); A(j,i) D(i,j); end end end % 补一条链保证连通否则 MST 收不满 n-1 条边 for i 1:n-1 if A(i,i1) 0 A(i,i1) D(i,i1); A(i1,i) D(i,i1); end end end最后那个补链的循环很关键。随机生成的图在p偏小的时候大概率不连通kruskal会老老实实返回一片森林你看着“边数不对”还以为算法坏了。补一条 1-2-3-…-n 的链之后图一定连通结果一定恰好 n-1 条边验证起来干净利落。pdist加squareform是 MATLAB 里算两两距离的标配组合返回的是完整对称矩阵。节点数上千时这个矩阵就是 8×10⁶ 个 double约 64MB还扛得住再往上就该改用稀疏表示或者直接按需计算距离别一次性铺开。4.3 输出怎么验三个必查项跑出结果之后至少检查三件事能挡掉九成的实现错误。第一边数。连通图上必须是 n-1 条。少了说明图不连通或者主循环提前退出的条件写错了多了说明去环逻辑失效。第二总权重对拍。如果环境里有minspantree直接比G graph(edges(:,1), edges(:,2), edges(:,3), n); Tb minspantree(G); fprintf(内置总权重 %.4f\n, sum(Tb.Edges.Weight)); fprintf(自实现总权重 %.4f\n, totalW);两个数在浮点误差范围内相等基本可以认为实现正确。这一步建议做成固定脚本而不是临时敲改完代码随手跑一遍比肉眼检查靠谱得多。第三连通性自检。把T的边重新建一个并查集走一遍最后数一数根节点个数等于 1 才算生成树parent 1:n; for k 1:size(T,1) [parent, ru] uf_find(parent, T(k,1)); [parent, rv] uf_find(parent, T(k,2)); if ru ~ rv [parent, ~] uf_union(parent, zeros(1,n), ru, rv); end end roots arrayfun((x) uf_find(parent, x), 1:n); fprintf(连通分量数 %d\n, numel(unique(roots(1,:))));这段自检代码看着有点绕但它不依赖任何工具箱在任何版本的 MATLAB 和开源替代环境里都能跑。写一次放那儿后面每次改完主函数都跑一遍心里踏实。5. 避坑与排查五个跑起来才会撞上的问题下面五条基本都是我在不同场合真实撞过或者见别人撞过的按“现象 → 原因 → 解决”记下来遇到时对号入座就行。5.1 现象结果总权重偏大生成树里出现了明显不该选的边原因几乎一定是并查集没生效。最常见的写法是ru uf_find(parent, u);漏掉了把返回的parent接回去。这样查找函数内部做的路径压缩全部丢失更致命的是合并时用的是旧的parent导致两个本该合并的集合没有真的合并后面判环全部失效算法退化成“随便挑边”。解决把所有uf_find调用改成[parent, ru] uf_find(parent, u);的形式uf_union同理。改完在一张小图上手工算一遍期望结果比对一下。这个坑太常见我现在写这类代码时会先写一个三节点的最小测试确认并查集行为正确再往上搭。5.2 现象边表里出现(i,i)自环或者每条边出现两次原因是从邻接矩阵转边表时直接用了find(A)而不是find(triu(A,1))。对称矩阵的每条边在对角线两侧各存一份find会把两份都取出来对角线上的非零值还会变成自环。解决统一走adj2edges不要在主函数里临时写find。如果你的矩阵不是严格对称手工录数据时很容易只写一边先做一次A max(A, A)把两边对齐再取上三角。自环本身在克鲁斯卡尔里会被并查集自然拒绝同一节点当然同分量不会算错但会让边数统计和调试输出变得难看早去早省心。5.3 现象图明明连通返回的边数却小于 n-1原因有两种。一是节点编号不连续比如输入用的是 0 到 n-1 或者带空洞的 ID而parent 1:n假设编号从 1 开始连续编号超范围的节点一访问就越界报错编号缺失的节点则永远孤立。二是图确实不连通比如随机生成时p太小又没补链。解决进主函数前加一句校验assert(all(edges(:,1:2) 1) all(edges(:,1:2) n) all(edges(:,1:2) fix(edges(:,1:2))))编号不合规立刻报错而不是算出个莫名其妙的结果。对不连通的情况主函数返回行数不足的T是合理行为调用方拿到后先判断size(T,1) n-1不满足就说明图有问题该补边补边该换数据换数据。5.4 现象换一份大一点的输入内存直接飙到几个 G原因是全程用稠密邻接矩阵。n 个节点就是 n² 个 doublen 到两万时单个矩阵就 3.2GB还没开始排序就已经把内存吃光了。解决节点数超过几千就改用稀疏矩阵或者直接构造边表。A sparse(i, j, w, n, n); A A A;之后adj2edges里的triu和find依然适用内存只和边数成正比。更进一步可以跳过矩阵直接从数据源拼出 m×3 的边表喂给kruskal——主函数本来就只认边表这条路一直是通的只是很多人习惯性地从矩阵入口进。5.5 现象同一份数据跑两次画出来的生成树不一样原因是权重存在大量相等值而排序不稳定或者数据本身有随机性比如用rand生成的位置每次不同。克鲁斯卡尔在权重相同时选哪条边不唯一总权重一样但树的形状可能不同这本身不是错误。解决想要结果可复现一是固定随机种子rng(42)二是排序用sort而不是其他不稳定实现三是比较结果时只比总权重和边数不要逐边比对。如果业务上确实要求“权重相同时按某种规则选”比如优先选小编号节点那就在排序前给边表加一列次级排序键用sortrows(edges, [3 1 2])按权重、起点、终点依次排。这个需求在小规模教学例子里不明显一旦上真实数据就会有人问“为什么两次结果不一样”提前想好怎么答。6. 二次开发从教学脚本改成能进项目的工具函数这套代码最容易停在一个尴尬位置能跑、能画图、能交作业但真要塞进别人的流程里就处处别扭。我一般会做三件事把它推到“能用”的水准。第一件是接口收敛。主函数签名保持[T, totalW] kruskal(edges, n)不变但加一个可选参数结构体把“是否返回并查集状态”“是否允许不连通”这类开关收进去function [T, totalW, info] kruskal(edges, n, opts) % opts.allowDisconnected : true 时不连通也返回森林默认 false % opts.returnComponent : true 时在 info 里返回每个节点的根 if nargin 3, opts struct(); end allowDisc getfield_default(opts, allowDisconnected, false); ... if cnt n - 1 ~allowDisc error(kruskal:disconnected, 图不连通只找到 %d/%d 条边, cnt, n-1); end这样默认行为是“不连通就报错”比返回一个长度不对的矩阵更容易在流水线里被发现需要宽容处理的场景显式打开开关。info里带上并查集的最终状态调用方可以顺手拿到连通分量划分做后续聚类或者分组不用再算一遍。第二件是对拍常态化。把verify_against_builtin.m改成脚本末尾自动跑的断言输入覆盖小图、稠密图、稀疏图、带重复权重的图四种情况每次改完主函数跑一遍全绿才算完cases {build_random_graph(8, 0.9, 1), build_random_graph(50, 0.3, 2), ... build_random_graph(200, 0.05, 3)}; for c 1:numel(cases) [A, ~] cases{c}; edges adj2edges(A); [~, w1] kruskal(edges, size(A,1)); G graph(edges(:,1), edges(:,2), edges(:,3), size(A,1)); w2 sum(minspantree(G).Edges.Weight); assert(abs(w1 - w2) 1e-9, 第 %d 组对拍失败%.6f vs %.6f, c, w1, w2); end第三件是把“必选边”这个真实需求考虑进去。工程上经常有“某几段管线已经建好必须包含在结果里”的情况做法是先把这些边强行合并进并查集并计入结果再从剩下的边里正常跑克鲁斯卡尔——注意这时候目标边数仍然是 n-1但初始cnt不再是 0。加这个功能只需要在主循环前插一段预合并改动不到十行却能让这份代码从“玩具”变成“能接需求”的东西。必须说一句这些改造里最值钱的不是功能而是对拍脚本。早年我改这类算法时习惯靠肉眼比对画出来的树觉得“形状差不多”就收工结果有一次在权重存在大量重复值的数据上总权重差了 0.3%画出来根本看不出来。从那以后我每次动排序或者并查集相关的代码都强制先把对拍脚本跑一遍再谈别的。希望这些经验帮到你少走一遍我当年绕的那段路。本文还有配套的精品资源点击获取 
长河君 · 2026/10/30 10:29:47 · 阅读 1.2k MATLAB克鲁斯卡尔最小生成树实现：并查集、边表与工程布线优化
简介围绕克鲁斯卡尔算法整理的 MATLAB 代码包面向正在学习图论、最小生成树及网络优化练习的初、中级用户。压缩包共 4 个文件全部为 .m 脚本或函数文件大小约 2KB体积轻便适合直接查阅、运行与二次修改内容涉及邻接矩阵建图、边集提取、按权重排序、并查集初始化与路径压缩、环路判断以及最小生成树构建等环节。已有 409 人学习可作为课堂实验、课程设计或算法复现的参考。读者能够据此理清 Kruskal 算法的模块拆分与调用关系对照输入、排序、并查集和结果输出梳理完整实现思路并在调试、改写和扩展测试中加深对最小生成树问题的理解对于需要快速复现算法流程或为后续图算法实验打基础的读者也提供了较直观的入口。1. 一个布线预算表MATLAB 克鲁斯卡尔算法到底在算什么去年帮一个做园区管网的团队看预算表发现他们手工排的管线比理论最优多出将近两成成本原因很朴素谁都按“就近连”的思路拍脑袋没人真去算一遍最小生成树。这份 MATLAB 克鲁斯卡尔Kruskal算法实现解决的就是这类问题——给一堆节点和节点之间带权重的候选连接挑出一组总权重最小、又保证所有节点连通的边。它适合两类人一是在课程设计或论文里需要一份能跑、能画图、能改的最小生成树代码的同学二是手里有真实距离矩阵、想快速验证“最优布线能省多少”的工程开发。代码本身不复杂但并查集在 MATLAB 里的值传递写法、邻接矩阵转边表的重边问题都是要踩过才知道的地方下面按目录、代码、运行、改造一路拆下去。2. 工程骨架拆解边表、排序、并查集三件套怎么分文件克鲁斯卡尔算法的思路可以压缩成一句话把所有边按权重从小到大排好依次尝试加入只要这条边的两个端点当前不在同一个连通分量里就收下它直到收满 n-1 条为止。真正决定代码质量的不是这句话而是“怎么判断两个端点是否同属一个分量”——这就是并查集的位置。在 MATLAB 里如果只用一个几百行的大脚本从头写到尾跑通没问题但只要你想换一份输入数据或者想把它塞进别的流程里就会立刻难受。常见做法是按职责拆成主函数、边表转换、并查集查找、并查集合并、演示脚本五个部分输入输出都用普通矩阵不依赖任何工具箱。2.1 目录与文件职责拆完之后的目录大致长这样每个文件只干一件事文件名就是它的职责说明kruskal_mst/ ├── kruskal.m % 主求解排序 主循环 结果回填 ├── adj2edges.m % 邻接矩阵 - 边表去重去自环 ├── uf_find.m % 并查集查找带路径压缩 ├── uf_union.m % 并查集合并按秩合并 ├── build_random_graph.m % 造随机连通图用于演示和压力测试 ├── demo_random.m % 随机图演示求解 画图 ├── demo_coords.m % 坐标图演示欧氏距离当权重 └── verify_against_builtin.m % 对拍脚本和内置 minspantree 比结果这里没有graph包、没有 classdef就是一组平铺的函数文件。理由很实际这套代码最常被拿去当教学材料或者嵌进别人已有的脚本里平铺函数用addpath一挂就能调比包和类都省事。verify_against_builtin.m是个容易被忽略但特别值得留的文件——自己实现的算法最怕“看起来对”有个能对拍的内置实现改完代码跑一遍就知道有没有把结果改坏。如果你的 MATLAB 版本较老、没有graph对象这个文件可以删掉不影响主流程。需要提醒的是主函数签名。常见做法是让kruskal接收“边表 节点数”两个参数而不是直接接收邻接矩阵。原因是邻接矩阵到边表的转换有坑重边、自环、不连通时 0 值怎么处理把它单独拆成adj2edges.m之后这个坑只在一个文件里出现改起来也只改一处。反过来说如果你拿到的是坐标而不是距离也只要写个几行的距离计算把坐标变成边表主函数完全不用动。2.2 数据入口邻接矩阵、边表、坐标三种输入怎么统一实际用起来输入数据基本就三种形态处理方式不一样输入形态典型来源转换方式注意点邻接矩阵 n×n距离表、相似度矩阵triu取上三角后find必须去自环、去重边边表 m×3数据库导出的连线清单直接用列顺序要固定为 u,v,w坐标 n×2传感器、站点位置先算两两距离再转边表全连接图边数是 n(n-1)/2统一到边表之后主函数就只认一种格式一个 m 行 3 列的数值矩阵第一列起点编号、第二列终点编号、第三列权重节点编号必须是 1 到 n 的连续正整数。这个约定听起来啰嗦但它是整套代码能复用的前提。我见过太多版本直接在函数体里写A(i,j)的下标运算结果想换成边表输入就得重写一遍。坐标输入这一路值得多说一句如果节点数是几百个两两算距离得到全连接图边数会到几万条排序完全扛得住但如果节点数上千边数就是几十万MATLAB 里一个 double 矩阵存三列也就几 MB还是能跑只是画图会卡。这时候通常的做法是先做一遍 k 近邻裁剪只保留每个点最近的若干个邻居图仍然连通但边数大幅下降。这一步不是克鲁斯卡尔本身的要求是喂数据之前的预处理放到build_random_graph.m或者独立的预处理脚本里更合适。2.3 主流程函数的调用链把调用链画成文字就是一条直线没有回调、没有递归demo_*.m └─ build/读取数据 └─ adj2edges.m如果是矩阵输入 └─ kruskal.m ├─ sort按第三列升序 ├─ uf_find.m 每次尝试边时调用两次 └─ uf_union.m 端点不同分量时调用一次 └─ 返回 Tn-1×3与 totalW这条链上有两个地方是性能热点。第一处是排序m条边排序是 O(m log m)在 MATLAB 里sort走的是编译好的底层实现几万条边毫秒级就完了不用优化。第二处是并查集查找主循环里每条边要查两次最坏情况接近 O(m α(n))α 是反阿克曼函数实际上近似常数。真正拖慢速度的往往不是算法本身而是把uf_find写成递归函数、或者在循环里反复edges [edges; newrow]这样增长数组——后者每次都要重新分配内存边数一多就是灾难。所以主函数的结构刻意写成“先预分配、再填坑”结果矩阵T zeros(n-1, 3)一次分配到位循环里只做T(cnt,:) ...的赋值cnt记录已经收下几条边收满n-1就直接break。这个提前退出的判断很重要它让算法在稀疏图上远早于遍历完所有边就结束。如果忘了写结果不会错但会白跑掉后面所有边在大图上差别很明显。3. 核心实现逐段读并查集与边排序的 MATLAB 写法这一章是整份代码里最值得逐行看的部分。三个函数加起来不到六十行但每一行都有它存在的理由尤其是并查集在 MATLAB 里的写法——它和 C、Python 的直觉完全不一样直接照搬会得到一个“看起来改了、实际没改”的幽灵 bug。3.1 并查集的 parent/rank 数组实现并查集用两个一维数组表示parent(i)是节点 i 的父节点编号根节点的父节点指向自己rank(i)是以 i 为根的树的高度上界只在合并时用来决定谁挂到谁下面。初始化就是把parent设成1:n。function [parent, rank] uf_init(n) % 并查集初始化每个节点自成一个集合 parent 1:n; % 父节点指向自己 rank zeros(1, n); % 秩从 0 开始 end查找函数带路径压缩把沿途所有节点直接挂到根上后续查询就变成一次跳转function [parent, root] uf_find(parent, x) % 并查集查找返回根节点并把路径上所有点压缩到根 root x; while parent(root) ~ root % 一路向上找根 root parent(root); end cur x; while parent(cur) ~ root % 第二趟把路径压平 nxt parent(cur); parent(cur) root; cur nxt; end end这里最关键的一点是函数必须把parent作为返回值吐出来。MATLAB 的函数参数是值传递写时复制函数内部对parent做的任何修改都不会影响到调用方的那个数组。所以调用时必须写成[parent, ru] uf_find(parent, u);把返回的新parent覆盖回原变量。如果偷懒只写ru uf_find(parent, u);路径压缩就白做了更严重的是后面的合并会基于旧状态结果直接错掉。这是这份代码里最容易翻车的一处几乎每个第一次用 MATLAB 写并查集的人都会中招。合并函数按秩来秩小的树挂到秩大的树下面避免退化成一条链function [parent, rank] uf_union(parent, rank, ru, rv) % 并查集合并把 ru 所在的树挂到 rv 下面或反过来 if rank(ru) rank(rv) parent(ru) rv; elseif rank(ru) rank(rv) parent(rv) ru; else parent(rv) ru; % 秩相同随便挂一个 rank(ru) rank(ru) 1; % 新根秩加一 end end两个优化叠加之后单次操作的均摊代价近似常数。单用路径压缩不用按秩合并复杂度也能到 O(log n) 级别在几千个节点的规模上其实感觉不出差别但按秩合并只多三行代码没有理由省。注意这里的rank是“秩”不是真实树高路径压缩之后真实高度会变小但秩只会增不会减作为合并的启发式依据依然成立。3.2 边表构建与排序triu 和 sort 的配合从邻接矩阵转边表这一段坑全在“重复”和“自环”上。稠密对称矩阵如果直接find(A)每条边会被取到两次(i,j)和(j,i)对角线上还会带出自环。正确做法是先取上三角function edges adj2edges(A) % 邻接矩阵转边表只取上三角天然去掉重复边和对角线 n size(A, 1); [I, J, W] find(triu(A, 1)); % triu(A,1) 保留严格上三角 edges [I, J, W]; endtriu(A, 1)把主对角线及以下全部清零find对稀疏存储的矩阵逐个返回非零元素的行列下标和值一次就拿到不重复、无自环的边表。如果你的A本身就是sparse类型这一步会更快而且内存占用只和边数有关和 n² 无关——大图上这一点差别巨大。排序这一步用sort取索引再重排比sortrows稳[~, order] sort(edges(:, 3), ascend); % 只按权重列排 edges edges(order, :); % 整行跟着重排为什么不用sortrows(edges, 3)两者结果都对但sort在这里更明确地表达了“我只关心权重列的顺序其他列跟着走”。还有一个隐性好处sort是稳定排序权重相同的边保持原来的相对顺序这样同样的输入每次跑出来的生成树是同一棵方便对拍和复现问题。sortrows在旧版本里对稳定性的保证没那么明确虽然实际行为也稳定但既然有更直接的写法就没必要给自己留疑问。3.3 主循环为什么收满 n-1 条边就能提前退出主函数把上面几块拼起来逻辑很短function [T, totalW] kruskal(edges, n) % 克鲁斯卡尔最小生成树 % edges: m×3列为 [起点 终点 权重]节点编号 1..n % n: 节点总数 % T: 生成树的边(n-1)×3图不连通时行数小于 n-1 % totalW: 生成树总权重 [~, order] sort(edges(:, 3), ascend); edges edges(order, :); parent 1:n; rank zeros(1, n); T zeros(n - 1, 3); % 预分配避免循环里增长数组 cnt 0; totalW 0; for k 1:size(edges, 1) u edges(k, 1); v edges(k, 2); w edges(k, 3); [parent, ru] uf_find(parent, u); % 注意接住返回的 parent [parent, rv] uf_find(parent, v); if ru ~ rv % 分属两个连通块这条边要了 [parent, rank] uf_union(parent, rank, ru, rv); cnt cnt 1; T(cnt, :) [u, v, w]; totalW totalW w; if cnt n - 1 % 收满即停后面不用看了 break; end end end T T(1:cnt, :); % 图不连通时把预分配多出来的零行砍掉 endcnt n - 1这个判断的依据是一条图论事实n 个节点的树恰好有 n-1 条边。因为算法每次都只在“端点不同分量”时才收边所以收下的边一定不会成环收到的边集合始终是一片森林当森林里有 n-1 条边时它必然已经覆盖全部 n 个节点此时再往后看任何一条边端点一定在同一分量里全部会被拒绝。提前退出省下的是“剩下那些边还要各查两次并查集”的开销在边数远大于 n 的稠密图上能省掉一大半时间。最后那行T T(1:cnt, :)处理的是不连通图。如果图本身不连通循环跑完也不会有cnt n-1此时T里后面那些预分配的行还是全零直接返回会让调用方以为存在一条0-0-0的边。砍掉之后调用方拿到的是“森林的边集”长度小于 n-1一眼就能看出图不连通。这种做法比抛异常温和也方便调用方自己决定是报错还是补边。提示如果你的输入保证连通可以省掉这行但建议保留——它几乎不花时间却能在数据出问题时给你一个明确的信号。3.4 结果回填与可视化拿到T之后画图通常用graph对象一步到位G graph(T(:,1), T(:,2), T(:,3), n); % 用生成树的边建图 p plot(G, EdgeLabel, G.Edges.Weight, Layout, force); highlight(p, EdgeColor, [0.85 0.33 0.10], LineWidth, 2); title(sprintf(MST 总权重 %.2f, sum(T(:,3))));graph的第四个参数是节点数一定要显式传n否则孤立节点会被自动丢弃画出来的图和原问题对不上。Layout选force是省事做法如果有真实坐标改成plot(G, XData, pos(:,1), YData, pos(:,2))更直观节点位置和实际地理位置对应给非技术同事看的时候说服力强很多。高亮那一步用highlight比重新plot一遍省事也不会把节点位置抖乱。边标签在边数超过三四十条时就会挤成一团这时候建议关掉EdgeLabel改成在图标题里写总权重——读者关心的是“省了多少”不是每条边的具体数值。4. 跑起来MATLAB 与开源替代环境的两条实操路径代码写完只是第一步能不能在别人机器上跑通是另一回事。这一章按“最少步骤跑出结果”和“跑出来怎么验”两条线走顺手把随机数据生成也讲了方便你自己造测试用例。4.1 最小可运行脚本把前面几个文件放在同一个目录新建一个脚本五行就能看到结果% demo_min.m —— 最小可运行示例 n 6; A zeros(n); % 手工构造一个带权无向图0 表示无边 A(1,2)4; A(2,1)4; A(1,3)1; A(3,1)1; A(2,3)2; A(3,2)2; A(2,4)5; A(4,2)5; A(3,5)8; A(5,3)8; A(4,5)3; A(5,4)3; A(4,6)7; A(6,4)7; A(5,6)6; A(6,5)6; edges adj2edges(A); [T, w] kruskal(edges, n); disp(T); fprintf(总权重 %.2f\n, w);adj2edges把对称矩阵削成 9 条候选边kruskal从中挑 5 条作为生成树总权重应该是 12367 19。如果你的输出不是这个数先别怀疑算法去检查A是不是严格对称——只要有一处只写了一边triu就会把它丢掉或者读错。手工构造这种小例子看着笨但它是唯一能让你在没有对拍工具时确认“算法真在按预期走”的办法。4.2 输入数据怎么造随机图与坐标图真实数据不好找的时候随机图是最省事的压力测试来源function [A, pos] build_random_graph(n, p, seed) % 生成 n 个点的随机连通图边存在概率 p if nargin 2, rng(seed); end pos rand(n, 2) * 100; % 随机坐标仅用于画图 D squareform(pdist(pos)); % 欧氏距离矩阵 A zeros(n); for i 1:n for j i1:n if rand p A(i,j) D(i,j); A(j,i) D(i,j); end end end % 补一条链保证连通否则 MST 收不满 n-1 条边 for i 1:n-1 if A(i,i1) 0 A(i,i1) D(i,i1); A(i1,i) D(i,i1); end end end最后那个补链的循环很关键。随机生成的图在p偏小的时候大概率不连通kruskal会老老实实返回一片森林你看着“边数不对”还以为算法坏了。补一条 1-2-3-…-n 的链之后图一定连通结果一定恰好 n-1 条边验证起来干净利落。pdist加squareform是 MATLAB 里算两两距离的标配组合返回的是完整对称矩阵。节点数上千时这个矩阵就是 8×10⁶ 个 double约 64MB还扛得住再往上就该改用稀疏表示或者直接按需计算距离别一次性铺开。4.3 输出怎么验三个必查项跑出结果之后至少检查三件事能挡掉九成的实现错误。第一边数。连通图上必须是 n-1 条。少了说明图不连通或者主循环提前退出的条件写错了多了说明去环逻辑失效。第二总权重对拍。如果环境里有minspantree直接比G graph(edges(:,1), edges(:,2), edges(:,3), n); Tb minspantree(G); fprintf(内置总权重 %.4f\n, sum(Tb.Edges.Weight)); fprintf(自实现总权重 %.4f\n, totalW);两个数在浮点误差范围内相等基本可以认为实现正确。这一步建议做成固定脚本而不是临时敲改完代码随手跑一遍比肉眼检查靠谱得多。第三连通性自检。把T的边重新建一个并查集走一遍最后数一数根节点个数等于 1 才算生成树parent 1:n; for k 1:size(T,1) [parent, ru] uf_find(parent, T(k,1)); [parent, rv] uf_find(parent, T(k,2)); if ru ~ rv [parent, ~] uf_union(parent, zeros(1,n), ru, rv); end end roots arrayfun((x) uf_find(parent, x), 1:n); fprintf(连通分量数 %d\n, numel(unique(roots(1,:))));这段自检代码看着有点绕但它不依赖任何工具箱在任何版本的 MATLAB 和开源替代环境里都能跑。写一次放那儿后面每次改完主函数都跑一遍心里踏实。5. 避坑与排查五个跑起来才会撞上的问题下面五条基本都是我在不同场合真实撞过或者见别人撞过的按“现象 → 原因 → 解决”记下来遇到时对号入座就行。5.1 现象结果总权重偏大生成树里出现了明显不该选的边原因几乎一定是并查集没生效。最常见的写法是ru uf_find(parent, u);漏掉了把返回的parent接回去。这样查找函数内部做的路径压缩全部丢失更致命的是合并时用的是旧的parent导致两个本该合并的集合没有真的合并后面判环全部失效算法退化成“随便挑边”。解决把所有uf_find调用改成[parent, ru] uf_find(parent, u);的形式uf_union同理。改完在一张小图上手工算一遍期望结果比对一下。这个坑太常见我现在写这类代码时会先写一个三节点的最小测试确认并查集行为正确再往上搭。5.2 现象边表里出现(i,i)自环或者每条边出现两次原因是从邻接矩阵转边表时直接用了find(A)而不是find(triu(A,1))。对称矩阵的每条边在对角线两侧各存一份find会把两份都取出来对角线上的非零值还会变成自环。解决统一走adj2edges不要在主函数里临时写find。如果你的矩阵不是严格对称手工录数据时很容易只写一边先做一次A max(A, A)把两边对齐再取上三角。自环本身在克鲁斯卡尔里会被并查集自然拒绝同一节点当然同分量不会算错但会让边数统计和调试输出变得难看早去早省心。5.3 现象图明明连通返回的边数却小于 n-1原因有两种。一是节点编号不连续比如输入用的是 0 到 n-1 或者带空洞的 ID而parent 1:n假设编号从 1 开始连续编号超范围的节点一访问就越界报错编号缺失的节点则永远孤立。二是图确实不连通比如随机生成时p太小又没补链。解决进主函数前加一句校验assert(all(edges(:,1:2) 1) all(edges(:,1:2) n) all(edges(:,1:2) fix(edges(:,1:2))))编号不合规立刻报错而不是算出个莫名其妙的结果。对不连通的情况主函数返回行数不足的T是合理行为调用方拿到后先判断size(T,1) n-1不满足就说明图有问题该补边补边该换数据换数据。5.4 现象换一份大一点的输入内存直接飙到几个 G原因是全程用稠密邻接矩阵。n 个节点就是 n² 个 doublen 到两万时单个矩阵就 3.2GB还没开始排序就已经把内存吃光了。解决节点数超过几千就改用稀疏矩阵或者直接构造边表。A sparse(i, j, w, n, n); A A A;之后adj2edges里的triu和find依然适用内存只和边数成正比。更进一步可以跳过矩阵直接从数据源拼出 m×3 的边表喂给kruskal——主函数本来就只认边表这条路一直是通的只是很多人习惯性地从矩阵入口进。5.5 现象同一份数据跑两次画出来的生成树不一样原因是权重存在大量相等值而排序不稳定或者数据本身有随机性比如用rand生成的位置每次不同。克鲁斯卡尔在权重相同时选哪条边不唯一总权重一样但树的形状可能不同这本身不是错误。解决想要结果可复现一是固定随机种子rng(42)二是排序用sort而不是其他不稳定实现三是比较结果时只比总权重和边数不要逐边比对。如果业务上确实要求“权重相同时按某种规则选”比如优先选小编号节点那就在排序前给边表加一列次级排序键用sortrows(edges, [3 1 2])按权重、起点、终点依次排。这个需求在小规模教学例子里不明显一旦上真实数据就会有人问“为什么两次结果不一样”提前想好怎么答。6. 二次开发从教学脚本改成能进项目的工具函数这套代码最容易停在一个尴尬位置能跑、能画图、能交作业但真要塞进别人的流程里就处处别扭。我一般会做三件事把它推到“能用”的水准。第一件是接口收敛。主函数签名保持[T, totalW] kruskal(edges, n)不变但加一个可选参数结构体把“是否返回并查集状态”“是否允许不连通”这类开关收进去function [T, totalW, info] kruskal(edges, n, opts) % opts.allowDisconnected : true 时不连通也返回森林默认 false % opts.returnComponent : true 时在 info 里返回每个节点的根 if nargin 3, opts struct(); end allowDisc getfield_default(opts, allowDisconnected, false); ... if cnt n - 1 ~allowDisc error(kruskal:disconnected, 图不连通只找到 %d/%d 条边, cnt, n-1); end这样默认行为是“不连通就报错”比返回一个长度不对的矩阵更容易在流水线里被发现需要宽容处理的场景显式打开开关。info里带上并查集的最终状态调用方可以顺手拿到连通分量划分做后续聚类或者分组不用再算一遍。第二件是对拍常态化。把verify_against_builtin.m改成脚本末尾自动跑的断言输入覆盖小图、稠密图、稀疏图、带重复权重的图四种情况每次改完主函数跑一遍全绿才算完cases {build_random_graph(8, 0.9, 1), build_random_graph(50, 0.3, 2), ... build_random_graph(200, 0.05, 3)}; for c 1:numel(cases) [A, ~] cases{c}; edges adj2edges(A); [~, w1] kruskal(edges, size(A,1)); G graph(edges(:,1), edges(:,2), edges(:,3), size(A,1)); w2 sum(minspantree(G).Edges.Weight); assert(abs(w1 - w2) 1e-9, 第 %d 组对拍失败%.6f vs %.6f, c, w1, w2); end第三件是把“必选边”这个真实需求考虑进去。工程上经常有“某几段管线已经建好必须包含在结果里”的情况做法是先把这些边强行合并进并查集并计入结果再从剩下的边里正常跑克鲁斯卡尔——注意这时候目标边数仍然是 n-1但初始cnt不再是 0。加这个功能只需要在主循环前插一段预合并改动不到十行却能让这份代码从“玩具”变成“能接需求”的东西。必须说一句这些改造里最值钱的不是功能而是对拍脚本。早年我改这类算法时习惯靠肉眼比对画出来的树觉得“形状差不多”就收工结果有一次在权重存在大量重复值的数据上总权重差了 0.3%画出来根本看不出来。从那以后我每次动排序或者并查集相关的代码都强制先把对拍脚本跑一遍再谈别的。希望这些经验帮到你少走一遍我当年绕的那段路。本文还有配套的精品资源点击获取