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 数据入口：邻接矩阵、边表、坐标三种输入怎么统一

实际用起来，输入数据基本就三种形态，处理方式不一样：

统一到边表之后，主函数就只认一种格式：一个 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 （端点不同分量时调用一次） └─ 返回 T（n-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]; end

triu(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, :); % 图不连通时把预分配多出来的零行砍掉 end

cnt == 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 条作为生成树，总权重应该是 1+2+3+6+7 = 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 = i+1: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,i+1) == 0 A(i,i+1) = D(i,i+1); A(i+1,i) = D(i,i+1); 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² 个 double，n 到两万时单个矩阵就 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%，画出来根本看不出来。从那以后我每次动排序或者并查集相关的代码，都强制先把对拍脚本跑一遍再谈别的。希望这些经验帮到你，少走一遍我当年绕的那段路。

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