扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最小生成树中等
单选题
2022年5月第43题
中等
单选题
2022年5月第43题
#第二版教材
#必须掌握
某乡有7个小山村A~G,村与村之间原有小路可加宽修建公路的线路如下图所示(路边的数字表示路长的公里数)。为实现村村通公路,修建公路总长至少 (问题1) 公里。若在 (问题2) 村新建一所中学,则可以使人们从离它最远的村到该校所走的优化路程最短。

正确答案
A
本题考察的是图论中最小生成树和最短路径的综合应用。
主要应用Kruskal算法来求解最小生成树,并结合图的中心性分析来决定学校的最优位置。
问题 1:
要使所有村庄之间公路互通,并且总长度最小,就是求整个图的最小生成树(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

问题 2:
在最小生成树上选一个村庄建立中学,目的是使所有村庄到该村的最短路径中最长的那一段最短。这属于图的中心节点(Graph Center)问题。
在最小生成树上计算每个点到其他点的最短距离最大值(即该点的“最远距离”):
以每个点为起点跑一遍 BFS/DFS,得到最大路径距离。
根据题意,已知经过计算后,E 村是最优中心点,也就是说,以 E 为学校建校点,其它村庄到达它的最长路径是所有村点中最短的。
因此,正确答案为:E
