扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最小生成树中等
单选题
2012年5月第41题
中等
单选题
2012年5月第41题
#第二版教材
#必须掌握
开发商需要在某小区9栋楼房之间敷设自来水管道，使各楼都能连通，又能使总成本最低。 经勘察，各楼房之间敷设管道的路径和成本（单位：千元）如下图所示。
该项目的总成本至少需要（__）千元。
问题（1）
浓缩知识点
最小生成树是带权连通无向图的特殊子图，它能连通图中所有顶点且不含回路，同时所有边的权值总和最小，边的数量固定为图的顶点数减一。求解最小生成树常用两种经典算法，Kruskal算法是将所有边按权值从小到大排序，依次选取不会形成回路的边，通常借助并查集判断是否成环；Prim算法则从任意顶点出发，每次选择连接当前已连通顶点集合与未连通顶点的权值最小的边，逐步拓展连通范围。这类算法常应用于网络布线、通信链路搭建、物流路径规划等需要以最低成本连通多个节点的实际场景。
正确答案
A
本题考察的是最小生成树（MST） 的求解。
由于“管道只能在楼房处分叉”，问题可抽象为带权连通无向图的最小生成树。求解可用Kruskal 算法：将所有候选边按权值从小到大依次选取，跳过会形成回路的边，直到选满 n−1 条边（本题 n=9，需选 8 条）。
按图中权值由小到大选择，可先取所有不致成环的权值为 1 的边（4条），再取能把剩余连通分量连成一体且不成环的权值为 2 的边（3条），权值为 3 的边 1 条。
这样恰好得到 8 条边，MST 总成本 = 1+2+1+1+1+2+3+2 = 13（千元）。
选择选项 A。