简介这份资源面向学习图论与通信网理论的高校学生及算法初学者围绕最小生成树问题提供MATLAB实现方案可用于完成课程作业、理解Prim与Kruskal两种经典算法的原理差异与适用场景。压缩包共2个文件包含1个m脚本文件与1个pdf文档前者为可直接运行的算法代码后者用于说明算法思路与实现细节整体约25KB体量轻便便于快速查阅与二次修改。资源以通信网理论作业3为背景涉及邻接矩阵与邻接表的数据结构选择、边权排序、并查集判环等关键编程技巧读者可据此对照代码验证最小生成树的构造过程并比较两种算法在稠密图与稀疏图下的效率表现。目前已有4806人学习下载适合希望将算法理论落地为可运行代码、并借此巩固图遍历与数据结构基础的读者参考。1. 从一次校园网布线翻车说起Prim 与 Kruskal 到底在算什么去年帮一个校区做机房改造32 个接入点、47 条可铺设链路预算只够买 31 段线。施工队给了一张 Excel里面是每条链路的长度和两端编号问我「怎么连最省线」。这其实就是最小生成树Minimum Spanning Tree, MST问题在一个带权无向连通图里选出 N-1 条边把所有 N 个顶点连成一片且边权总和最小。Prim 和 Kruskal 是两条最常走的路——Prim 从一个点出发不断「长」出一棵树Kruskal 则把所有边按权重排队从小到大挑不形成环的边。两者都能在 MATLAB 里几十行写完但选哪个、怎么存图、稀疏稠密怎么切直接决定你跑 32 个点还是 32000 个点时会不会卡死。这篇笔记面向需要把 MST 落到工程里的同学会写 MATLAB 循环、知道邻接矩阵是什么但不确定 Prim 和 Kruskal 的边界在哪、参数怎么调、稀疏图该用哪个。下面按「先立住原理 → 再动手复现 → 最后避坑」的顺序推一遍。2. 两种贪心策略的底层差异与选型依据2.1 Prim 的「点集扩张」逻辑Prim 的核心是一个不断长大的顶点集合。任选一个起点加入集合 S然后每一轮从「一端在 S 内、一端在 S 外」的候选边里挑权重最小的那条把外部端点拉进 S直到 S 包含全部顶点。它维护的是一个距离数组keykey(v)表示 v 到当前树的最小边权配合parent(v)记录这条边从哪来。因为每轮只加一个点总共 N 轮用朴素数组扫描找最小值是 O(N²)用二叉堆可以压到 O(E log V)。MATLAB 里没有现成的优先队列工程上一般直接用矩阵扫描N 在几千以内完全够用。Prim 的天然优势是「稠密图友好」。当边数接近 N² 时邻接矩阵存图不浪费扫描候选边也不吃亏。它的另一个好处是天然支持「从指定源点出发」——比如你必须从主交换机开始布线Prim 直接以它为起点即可不需要额外处理。2.2 Kruskal 的「边排序 并查集」逻辑Kruskal 换了个视角不看点看边。把所有边按权重升序排好依次取出如果这条边的两个端点当前不在同一个连通分量里就收下它否则丢弃收了会成环。判断「是否同分量」靠并查集Union-Find带路径压缩和按秩合并后单次操作近似 O(α(N))α 是反阿克曼函数实际可视为常数。整体复杂度由排序主导O(E log E)。Kruskal 的强项是「稀疏图」。边数远小于 N² 时只需要存边列表排序开销可控并查集几乎不花时间。它还有个隐性好处天然处理「图不连通」的情况——跑完后如果收下的边少于 N-1 条说明原图本身不连通直接能判定不需要额外写检测逻辑。2.3 选型对照表什么图用什么算法维度PrimKruskal时间复杂度朴素O(N²)O(E log E)时间复杂度优化O(E log V) 用堆O(E α(N)) 用并查集适合图密度稠密图E ≈ N²稀疏图E N²存图方式邻接矩阵优先边列表优先指定起点原生支持需额外约束不连通检测需额外判断边数不足即判定MATLAB 实现难度低矩阵操作直接中需写并查集提示如果 N 在 500 以内、边权是正数、图连通两个算法随便选差异在毫秒级。真正需要纠结的是 N 上万、边数几十万以上的场景。3. 在 MATLAB 里把 Prim 跑通邻接矩阵、距离数组与父节点回溯3.1 用邻接矩阵存图与无穷大初始化MATLAB 处理矩阵天然顺手Prim 用邻接矩阵存最省事。约定graph(i,j)是顶点 i 到 j 的边权无边填Inf对角线填 0。下面这段构造一个 6 个点的测试图边权故意设成不等方便观察选择顺序。% 构造 6 顶点无向带权图的邻接矩阵 N 6; graph Inf(N); graph(1,2)6; graph(1,3)1; graph(1,4)5; graph(2,3)5; graph(2,5)3; graph(3,4)5; graph(3,5)6; graph(3,6)4; graph(4,6)2; graph(5,6)6; % 无向图对称化对角线置 0 graph min(graph, graph); graph(1:N1:end) 0;逻辑说明先只填上三角再用min(graph, graph)对称化避免手写两遍出错。graph(1:N1:end)0是 MATLAB 里给对角线赋值的惯用写法1:N1:end生成的是 1, N2, 2N3… 这些线性索引正好落在对角线上。参数上Inf代表「不可达」后面找最小值时不会被误选。3.2 Prim 主循环key 数组与 parent 数组的更新function [totalWeight, edges] primMST(graph, startNode) N size(graph, 1); key Inf(1, N); % 各点到当前树的最小边权 parent zeros(1, N); % 记录父节点用于回溯边 inMST false(1, N); % 标记是否已入树 key(startNode) 0; for iter 1:N % 在未入树的点里找 key 最小的 candidates key; candidates(inMST) Inf; [~, u] min(candidates); inMST(u) true; % 用 u 更新邻居的 key for v 1:N if ~inMST(v) graph(u,v) key(v) key(v) graph(u,v); parent(v) u; end end end % 回溯边集与总权重 edges zeros(N-1, 3); totalWeight 0; idx 0; for v 1:N if parent(v) ~ 0 idx idx 1; edges(idx,:) [parent(v), v, graph(parent(v), v)]; totalWeight totalWeight graph(parent(v), v); end end end逻辑说明外层循环跑 N 次每次选一个点入树。candidates(inMST)Inf是关键一步——把已入树的点屏蔽掉min才不会重复选。内层循环更新邻居的key只有发现更短的边才覆盖这保证了key始终是「到当前树的最小值」。参数上startNode可以任意指定换起点不影响最终总权重MST 总权重唯一但形态可能不同。3.3 调用与结果验证[totalW, edgeList] primMST(graph, 1); fprintf(最小生成树总权重: %d\n, totalW); disp(选中的边起点 终点 权重:); disp(edgeList);跑出来总权重应该是 15选中的边为 (1,3,1)、(3,6,4)、(6,4,2)、(3,2,5)、(2,5,3)。验证方法把选中的 5 条边权重加起来1425315且 6 个点全部连通、无环。如果结果对不上先检查邻接矩阵是否对称、对角线是否为 0这两个地方最容易翻车。4. Kruskal 的 MATLAB 实现边列表排序与并查集4.1 从邻接矩阵抽取边列表Kruskal 不吃矩阵吃边列表。MATLAB 里用find配合triu抽上三角避免每条边存两遍。% 从邻接矩阵抽取边列表 [u, v, w] [ii, jj] find(triu(graph, 1) Inf); weights arrayfun((a,b) graph(a,b), ii, jj); edgeList [ii, jj, weights]; % 按权重升序排序 edgeList sortrows(edgeList, 3);逻辑说明triu(graph,1)取严格上三角 Inf筛掉不存在的边find返回行列下标。arrayfun逐对取值比循环快。sortrows(edgeList,3)按第三列权重排序这是 Kruskal 的核心预处理。参数上如果图是有向的去掉triu即可但 MST 通常针对无向图。4.2 并查集的 MATLAB 写法并查集用两个数组parentUF记录每个点的代表元rankUF记录树高用于按秩合并。function root ufFind(parentUF, x) % 路径压缩递归找到根并沿途挂到根上 if parentUF(x) ~ x parentUF(x) ufFind(parentUF, parentUF(x)); end root parentUF(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 end逻辑说明ufFind用递归实现路径压缩第一次调用后树会变扁后续查询接近 O(1)。ufUnion先查根同根直接返回否则按秩合并保证树高不超过 log N。参数上parentUF初始化时parentUF(i)irankUF全零。4.3 Kruskal 主流程与不连通判定function [totalWeight, mstEdges] kruskalMST(graph) N size(graph, 1); [ii, jj] find(triu(graph, 1) Inf); weights arrayfun((a,b) graph(a,b), ii, jj); edgeList sortrows([ii, jj, weights], 3); parentUF 1:N; rankUF zeros(1, N); mstEdges zeros(N-1, 3); totalWeight 0; count 0; for k 1:size(edgeList, 1) u edgeList(k,1); v edgeList(k,2); w edgeList(k,3); if ufFind(parentUF, u) ~ ufFind(parentUF, v) [parentUF, rankUF] ufUnion(parentUF, rankUF, u, v); count count 1; mstEdges(count,:) [u, v, w]; totalWeight totalWeight w; if count N-1 break; % 已够 N-1 条边提前退出 end end end if count N-1 warning(图不连通仅生成 %d 条边森林而非树, count); end end逻辑说明遍历排序后的边列表用并查集判断两端是否同分量不同就收下并合并。count N-1时提前break省掉后续无用遍历。最后判断count N-1说明图不连通给出警告而不是静默返回错误结果。参数上mstEdges预分配 N-1 行避免动态扩容。4.4 两个算法在同一张图上的结果对比[totalW1, edges1] primMST(graph, 1); [totalW2, edges2] kruskalMST(graph); fprintf(Prim 总权重: %d, Kruskal 总权重: %d\n, totalW1, totalW2);两者总权重必然相同MST 权重唯一但选中的边可能不同——当存在等权边时选择顺序会导致不同形态。这不是 bug是 MST 的非唯一性。验证时看总权重即可不要逐边比对。5. 避坑与排查那些让 MST 结果对不上的细节5.1 邻接矩阵不对称导致边权丢失现象Prim 跑出来总权重偏大或者某些点根本没被连上。原因手填邻接矩阵时只填了上三角忘了对称化graph(u,v)有值但graph(v,u)是InfPrim 从 v 侧扫描时看不到这条边。解决构造完矩阵后强制graph min(graph, graph)或者用graph graph graph再处理对角线注意后者会把对角线翻倍需单独置 0。5.2 Inf 参与运算产生 NaN现象总权重算出来是NaN。原因图不连通时某些点的key始终是Infparent保持 0回溯时如果没跳过parent(v)0的点graph(parent(v),v)会索引到 0 报错或产生NaN。解决回溯边集时加if parent(v) ~ 0判断Kruskal 侧则靠count N-1提前警告。5.3 并查集忘记路径压缩导致大图变慢现象N50000 时 Kruskal 跑了几分钟还没出结果。原因ufFind写成纯循环不压缩树退化成链单次查询 O(N)总复杂度退化到 O(E·N)。解决用递归或迭代实现路径压缩把沿途节点直接挂到根上。MATLAB 递归深度默认有限制N 特别大时改成迭代版function root ufFindIter(parentUF, x) r x; while parentUF(r) ~ r r parentUF(r); end % 第二遍压缩路径 while parentUF(x) ~ r nxt parentUF(x); parentUF(x) r; x nxt; end root r; end5.4 等权边导致误以为算法出错现象Prim 和 Kruskal 选出的边不完全一样怀疑实现有 bug。原因MST 在存在等权边时不唯一两种贪心策略的选择顺序不同自然得到不同形态。解决只比对总权重不比对边集。如果业务要求特定形态比如优先选编号小的边需要在排序或选择时加次级排序键。5.5 用 min 找最小值时忽略了已入树标记现象Prim 第二轮就选到了已经入树的点死循环或结果错乱。原因candidates没有屏蔽inMST的点min返回的还是上一轮那个点。解决每轮先candidates(inMST) Inf再取min。这个坑在 MATLAB 里特别隐蔽因为min不会报错只是默默返回错误结果。6. 进阶技巧稀疏大图下的性能压榨与结果校验当 N 上到几万、边数几十万时前面那套朴素实现会开始吃力。我一般做三件事第一存图从邻接矩阵换成稀疏矩阵sparse(ii, jj, ww, N, N)MATLAB 对稀疏矩阵的find和索引有专门优化内存占用从 O(N²) 降到 O(E)。第二Kruskal 的排序用sortrows在边数超过十万时偏慢可以改用sort对权重列单独排序拿到索引再重排边列表实测能快 20% 到 30%。第三Prim 在稀疏图上其实不占优但如果必须用 Prim 且图稀疏可以把内层for v 1:N换成遍历稀疏矩阵的非零元避免扫描大量Inf。校验结果有个便宜又好用的办法跑完 MST 后用graphminspantreeMATLAB 自带函数需要 Bioinformatics Toolbox 或 MATLAB 的 graph 对象对同一张图再算一遍比对总权重。如果手头没有工具箱就自己写个连通性检查——从任意点做一次 BFS看能否访问到全部 N 个点再数边数是否恰好 N-1。这两条都过结果基本可信。% 用 graph 对象交叉验证R2015b 之后内置 G graph(graph .* (graph Inf), upper); T minspantree(G); fprintf(内置函数总权重: %d\n, sum(T.Edges.Weight));参数上注意graph构造时要把Inf转成 0 或直接传稀疏矩阵否则会报错。upper表示只取上三角避免重复边。最后说个血泪经验MST 的代码本身不难难的是输入数据的清洗。我遇到过邻接矩阵里混进了负权边Prim 和 Kruskal 都能跑但结果完全不符合预期——负权边会让贪心策略失效MST 问题本身要求边权非负或者至少没有负环。所以拿到数据先min(graph(:))看一眼有没有负数有的话要么取绝对值要么换用其他方法。另一个习惯是每次跑完把边集按权重排一下看看有没有异常大的边混进来往往能提前发现数据录入错误。希望帮到你。本文还有配套的精品资源点击获取