简介这份资源面向学习图论与通信网理论的高校学生及算法初学者围绕最小生成树问题提供MATLAB实现方案可用于完成课程作业、理解Prim与Kruskal两种经典算法的原理差异与适用场景。压缩包共2个文件包含1个m脚本文件与1个pdf文档前者为可直接运行的算法代码后者用于说明算法思路与实现细节整体约25KB轻量便于快速上手。资源以通信网理论作业3为背景涉及邻接矩阵与邻接表的数据结构选择、并查集维护连通性、边权排序与环路检测等编程要点读者可据此对给定网络图数据构造最小生成树并验证结果进而掌握图遍历与数据结构设计的实践技巧。目前已有4806人学习下载适合希望用MATLAB动手复现算法、巩固图论基础的读者参考。1. 从一次通信网作业说起Prim 与 Kruskal 的最小生成树 MATLAB 实现带权无向图里找一棵连接所有节点、总权重最小的树这件事在通信网规划、布线成本估算、聚类预处理里反复出现。这次拆的资源是一份通信网理论作业包里面包含minspantree.m脚本和一份minspantree.pdf说明文档核心就是用 MATLAB 把 Prim 和 Kruskal 两种最小生成树算法各写一遍。它适合正在上通信网理论、图论或数据结构课的学生也适合需要快速验证网络拓扑最小代价的工程师。资源本身不大但两种算法的实现思路、数据结构选型和边界处理都压在了一个脚本里拿来当模板改比从零写省事得多。下面按「算法怎么落地 → 代码怎么跑 → 坑在哪」的顺序拆开讲。2. Prim 算法落地从邻接矩阵到逐步生长2.1 为什么 Prim 适合稠密图Prim 的思路是从一个起点开始每次把「离当前树最近」的那个外部顶点拉进来直到所有顶点入树。它的复杂度在朴素实现下是 O(n²)n 是顶点数跟边数关系不大。这意味着当图比较稠密、边数接近 n² 时Prim 不会因为边多而变慢反而邻接矩阵遍历起来很规整。通信网里节点之间常常两两可达邻接矩阵天然合适。反过来说如果图很稀疏邻接矩阵里大量 Inf 参与比较浪费计算。这时候要么换邻接表要么直接上 Kruskal。选型的第一条判断就是看边密度边数 m 远小于 n² 走 Kruskal接近 n² 走 Prim。MATLAB 里没有内置的优先队列朴素 Prim 用两个数组就能实现key存每个顶点到当前树的最小边权parent存这条边连的是树里哪个顶点。每轮扫描key找最小值O(n) 一轮总共 O(n²)。2.2 Prim 的 MATLAB 实现下面这段是常见的朴素 Prim 写法输入邻接矩阵WInf表示两点不直接相连输出parent和总权重totalWeight。function [parent, totalWeight] primMST(W) n size(W, 1); key inf(1, n); % 各顶点到当前树的最小边权 parent zeros(1, n); % 最小生成树的父节点 inMST false(1, n); % 标记顶点是否已入树 key(1) 0; % 从顶点1出发 parent(1) -1; for count 1:n % 找未入树中 key 最小的顶点 minVal inf; u -1; for v 1:n if ~inMST(v) key(v) minVal minVal key(v); u v; end end if u -1 error(图不连通无法生成最小生成树); end inMST(u) true; % 用 u 更新邻居的 key for v 1:n if W(u, v) 0 W(u, v) inf ~inMST(v) W(u, v) key(v) key(v) W(u, v); parent(v) u; end end end totalWeight sum(key); end逻辑上分三步初始化把起点key设为 0保证第一轮选中它主循环每轮选一个key最小的未入树顶点u标记入树然后用u的所有邻边去松弛外部顶点的key。parent(v) u记录的是「v 是通过 u 接进树的」最后顺着parent就能还原整棵树。参数上要注意两点。一是W(u,v) 0这个判断如果图里允许零权边得改成W(u,v) 0并单独处理对角线。二是key(1) 0让起点第一轮必被选中但totalWeight sum(key)会把起点的 0 也算进去结果不受影响因为 0 不改变总和。如果起点不是 1改key(start) 0即可。2.3 用邻接表改造的时机当 n 上千、边又稀疏时上面每轮 O(n) 扫描key会拖慢整体。常见做法是把key的更新和取最小改成用 MATLAB 的sort配合索引数组或者干脆用graph对象加minspantree内置函数做对照验证。自己手写邻接表版本时用一个 cell 数组存每个顶点的邻居和权重主循环里只遍历当前顶点的邻居能把内层从 O(n) 降到 O(deg(u))。不过作业规模一般几十个节点朴素版足够先跑通再谈优化。3. Kruskal 算法落地边排序加并查集判环3.1 为什么 Kruskal 适合稀疏图Kruskal 完全换了个视角不管顶点先把所有边按权重升序排好从小到大逐条尝试加入只要这条边的两个端点当前不在同一个连通分量里就收进最小生成树。判断「是否同分量」靠并查集接近 O(1) 摊还。整体复杂度由排序主导O(m log m)m 是边数。边少的时候这个量级很舒服所以稀疏图优先 Kruskal。两种算法的适用边界可以这样记Prim 围着顶点转稠密图省事Kruskal 围着边转稀疏图省事。两者结果的总权重一定相同但选出的边集可能不同因为最小生成树不唯一存在等权边时。3.2 并查集的 MATLAB 写法并查集用两个数组parentUF记录每个元素的父节点rankUF记录秩用于按秩合并。查找时做路径压缩。function root ufFind(parentUF, x) % 路径压缩查找 while parentUF(x) ~ x parentUF(x) parentUF(parentUF(x)); x parentUF(x); end root x; end function [parentUF, rankUF] ufUnion(parentUF, rankUF, x, y) rx ufFind(parentUF, x); ry ufFind(parentUF, y); if rx ry return; % 已在同一集合合并无意义 end if rankUF(rx) rankUF(ry) parentUF(rx) ry; elseif rankUF(rx) rankUF(ry) parentUF(ry) rx; else parentUF(ry) rx; rankUF(rx) rankUF(rx) 1; end endufFind里的parentUF(x) parentUF(parentUF(x))是路径压缩的关键把链上节点直接挂到祖父上后续查找更快。ufUnion按秩合并避免树退化成链。这两个函数是 Kruskal 判环的核心单独存成文件或写成局部函数都行。3.3 Kruskal 主流程与边表构建MATLAB 里邻接矩阵转边表用find取上三角避免重复边。function [edgesMST, totalWeight] kruskalMST(W) n size(W, 1); % 取上三角非零非Inf元素构建边表 [u, v, w] [rows, cols] find(triu(W) 0 triu(W) inf); weights arrayfun((r, c) W(r, c), rows, cols); edges [rows, cols, weights]; % 按权重升序排序 [~, idx] sort(edges(:, 3)); edges edges(idx, :); % 初始化并查集 parentUF 1:n; rankUF zeros(1, n); edgesMST []; totalWeight 0; for i 1:size(edges, 1) u edges(i, 1); v edges(i, 2); w edges(i, 3); if ufFind(parentUF, u) ~ ufFind(parentUF, v) [parentUF, rankUF] ufUnion(parentUF, rankUF, u, v); edgesMST [edgesMST; u, v, w]; totalWeight totalWeight w; if size(edgesMST, 1) n - 1 break; % 已够 n-1 条边 end end end if size(edgesMST, 1) n - 1 error(图不连通无法生成最小生成树); end endtriu(W) 0 triu(W) inf同时过滤掉下三角重复边、零权对角线和无穷远边。sort返回排序后的索引idx用它重排整个边表保证 u、v、w 对应关系不乱。主循环里每次取一条边查两端根节点不同就合并并收边收到 n-1 条提前退出。最后那个连通性检查别省不连通图会静默少边加个报错能省很多排查时间。参数上如果图里有负权边triu(W) 0会漏掉它们得改成triu(W) ~ 0 triu(W) inf。零权边同理。作业数据一般非负但改别人代码时这是高频翻车点。4. 两种算法对照验证结果对不对怎么查4.1 用内置函数做交叉验证MATLAB 的graph对象自带minspantree拿它当参照最省事。% 假设 W 是邻接矩阵 G graph(W, upper); % 只取上三角避免重复边 T minspantree(G); refWeight sum(T.Edges.Weight); [~, wPrim] primMST(W); [~, wKruskal] kruskalMST(W); fprintf(内置: %.4f, Prim: %.4f, Kruskal: %.4f\n, ... refWeight, wPrim, wKruskal);三个总权重应该完全相等。如果 Prim 和 Kruskal 一致但跟内置对不上多半是边表构建时把某条边算重或漏了如果两者之间就不一致优先查并查集合并逻辑和 Prim 的松弛条件。graph(W, upper)的upper参数告诉它只读上三角跟前面 Kruskal 的边表构建口径一致避免重复边导致权重翻倍。4.2 小规模手算用例拿一个 4 节点图验证最稳顶点 1-2 权 12-3 权 23-4 权 31-4 权 41-3 权 5。手算最小生成树是 1-2、2-3、3-4总权重 6。把邻接矩阵填进去跑两个函数输出不是 6 就说明实现有问题。这种用例的好处是能一眼看出选错哪条边比随机大图好定位。提示验证时把parent或edgesMST打印出来对照手算的边集别只看总权重。等权边存在时总权重对但边集不同是正常的不算 bug。4.3 复杂度实测的简单办法想直观感受两种算法在稠密和稀疏下的差异用tic/toc包住调用构造两组图一组 n50 全连接一组 n50 但每个节点只连 3 个邻居。前者 Prim 通常更快后者 Kruskal 占优。注意 MATLAB 的循环开销大小规模下差异可能被解释器吃掉n 至少上百才有参考意义。作业规模不用纠结这个理解边界即可。5. 避坑与常见问题排查5.1 图不连通导致死循环或报错现象Prim 跑到某轮找不到key有限的顶点u保持 -1Kruskal 跑完边表但边数不足 n-1。 原因图本身不连通不存在覆盖所有顶点的生成树。 解决Prim 里加if u -1判断并报错Kruskal 末尾检查size(edgesMST,1) n-1。别让程序静默返回半棵树。5.2 邻接矩阵对角线非零污染结果现象总权重偏大多出几条自环边。 原因邻接矩阵对角线填了 0 以外的值或者find没排除对角线。 解决构建边表时用triu取上三角天然排除对角线Prim 松弛时加u ~ v判断。填矩阵时对角线统一置 0 或 Inf。5.3 Inf 参与比较引发意外现象Prim 里key更新后出现 Inf 被当成有效最小值或 Kruskal 边表混入 Inf 权重的边。 原因MATLAB 里Inf Inf为假但Inf和有限值比较逻辑要小心边表过滤条件写漏。 解决边表构建用triu(W) inf明确排除Prim 松弛条件里W(u,v) inf不能省。所有涉及 Inf 的比较都显式写出来。5.4 并查集路径压缩写错导致判环失效现象Kruskal 收进了会成环的边边数超过 n-1 或总权重偏大。 原因ufFind里压缩逻辑写错根节点查找返回了非根或ufUnion忘了先查根就合并。 解决ufFind返回前确认parentUF(x) xufUnion开头必须先ufFind两端再比较。写完拿两节点合并一次、再查一次验证。5.5 中文注释乱码现象脚本在 MATLAB 里打开中文注释变成问号或方块。 原因文件编码和 MATLAB 当前编码不一致常见于 GBK 与 UTF-8 混用。 解决用feature(DefaultCharacterSet)查看当前编码把脚本另存为对应编码或统一转成 UTF-8 并在较新版本里设置。作业提交前在目标机器上打开确认一遍别等老师那边显示乱码。6. 把脚本改成通用工具的几个技巧跑通作业只是起点把minspantree.m改成能复用的工具更值。第一个技巧是统一输入输出接口两个函数都接受邻接矩阵、都返回边表和总权重这样上层调用不用关心用的哪种算法。我一般会再包一层solveMST(W, method)method传prim或kruskal内部switch分发方便对照。第二个技巧是加输入校验。检查矩阵是否方阵、是否对称、对角线是否为零不满足就报明确错误。通信网作业的数据偶尔是手填的对称性出错很常见早报错早改。function validateGraph(W) n size(W, 1); assert(size(W, 2) n, 邻接矩阵必须是方阵); assert(isequal(W, W), 邻接矩阵必须对称); assert(all(diag(W) 0), 对角线必须为0); endisequal(W, W)检查对称diag(W) 0检查对角线。这两个断言能挡掉大部分脏数据。注意浮点权重下isequal可能因精度失败必要时改成norm(W - W, fro) 1e-9。第三个技巧是可视化。用graph加plot把原图和最小生成树画在一起边权标出来一眼能看出选边是否合理。G graph(W, upper); T minspantree(G); figure; p plot(G, EdgeLabel, G.Edges.Weight); highlight(p, T, EdgeColor, r, LineWidth, 2); title(最小生成树红色边);highlight把生成树的边标红加粗对照原图检查有没有漏掉更短的连接。等权边多的时候图上看比看数字直观。最后一个习惯每次改完算法先跑那个 4 节点手算用例再跑内置minspantree对照两个都过才拿去跑真实数据。从那以后我每次动图算法代码都强制走一遍「手算小例 内置对照」这两步省下过不少返工。希望帮到你。本文还有配套的精品资源点击获取