简介：面向图论与网络优化学习者的克鲁斯卡尔算法 MATLAB 实现代码包，聚焦加权无向图最小生成树的构建，适合算法课程实验、课程设计及网络设计入门练习。压缩包内共 4 个 .m 源文件，整体约 2KB，体积轻便，内容围绕边集提取、按权重排序、并查集查找与合并、连通分量判断及成环检测等核心环节展开，可帮助读者理解从邻接矩阵输入到最小生成树输出的完整实现路径。已有 409 人学习，说明其在 MATLAB 图论算法练习中具有一定参考价值。主函数与辅助操作分模块组织，便于对照算法步骤阅读、调试和二次修改；读者可据此完成小规模图的最小生成树求解，并扩展测试用例，观察不同图结构下的边选择过程，积累并查集与贪心策略的排错经验。

1. 克鲁斯卡尔算法：为什么先把所有边排一遍，反而更省事

克鲁斯卡尔（Kruskal）算法在 matlab 里的实现，短得有点反直觉：几十行代码就能算完最小生成树，而且没有递归回溯、没有邻接表遍历、没有优先队列。它的全部动作只有三步——把边按权重排一次序，从小到大逐条试，用并查集判断两端是否已经连通。真正让人卡住的，从来不是这个算法本身复杂，而是三件琐事：边怎么存、排序之后怎么判断是否成环、循环什么时候能提前结束。把这三件事想清楚，你再看任何一份 matlab 克鲁斯卡尔代码，都能一眼看出它有没有在稠密图上运行很多无用步骤。

2. 割性质与环性质：贪心为什么不会走进死胡同

克鲁斯卡尔算法被归入贪心算法这一类。贪心算法最容易被怀疑的一点是：局部最优真的能堆出全局最优吗？对最小生成树来说，答案是能，而且理由只有两条，它们分别是割性质和环性质。理解这两条性质，比记住算法流程重要得多，因为它们是后面所有实现细节的判断依据。

2.1 割性质：横跨一个割的最小边一定属于某棵最小生成树

把一个图的点集拆成两部分 S 和 V\S，所有一端在 S、另一端在 V\S 的边，就构成横跨这个割的边集。割性质说：这个集合里权重最小的那条边，一定存在一棵最小生成树（下称 MST）包含它。

证明思路不复杂，但值得走一遍：设 e 是横跨该割的最小边，T 是任意一棵 MST。如果 e 已经在 T 里，结论成立；如果不在，把 e 加进 T 必然形成一个环，而这个环上一定还有另一条横跨同一个割的边 f——因为要走回 S 那一侧，环必须再次跨过割。由 e 的最小性有 w(f) ≥ w(e)，于是用 e 换掉 f，得到的仍然是一棵生成树，总权重不变差。这个交换论证的关键在于「跨割」这个条件：它保证了 f 一定存在、且和 e 不同，换边之后树依然合法。

2.2 环性质：两端已连通就必须跳过

环性质是割性质的镜像：如果一条边加入当前森林后会成环，那它一定不是必需的，环上权重最大的那条边可以被它替换。克鲁斯卡尔算法按权重升序处理边，所以当它遇到一条两端已经连通的边时，说明之前已经用权重更小或相等的边把这两点连起来了，再纳入这条边只会制造环、不会降低总权重。

这两条性质合起来，恰好对应算法里的两个动作。第一，排序对应割性质——保证每次考虑的是当前最小的候选边，选出的边是横跨当前某个割的最小边，因此加入它是安全的。第二，并查集对应环性质——保证只在不同分量之间加边，永远不会闭合。算法里没有回溯、没有启发式，正确性完全由这两条性质支撑。

2.3 从证明到可执行判据：环检测其实只问一句话

把上面的证明写成代码，判断条件只有一句：find(u) == find(v)。既不需要真的在图上做深度优先搜索找环，也不需要维护邻接表，只需要维护「每个点当前属于哪个集合」。

这里有一层容易被忽略的推理：为什么克鲁斯卡尔算法选出的边一定是「横跨当前分量这个割的轻边」？关键在于并查集的分量是单调合并的——两个集合一旦合并，就再也不会拆开。假设存在一条横跨当前分量 C 的边 f，且 w(f) < w(e)，那么 f 在 e 之前就被处理过；处理 f 时它的两端必然分属不同分量（因为 f 的另一端不在 C 里，而那时 x 所在的分量还是 C 的子集），因此 f 会被接受，两端就此连通，这又与「另一端不在 C 里」矛盾。所以 e 确实是横跨该割的最小边。这条单调性，正是我后面反复强调「并查集只能合不能拆」的原因。

如果把这个判据用最朴素的写法实现，也可以：给每个点存一个集合标签，合并时把一边所有点的标签刷成另一边的。在小图上它跑得动，代价是每次合并 O(n)、总复杂度 O(n²)。并查集做的，就是把这次 O(n) 的全量刷标签，压成近似 O(1) 的两次指针跳转。

3. 并查集：环检测的复杂度怎么压到近似常数

并查集（Union-Find）是克鲁斯卡尔算法里唯一需要设计的数据结构。它只支持两个操作：查某个点的根，把两个集合合并。看起来简单得很，但实现得好与不好，在百万级边上的耗时能差出一个数量级。

3.1 parent 数组：把「是否同集合」变成「根是否相同」

标准的表示法是把每个集合组织成一棵树：parent(i) 存 i 的父节点，根节点的 parent 指向自己。查根就是从 i 一路向上走，直到 parent(r) == r；判断两个点是否同集合，就是比较它们走到的根是否相同；合并两个集合，就是把一棵树的根挂到另一棵树的根下面。

这个结构只用一个长度为 n 的整型数组，空间是 O(n)，比邻接表还省。它之所以适配克鲁斯卡尔算法，是因为算法整个过程中只需要回答一个问题——「u 和 v 现在连通吗」，而这个问题被 parent 数组压缩成了「往上走到根，看是不是同一个」。

3.2 路径压缩与按秩合并：两招把树高压下去

朴素的并查集有一个明显的弱点：如果一直把大树挂到小树下面，树会退化成一条链，单次查根变成 O(n)。两种优化分别从不同方向解决它。

路径压缩的思路是「顺手把路修平」：第一次查根要走 k 步，那就在返回之前把路径上所有点直接挂到根上，以后再查任何一点都只要一步。按秩合并的思路是「矮的挂高的」：额外维护一个秩（rank，可以理解为树高的上界），合并时始终让秩小的根指向秩大的根，只有秩相等时才把新根的秩加一。

最后一行里的 α(n) 增长极慢，在可想象的任何输入规模下都不超过 4。也就是说，当节点数、边数达到亿级时，并查集这部分的开销已经可以忽略，真正决定运行时间的是排序。

3.3 MATLAB 实现：值语义与 1-based 索引是主要的坑

先看显式传参的版本，这也是最容易做单元测试的写法：

function [root, parent] = uf_find(parent, x) % 迭代版查根 + 路径压缩，两趟走完 r = x; while parent(r) ~= r r = parent(r); % 第一趟：一路向上找到根 end while parent(x) ~= r nxt = parent(x); % 先存下原来的父节点，否则会被覆盖 parent(x) = r; % 第二趟：把路径上的点直接挂到根 x = nxt; end root = parent; % 占位，见下方说明 root = r; end

上面这段代码第 9、10 行是我故意写出来的反例，正确写法只保留root = r;。parent在函数内部被修改后，必须由调用方接收返回值才能生效——MATLAB 的参数是值传递（写时复制），函数里改parent不会影响外面的变量。这一点是所有 matlab 版并查集最容易踩的坑：代码看起来路径压缩执行了，实际上回到主循环后parent还是旧的，树高根本没有下降。

节点编号从 1 开始也很关键。parent = 1:n是正确的初始化，千万不要为了「和 C 语言对齐」写成0:n-1，再用 0 当哨兵值——MATLAB 里parent(0)会直接报索引错误，而且zeros初始化出来的 0 会被误判成「指向 0 号节点」。

3.4 嵌套函数还是返回值：一个真实的作用域取舍

既然值语义这么麻烦，另一条路是把并查集写成主函数里的嵌套函数。嵌套函数和父函数共享工作区，可以直接改parent、rnk，一次返回值都不用写：

function [T, w] = kruskal_nested(n, edges) parent = 1:n; rnk = zeros(1, n); edges = sortrows(edges, 3); % 嵌套函数能读到 edges function r = findroot(x) r = x; while parent(r) ~= r r = parent(r); end while parent(x) ~= r nxt = parent(x); parent(x) = r; % 直接改父作用域的 parent x = nxt; end end % 主循环里直接调用 findroot 即可，parent 会被就地更新 end

代价是作用域被污染：parent、rnk、edges全都暴露在同一个工作区里，调试时想看中间状态，得在父函数里打断点；而且含嵌套函数的文件里，所有函数都必须用end收尾，风格上不能混。我的习惯是：原型阶段用嵌套函数，图快；一旦这份代码要给别人用或者要写测试，就切回显式传参——多写几个返回值，换来的是每个函数都能单独调用、单独验证。

3.5 递归还是迭代：一个会被规模直接放大的选择

有些实现把查根写成递归，逻辑更短，但在 MATLAB 里有明确的代价。递归深度默认受RecursionLimit限制（默认 500），当图里出现一条长链时，递归版会直接抛出「Maximum recursion limit reached」；即便手动调高限制，MATLAB 的函数调用开销本来就比 C 大，深递归在百万级边上会明显拖慢整体。

所以路径压缩一律写成两趟迭代：第一趟只找根，第二趟再压缩。第一趟不能省，因为压缩时必须知道根是谁；两趟写法的额外开销只是多走一遍同一条路径，比递归的栈开销便宜得多。

4. 从边列表到能跑的代码：MATLAB 里的数据结构与主循环

算法想清楚了，剩下的是工程问题：图用什么存、排序怎么排、循环怎么写才不会把时间浪费在无用的迭代上。这三件事在 MATLAB 里有很具体的答案。

4.1 三种图存储：邻接矩阵、稀疏矩阵、边列表

克鲁斯卡尔算法的核心动作是「按权重升序遍历所有边」，它根本不关心某个点的邻居是谁。所以边列表是天然选择：一个 E 行 3 列的矩阵，每行[u v w]，sortrows排一次就完成了算法里唯一的全局预处理。如果手上拿到的是邻接矩阵，先用sparse转成稀疏形式，再用find取三元组，避免full把内存打满。

4.2 sortrows 的排序细节与权重并列

sortrows(edges, 3)按第 3 列升序排，这是克鲁斯卡尔算法的第一步，也是复杂度里唯一超过线性的部分：O(E log E)。这里有一个必须讲清楚的事实——MST 不唯一。当图里存在权重相同的边时，不同的处理顺序会得到形态不同的生成树，但总权重相同。所以如果你的结果和某份「标准答案」边集对不上，先比总权重，别急着怀疑代码。

需要确定性输出时（比如做回归测试），把排序键写全：sortrows(edges, [3 1 2])，权重相同的边再按端点编号排，这样同一个输入永远得到同一个输出。另外，边列表里出现自环u == v不会造成问题——查根时两端必然相同，会被直接跳过；重边也不需要预先去重，第二条会被并查集自动判掉。

4.3 主循环：预分配、提前退出、连通性判定

function [T, totalW, connected] = kruskal_mst(n, edges) % KRUSKAL_MST 并查集版最小生成树 % 输入 n : 节点数，节点编号 1..n % 输入 edges : E×3，每行 [u v w] % 输出 T : 被选中的边，k×3 % 输出 totalW: 最小生成树（或森林）的总权重 % 输出 connected : 图是否连通，false 表示只能得到最小生成森林 edges = sortrows(edges, [3 1 2]); E = size(edges, 1); parent = 1:n; rnk = zeros(1, n); T = zeros(n - 1, 3); % 生成树最多 n-1 条边，一次预分配 k = 0; totalW = 0; for i = 1:E u = edges(i, 1); v = edges(i, 2); w = edges(i, 3); ru = findroot(u); rv = findroot(v); if ru == rv continue; % 成环，丢弃 end if rnk(ru) < rnk(rv) % 按秩合并：矮树挂高树 tmp = ru; ru = rv; rv = tmp; end parent(rv) = ru; if rnk(ru) == rnk(rv) rnk(ru) = rnk(ru) + 1; end k = k + 1; T(k, :) = edges(i, :); totalW = totalW + w; if k == n - 1 break; % 已够 n-1 条，剩下的边不用再看 end end T = T(1:k, :); connected = (k == n - 1); function r = findroot(x) r = x; while parent(r) ~= r r = parent(r); end while parent(x) ~= r nxt = parent(x); parent(x) = r; x = nxt; end end end

几个参数和写法值得单独说明。edges的列顺序是硬约定，sortrows的列索引、主循环里edges(i,1)的取值都依赖它，换个顺序就得改三处，很容易漏改。T预分配n-1行是因为生成树最多就这么多边，反复T = [T; ...]会让 MATLAB 每轮重新分配内存，边多了以后耗时曲线会明显变陡。break条件是k == n - 1而不是k == n，这是差一错误的高发地：n 个点的树恰好 n-1 条边，取到 n 条必然成环。最后的connected用边数判断，比再跑一次连通性遍历便宜得多，也顺手把「最小生成森林」这个更容易被忽略的输出暴露出来。

复杂度上，排序 O(E log E) 是主导项，并查集部分 O(E·α(n)) 可以忽略，空间则是 O(n + E)。这也解释了为什么克鲁斯卡尔算法在稀疏图上表现很好：边少，排序就便宜。

4.4 向量化的边界：主循环不要硬套 arrayfun

有人看到 for 循环就想换成arrayfun，抱着血泪经验说一句：这里不行。克鲁斯卡尔算法的每一步都依赖上一步的并查集状态，本质是串行的，arrayfun只是把 for 写成了函数调用形式，内部照样逐个执行，而且回调函数的调用开销比直接 for 更大。更麻烦的是parent这种共享状态没法干净地穿过arrayfun的闭包——用嵌套函数勉强能改，但一旦出问题，调试器里看到的变量会藏得很深。

真正能向量化的只有两处：构造边列表（用sparse+find批量生成）和排序（sortrows本身就是向量化的）。主循环保持 for，现代 MATLAB 的 JIT 对定长循环已经优化得不错，没必要为了「看起来向量化」牺牲可读性和正确性。

5. 常见问题排查：MATLAB 版克鲁斯卡尔算法最容易出错的几处

5.1 选出的边数不到 n-1，代码却不报错

现象：输入几十条边，最后只选出 5 条，totalW却正常返回，看不出任何异常。

原因：图本身不连通。克鲁斯卡尔算法在不连通图上得到的是最小生成森林，k永远到不了 n-1。常见诱因是节点编号不连续（中间缺了编号）、边列表里混进了超出 1..n 的编号，或者从某个子图导出的边列表根本没覆盖全部点。

解决：入口处先做两件事——max(edges(:,1:2))检查编号上界，numel(unique(edges(:,1:2)))检查覆盖点数是否等于 n。然后把connected显式返回，让调用方自己决定这是「正常结果」还是「输入有问题」，而不是让一个静默的错误答案流到下游。

5.2 路径压缩写了，树高却没降下来

现象：findroot里明明有压缩逻辑，但给并查集加个计数器观察，发现每次查根的步数还是和没压缩一样。

原因：MATLAB 值传递。函数内部改parent只改了副本，函数返回后外部变量原封不动。表现上就是「代码看着对，行为完全不对」，属于典型的黑匣子式困惑。

解决：二选一——把parent作为返回值显式接出去并在调用处覆盖，或者改成嵌套函数共享工作区。选完之后做个最小验证：初始化一条长度为 5 的链，查一次尾部节点，然后打印parent，看中间节点是不是都指向了根。这个两行验证能省掉后面几小时的排查。

5.3 结果和参考实现对不上，边集不同

现象：换个输入，自己的实现和某份参考代码选出的边不一样，权重和却相同。

原因：MST 不唯一。权重并列时，处理顺序不同就会得到不同形态的树。这是数学性质，不是 bug。

解决：断言比总权重，不比边集合。确实需要逐边对比时，先把边列表按完整键排序（sortrows(edges,[3 1 2])）固定住并列边的次序，再比。

5.4 节点规模上一万，内存就爆

现象：n 到 10⁴、E 到 10⁵ 时内存占用飙升，甚至直接 out of memory。

原因：多半是在某一步用了full把稀疏邻接矩阵转成了稠密矩阵，n×n 的 double 在 n=10⁴ 时就是 800MB，还没开始排序就先崩了。另一种情况是边列表用了 double 存节点编号，E 大时也占不少。

解决：全程走稀疏或边列表，永远不要full。节点编号用uint32存能省一半空间（注意权重列仍要保持 double，别把浮点权重转成整型截断）。定位内存问题时，在关键节点插whos看变量大小，比在任务管理器里猜有效得多。

5.5 递归版查根直接抛错

现象：递归实现的findroot在某些输入上报Maximum recursion limit reached。

原因：递归深度默认上限是 500，图里出现长链时必然撞线。

解决：改成两趟迭代写法。用set(0,'RecursionLimit',...)调高上限只是把问题往后推——链长等于 n 时，迟早还会撞上，而且深递归本身在 MATLAB 里就慢。

6. 设计取舍：什么时候该换 Prim，以及怎么相信自己的实现

克鲁斯卡尔算法和 Prim 都能求最小生成树，选哪个不是偏好问题，而是由图的稠密程度和已有的数据结构决定的：

判断依据其实只有一个数：E 和 n log n 的关系。当 E 接近 n²（稠密图），克鲁斯卡尔算法的排序会成为瓶颈，而 Prim 的邻接矩阵版本完全不碰排序；当 E 接近 n（稀疏图），比如路网、电路连线、聚类里的近邻图，克鲁斯卡尔算法的 O(E log E) 明显更省，而且它能直接返回最小生成森林，省掉一次连通分量计算。

至于怎么确认自己的实现没错，我习惯跑三重验证。先用小规模随机图对拍：造 20 个点、边权取 1 到 5 的随机整数，把自己的结果和 MATLAB 自带的minspantree(graph(...))比总权重，几十次随机输入就能把大部分逻辑错误逼出来。再查不变量：结果必须是 n-1 条边、必须无环、每条边的两端在加边时刻必须分属不同分量。最后压规模看行为：把 n 从 100 加到 10⁴，观察耗时曲线是否接近 E log E 的形状，如果提前出现陡坡，多半是某处预分配漏了。

踩过的坑里，最贵的一次不是算法写错，而是并查集的值语义问题——代码看起来每一步都在压缩路径，实际上压缩结果全丢在函数里，树一直退化成链，小图上看不出差别，规模一上来耗时直接数量级跳变，还找不到原因。从那以后我每次写并查集，都强制先用一条 5 个点的链做一次「压缩后打印 parent」的验证，再往主流程里接。希望帮到你。

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