简介最小生成树室内布线课程设计报告面向计算机科学与技术专业学生演示如何利用Prim或Kruskal算法求解带门障碍的室内插座最短布线问题。在室内场景中插座分散在不同墙面门洞会阻断直线连接文档将墙面抽象为图的顶点插座距离作为边权门的位置转化为权重修正条件形成可计算模型。程序定义outlet、VertexType、MGraph等结构体并设计Dplace、Oplace、Xplace三个辅助函数分别判定门所在墙面1~4号墙、插座所在墙面及两插座相对位置同墙/邻墙/对墙核心函数CC在门位于两插座连线时会加入门高差重新计算路径否则采用曼哈顿距离加高度差逻辑清晰且贴近实际工程。随后借助InsertSort对边按权重排序以Kruskal算法构造最小生成树并输出最短电线总长另附边界测试数据验证门影响与不影响两种情况。资源为单个PDF文件大小183KB内容紧凑完整目前已有100人学习下载适合算法课程设计、期末复习或最小生成树应用实践参考。1. 室内布线为什么不是拉直线而是求最小生成树把一排插座用最短的线串起来直觉上是两两相邻拉直线。但真实房间里有墙角、有门插座分布在四面墙的不同高度上线要贴着墙脚走门还要留出开合空间。于是问题从求两点最短路径变成了给定若干个点找一条连接所有点的最短总路径——这正是图论里的最小生成树MST模型。这篇课程设计最值得拆的不是Kruskal本身而是它如何把墙面、门、插座高度这些物理条件翻译成图的边权再用程序自动算出最优布线长度。材料里给出的完整C代码覆盖了从坐标输入、墙面判定、门遮挡修正到Kruskal求最小生成树的全过程适合正在做《算法与数据结构》课程设计、或者想看看最小生成树如何脱离课本例题落到真实约束场景的人。下文按建模 → 边权计算 → 算法落地 → 验证技巧的顺序逐段拆解所有代码均能从原文提取、可直接编译运行。2. 墙面判定与邻接矩阵把房间坐标系翻译成图2.1 三个结构体各管什么程序开头定义了三个结构体分工非常清晰typedef struct { float x; float y; float h; } outlet; // 插座平面坐标 离地高度 typedef struct { int no; // 节点编号 int info; // 插座所在墙面编号 1~4 } VertexType; typedef struct { float edges[20][20]; // 邻接矩阵存的是走线距离 int n, e; VertexType vexs[20]; // 节点数组上限 20 } MGraph;outlet用x、y、h三个量描述一个插座其中h是插座离地高度。注意它没有用z而是叫h因为后面计算距离时要区分两种情况走线沿墙脚时高度差直接相加而绕门时高度只参与上翻到门框这一段计算语义上h更贴近安装高度而非空间坐标。MGraph的edges[20][20]是标准邻接矩阵但存的值不是欧氏距离而是考虑了墙面关系、门遮挡之后的实际走线长度。这是整个程序建模的起点图结构本身是常规的特殊之处全在边权怎么算。2.2 墙面编号的约定Dplace和Oplace两个函数负责把门在哪个位置插座在哪面墙翻译成统一的编号。编号规则如下表墙面编号判定条件房间长 HX、宽 HY1 号墙门四角 x 坐标全为 0插座 x0 且在房间范围内2 号墙门四角 y 坐标全为 0插座 y0 且 x03 号墙门四角 x 坐标全等于 HX插座 xHX4 号墙门四角 y 坐标全等于 HY插座 yHYint Oplace(outlet Olet, float a, float b) { if (Olet.x 0 Olet.y 0 Olet.h 0) return 1; if (Olet.y 0 Olet.x 0 Olet.h 0) return 2; if (Olet.x a Olet.y 0 Olet.h 0) return 3; if (Olet.y b Olet.x 0 Olet.h 0) return 4; }参数a、b分别是房间的长和宽由用户在main里输入后传入。判定逻辑有一点需要注意2 号墙的判定要求x 0是为了避免原点(0,0)同时满足 1 号墙和 2 号墙的条件。实际房间中墙角位置一般是踢脚线或立柱不会装插座但这种边界处理在程序里是必要的。如果你打算扩展这个程序支持墙角插座需要额外定义墙角属于哪面墙的规则否则会重复计入。2.3 两插座相对位置 XplaceXplace返回三种关系0 表示同墙1 表示相邻墙2 表示对面墙。判断逻辑是四个墙面编号两两组合的枚举if (a 1 (b 2 || b 4) || a 2 (b 1 || b 3) || a 3 (b 2 || b 4) || a 4 (b 3 || b 1)) return 1; // 相邻墙面 return 2; // 剩下的都是对面墙这个函数本身没有技术难度但它是后续main里分支计算距离的入口。三种相对位置对应三种不同的走线路径模型下一章详细展开。3. 边权计算门遮挡下曼哈顿距离的三种变体3.1 无遮挡时的基准距离先看不考虑门的情况。程序统一使用沿墙面展开的曼哈顿距离 高度差而不是三维欧氏距离。以同墙两插座为例m fabs(Olet[i].x - Olet[j].x) fabs(Olet[i].y - Olet[j].y) fabs(Olet[i].h - Olet[j].h);这里的物理含义是线从插座 A 沿墙面水平走到 B 的投影位置再垂直上下到 B 的安装高度。fabs取绝对值保证方向无关两条走线方向相反结果一致。如果你在实际工程中布线线一般走墙脚或踢脚线不会真的贴着插座高度走但课程设计里这样简化是合理的——它抓住了水平距离 高度差的主要矛盾。3.2 门在插座连线上绕门公式的推导CC函数是本程序最核心的几何逻辑。以门在 1 号墙x0为例if (Olet1.h door[2].h Olet2.h door[2].h (Olet1.y door[2].y door[3].y Olet2.y || Olet2.y door[2].y door[3].y Olet1.y)) { n fabs(Olet1.x - Olet2.x) fabs(Olet1.y - Olet2.y) (door[2].h - Olet1.h) (door[2].h - Olet2.h); } else { n fabs(Olet1.x - Olet2.x) fabs(Olet1.y - Olet2.y) fabs(Olet1.h - Olet2.h); }条件Olet1.h door[2].h Olet2.h door[2].h的含义是两个插座的安装高度都不超过门框高度。这里door[2].h取的是门右上角的高度即门框顶。如果插座本身比门框还高线可以直接从门框上方跨过不需要绕行。第二个条件(Olet1.y door[2].y door[3].y Olet2.y)判断的是门在水平方向是否挡住插座连线。door[2].y和door[3].y分别是门右边界和左边界的 y 坐标如果两个插座一个在门左侧、一个在门右侧那么直线路径一定会穿过门洞。满足这两个条件时距离公式变成水平曼哈顿距离 (门框高 - 插座1高) (门框高 - 插座2高)拆开看线从插座 1 向上走到门框高度door[2].h水平跨过门洞上方再向下走到插座 2。相比无遮挡公式fabs(h1 - h2)被替换成了(门框高 - h1) (门框高 - h2)。两者之差恰好是绕门额外付出的高度代价。为了验证这个逻辑是否正确我建议你手动算一个例子插座 A 高 0.3m插座 B 高 0.3m门框高 2.1m那么绕门公式给的是(2.1-0.3)*2 3.6m的高度代价而直接高度差是 0。也就是说只要走线必须跨过门就至少要上翻到门框再下来这段额外长度无法消除。3.3 对面墙插座的特殊处理if (Xplace(k, l) 2) { // 对立墙面 m fabs(Olet[i].x - Olet[j].x) fabs(Olet[i].y - Olet[j].y) Olet[i].h Olet[j].h; }对面墙的插座不走门框而是沿天花板或地板绕行所以距离是水平曼哈顿距离加上两个插座各自的高度之和。这个分支没有调用CC也没判断门是否在中间——因为无论门在哪面墙走天花板或地板都不受影响。这个简化成立的前提是线可以自由选择走顶还是走底。CC函数只能处理门在第 1、3 面墙竖直墙或第 2、4 面墙水平墙这两种情况代码里if (a1||a3)和if (a2||a4)两个分支的几何判据分别是y 方向被门挡住和x 方向被门挡住逻辑对称但坐标轴不同。如果你要扩展房间为不规则形状这个函数是第一个需要重写的地方。4. Kruskal 落地从边集提取到 vset 数组判环4.1 邻接矩阵转边集数组Kruskal 算法的输入是边集而程序里图是用邻接矩阵存的所以第一步要把矩阵摊平成Edge数组typedef struct { int u; // 起点编号 int v; // 终点编号 float w; // 边权走线距离 } Edge; k 0; for (i 0; i g.n; i) for (j 0; j g.n; j) if (g.edges[i][j] ! 0) { E[k].u i; E[k].v j; E[k].w g.edges[i][j]; k; }因为main里填邻接矩阵时同时写了对称位置edges[i][j]和edges[j][i]这里会把每条边存两次。Kruskal 处理重复边不影响最终结果——排序后第一条被选中的边会被加入生成树它的对称边因为两个端点已经在同一集合里而被跳过只是多占了一点排序时间。如果你追求效率可以在建边时只取j i的上三角。常见做法是改成for (j i 1; j g.n; j)因为无向图的邻接矩阵天然对称。4.2 直接插入排序边数少时的合理选择void InsertSort(Edge R[], int n) { for (i 1; i n; i) { tmp R[i]; h R[i].w; j i - 1; while (j 0 tmp.w R[j].w) { R[j 1] R[j]; j--; } R[j 1] tmp; } }这是标准的直接插入排序按w升序排列。复杂度 O(n²)在边数不多时比快排更简单、没有递归开销。注意排序的稳定性当两条边权值相同时比较条件tmp.w R[j].w是严格小于相等时不交换因此保持了原始顺序。这在 Kruskal 里不影响正确性但如果你在输出时要保留某种优先级这个细节需要注意。4.3 vset 数组与判环逻辑for (i 0; i g.n; i) vset[i] i; // 初始时每个顶点独立成集合 k 1; j 0; while (k g.n) { u1 E[j].u; v1 E[j].v; sn1 vset[u1]; sn2 vset[v1]; if (sn1 ! sn2) { // 两个端点不在同一集合 m E[j].w; // 累加边权 k; // 已选边数 1 for (i 0; i g.n; i) if (vset[i] sn2) vset[i] sn1; // 合并集合 } j; // 无论是否选中都继续下一条边 }vset[i]存的是顶点i所属的集合编号。初始时每个顶点自成一个集合编号就是它自己。当选中一条边(u1, v1)时检查两个端点是否属于同一集合如果不同则说明这条边不会形成环可以加入生成树然后把所有属于sn2集合的顶点并入sn1。这个实现是并查集最朴素的形式没有路径压缩和按秩合并每次合并都要扫一遍全部顶点。对于g.n 20的问题规模完全够用。如果掌握并查集可以替换为带路径压缩的版本Find操作复杂度从 O(n) 降到接近 O(1)但在这个规模下性能差异感受不到。4.4 为什么 Kruskal 在这里比 Prim 合适从代码结构看程序先算出所有插座两两之间的距离存进邻接矩阵然后一次性提取所有边。这正好是 Kruskal 的输入形态边集完整、需要排序。Prim 算法适合边稠密且从某个顶点逐步扩展的场景虽然本题邻接矩阵是稠密的但 Kruskal 的边排序结果可以直接复用逻辑也更贴合每次选最短且不构成环的边这个直观理解。课程设计的验证重点是程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足要求的结果所以算法选择不是关键关键是边权计算是否在各种几何条件下都正确。5. 边界测试与 ceil 取整验证程序正确性的两个关键点文档里记录了第一个边界测试数据两插座在相邻墙面门处在两插座连线上。这个测试之所以带刁难性是因为它同时触发两个分支Xplace判定为相邻墙返回 1而CC里的遮挡条件判断为门在连线上于是启用绕门公式。如果Xplace或CC的任一判断出错输出长度就会偏小——因为程序会误用无遮挡公式少算绕门的高度代价。验证方法是先手算假设房间长 6m、宽 4m、高 3m插座 A 在 1 号墙x0高度 0.3m插座 B 在 2 号墙y0高度 0.3m门在 1 号墙且门框高 2.1m。A 的 y 坐标为 0.5mB 的 x 坐标为 4m门从 y1 到 y3。此时 A 和 B 的连线在 y 方向跨越门洞绕门距离 |0-4| |0.5-0| (2.1-0.3)*2 8m。如果程序输出 8说明遮挡判断正确。第二个容易忽略的问题是ceil(m)。边权累加结果m是float而输出用了ceil向上取整cout 所需要的电线最短为 endl; cout ceil(m) endl;这是非常实际的工程考量电线按米卖不能买 8.3 米必须买 9 米。但ceil有个坑——浮点误差。如果理论值是 8.0但浮点运算得到 7.9999999ceil会错误地取到 8更常见的是理论值刚好是整数时被多算 1 米。我一般会在ceil前加一个很小的 epsilon比如ceil(m - 1e-6)避免浮点精度导致多算一段线。验证最小生成树本身正确性的方法是把程序输出和 Prim 算法手算结果对照。比如上述测试数据若只有 3 个插座手算所有两两距离后按 Kruskal 手工选边应该得到相同的总长度。更系统的做法是随机生成插座坐标和门位置用暴力枚举所有生成树找最小总长再和程序输出比对——对于 N 8 的规模暴力枚举是可行的这是验证 Kruskal 实现是否有隐藏 bug 的最可靠手段。最后可以做一个有意思的实验把CC函数的门遮挡条件Olet1.h door[2].h Olet2.h door[2].h改成Olet1.h door[2].h - 0.01 Olet2.h door[2].h - 0.01再跑一遍边界测试。你会发现原本恰好等于门框高度的插座走线结果变了——这个微小改动揭示了原判断里等于门框高度也视为需要绕行的隐含约定理解这一点你就真正读懂了这份代码的几何边界在哪。本文还有配套的精品资源点击获取