返回
当前 - 选择题 - 最小生成树中等
题号：0120220500043
单选题
2022年5月第43题
中等
题号：0120220500043
单选题
2022年5月第43题
最小生成树
中等
高频
收藏
分享
反馈
某乡有7个小山村A~G，村与村之间原有小路可加宽修建公路的线路如下图所示（路边的数字表示路长的公里数）。为实现村村通公路，修建公路总长至少（13.8）公里。若在（E）村新建一所中学，则可以使人们从离它最远的村到该校所走的优化路程最短。
浓缩知识点
最小生成树是连通无向图中连接所有顶点且总边权值最小的子图，可解决如全域连通建设成本最优的问题，常用求解算法有Kruskal算法和Prim算法，其中Kruskal算法是将所有边按权值升序排序后，依次选取不构成回路的边，直至选出n-1条边（n为顶点总数）；Prim算法则从某一顶点出发，逐步添加邻接的最小权值边来扩展生成树。图的中心节点是公共设施选址类问题的核心解法指向，指在图中（实际应用常依托最小生成树简化计算），能让其他所有顶点到该节点的最短路径里的最大值达到最小的顶点，可实现最远服务对象的通行距离尽可能短，适用于学校、应急站点等设施的最优选址。
正确答案
A
本题考察的是图论中最小生成树和最短路径的综合应用。
主要应用Kruskal算法来求解最小生成树，并结合图的中心性分析来决定学校的最优位置。
要使所有村庄之间公路互通，并且总长度最小，就是求整个图的最小生成树（Minimum Spanning Tree, MST）。这类问题常用的算法有 Prim 和 Kruskal，这里采用 Kruskal 算法。
步骤如下：
- 将所有边按长度升序排序。
- 从最短边开始依次选择，只要不构成回路，就纳入生成树中，直到选出 n−1=6n-1 = 6n−1=6 条边（因为有7个村）。
排序后的边长度为：
- D-E（1.5）
- E-G（1.5）
- C-E（1.8）
- A-D（2）
- A-C（2）
- F-D（3）
- A-F（4）
- B-G（4）
- A-B（5）
- B-C（5）
- F-G（6）
选取以下6条边组成最小生成树：
- B-G（4）
- A-C（2）
- D-E（1.5）
- E-G（1.5）
- C-E（1.8）
- F-D（3）
总长为：4 + 2 + 1.5 + 1.5 + 1.8 + 3 = 13.8公里
因此，正确答案为：A. 13.8
