简介面向图论与网络优化学习者的克鲁斯卡尔算法 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可以理解为树高的上界合并时始终让秩小的根指向秩大的根只有秩相等时才把新根的秩加一。实现方式单次操作摊还复杂度说明只有 parent随便挂O(n)可能退化成链parent 按秩合并O(log n)树高被限制住parent 路径压缩O(log n) 摊还单次可能慢平均很快两者都用O(α(n))α 是反阿克曼函数实际 ≤ 4最后一行里的 α(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 三种图存储邻接矩阵、稀疏矩阵、边列表存储方式空间取「所有边」的代价适配度邻接矩阵 n×nO(n²)双重循环或find稠密小图尚可稀疏图会占满内存sparse稀疏矩阵O(nnz)find出三元组通用但多一次转换边列表 E×3O(E)直接读sortrows即排序克鲁斯卡尔算法最贴合克鲁斯卡尔算法的核心动作是「按权重升序遍历所有边」它根本不关心某个点的邻居是谁。所以边列表是天然选择一个 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的闭包——用嵌套函数勉强能改但一旦出问题调试器里看到的变量会藏得很深。真正能向量化的只有两处构造边列表用sparsefind批量生成和排序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 在 n10⁴ 时就是 800MB还没开始排序就先崩了。另一种情况是边列表用了 double 存节点编号E 大时也占不少。解决全程走稀疏或边列表永远不要full。节点编号用uint32存能省一半空间注意权重列仍要保持 double别把浮点权重转成整型截断。定位内存问题时在关键节点插whos看变量大小比在任务管理器里猜有效得多。5.5 递归版查根直接抛错现象递归实现的findroot在某些输入上报Maximum recursion limit reached。原因递归深度默认上限是 500图里出现长链时必然撞线。解决改成两趟迭代写法。用set(0,RecursionLimit,...)调高上限只是把问题往后推——链长等于 n 时迟早还会撞上而且深递归本身在 MATLAB 里就慢。6. 设计取舍什么时候该换 Prim以及怎么相信自己的实现克鲁斯卡尔算法和 Prim 都能求最小生成树选哪个不是偏好问题而是由图的稠密程度和已有的数据结构决定的对比项克鲁斯卡尔算法Prim复杂度O(E log E)邻接矩阵 O(n²)二叉堆 O(E log V)依赖结构并查集 一次全局排序优先队列或最小权数组稀疏图明显占优边少排序就便宜堆版本接近但常数更大稠密图要排 O(n²) 条边吃亏邻接矩阵版本几乎不用额外结构输出天然是最小生成森林不连通图直接可用需要额外判断连通性实现难点并查集的值语义、环检测堆的维护或数组的更新时机判断依据其实只有一个数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」的验证再往主流程里接。希望帮到你。本文还有配套的精品资源点击获取
