扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最小生成树简单
单选题
2018年5月第39题
简单
单选题
2018年5月第39题
#第二版教材
#必须掌握
某小区有七栋楼房①~⑦（见下图），各楼房之间可修燃气管道路线的长度（单位：百米）已标记在连线旁。为修建连通各个楼房的燃气管道，该小区内部煤气管道的总长度至少为（23）百米。
问题（1）
浓缩知识点
带权连通无向图的最小生成树，是可连通图中所有顶点且边的总权值最小的边集合，其包含的边数固定为顶点总数减一。求解这类问题有两种经典算法，Kruskal算法是将所有边按权值从小到大排序，依次选取不会形成回路的边，直至选满顶点数减一条；Prim算法则从任意顶点出发，每次选择与当前已连通顶点集合邻接的权值最小的边，逐步扩展直至覆盖所有顶点。这类算法常应用于燃气管道、通信电缆等基础设施的路径规划场景，能在保证全域连通的前提下最大化压缩建设成本。
正确答案
A
本题考察的是带权连通无向图的最小生成树（MST）。
可用Kruskal 算法求解。算法步骤为：将所有边按权从小到大排序，依次选取不会形成回路的边，直到选满 n−1 条（本题 n=7，需选 6 条）。
根据图中标注，权值较小的关键边有：1–2（3）、3–6（2）、3–7（3）、2–4（4）、4–7（5）、2–5（6）、3–4（6）等。
按 Kruskal 思路依次选择并避免成环，可得到一组满足连通且最短的边集合：3–6（2）、3–7（3）、1–2（3）、2–4（4）、4–7（5）、2–5（6）。
此时 7 个顶点已连通，所选 6 条边的总长度为 2+3+3+4+5+6=23（百米），即 2300 米，为最小生成树长度。
因此，最小总长度为 23 百米。