2026年10月押题密卷 · 选择题

山区某乡的6个村之间有山路如图所示,其中的数字标明了各条山路的长度(千米)。 6 个村之间的山路乡政府决定沿山路架设电话线 。 为实现村村通电话 , 电话线总长至少为千米 。 客户扣! 客户机2 打印机2 口。请选择正确选项( )。

A. 11
B. 14
C. 18
D. 33
参考答案:B

该题考查最小生成树相关知识。解题时,可以采用克鲁斯卡尔算法,从图中,按边权值从小到大顺序 来选择边,当选取的边会形成环路时,放弃该边的选择。选足n-1 条边时(n 为图中的节点数),即为 解。依据该原则,得到图,加粗线组成最小生成树。 最小生成图示意图 所以电话线总长为:1+2+3+4+4=14。