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=50 时邻接矩阵才 2500 个元素，怎么存都无所谓；n=5000 时邻接矩阵是 2500 万个数，光find一遍就吃掉几百 MB，而真实路网、通信网这类图边数往往只有节点的几倍，边表能把内存压下去两个数量级。所以比较稳的写法是：对外接口收邻接矩阵（用户方便），对内一律转边表（算法高效），并额外提供一个直接吃边表的入口，给稀疏图场景用。

还有一点要注意，转换的时候只取上三角：

[ii, jj] = find(triu(Wmat, 1)); % triu(...,1) 只保留主对角线以上

如果整张矩阵扫，无向图的每条边会算两次，边数翻倍。边数翻倍本身不致命，但后面排序多了近一倍元素，主循环也多跑一轮，属于白白浪费；更麻烦的是输出结果里可能出现(3,7)和(7,3)同时被打印出来，看起来像算法出了 bug。

2.3 并查集为什么不能省：每次做连通性检查会怎样

新手最容易写出的版本是：每挑一条边，就用 BFS 或者连通分量矩阵判断两个端点是不是已经连通。n 个点、k 条边，每判断一次要 O(n+k)，总体复杂度 O(k·(n+k))，完全图下 k=n²，直接退化成 O(n³) 以上。n=200 的完全图就要跑上千万次操作，MATLAB 这种解释执行环境下会明显感觉到卡。

并查集把这一步压到近似 O(α(n))，α 是阿克曼函数的反函数，n 在现实规模内几乎不超过 4。代价是多维护两个长度 n 的数组，几乎可以忽略。所以这不是「优化技巧」，而是这个算法的标准配置——没有并查集的克鲁斯卡尔只能叫「按边排序的贪心尝试」。

这里有个 MATLAB 特有的坑必须提前说清楚：MATLAB 函数参数是按值传递，函数内部改parent数组，调用方的parent一个字节都不会变。所以并查集的find必须写成[root, parent] = uf_find(parent, x)，把压缩后的数组返回出去。第一次写的人十个里有八个会漏返回值，然后发现路径压缩完全没生效，跑得比预期慢，还找不到原因。

2.4 输入输出接口约定：先把契约写死

接口约定清楚了，后面二次开发才不会互相打架。这份代码的约定是：

用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 end

function [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(end+1,:) = ...快得多，后者每次扩容都要重新分配内存，节点数上千时差距明显。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 = i+1: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)/2，n=200 就是将近两万条边，排序和主循环会开始有感。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 对答案

较新版本的 MATLAB（R2015b 及以后）自带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 到几百就明显变慢

如果n=300的完全图要跑好几秒，先看三处。一是T(end+1,:) = ...有没有改成预分配，这是最常见的性能黑洞；二是uf_find是不是写成了递归，MATLAB 的函数调用开销在深链上很难看；三是边表构建有没有用arrayfun，改用sub2ind一次性取下标能快一个数量级。

还有一处容易被忽略：sort排的是w，但主循环里每次要用order(k)反查ii、jj、w，如果w是从矩阵里临时算出来的（比如每次循环重算距离），开销会翻倍。正确做法是排序前就把w固化成数组，循环里只做下标访问。

6. 二次开发：换算法、加约束和随机对照验证的三个改造方向

代码跑通只是起点，多数人拿到它是要改的。三个方向最常用。

换算法做对比。稠密图场景下 Prim 往往更快，因为它是按点扩展，不需要对全部边排序。改造位置很集中：保留kruskal_mst.m的输入校验和输出封装，把中间的排序和主循环换成「维护一个已选点集 + 一个候选边最小堆」。MATLAB 没有原生堆，用sort每次取最小也行，n 不大时够用。改完拿同一份D分别喂给两个函数，比总权重和运行时间。

加约束是克鲁斯卡尔最舒服的地方。比如布线场景要求某两个机房之间必须直连，做法不是改算法，而是在主循环之前先把这条边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 = i+1: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结构直接乱掉，而算法还不报错——只是结果偏小。那之后我每次改图算法的入口，不管多小的例子，都强制先跑一遍随机对照，再手算一两个小图确认输出格式，两关都过了才往下写。希望帮到你。

本文还有配套的精品资源，点击获取