山区某乡的6个村之间有山路如下图所示,其中的数字标明了各条山路的长度(公里)。乡政府决定沿山路

12 查阅

山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路的长度(公里)。

乡政府决定沿山路架设电话线。为实现村村通电话，电话线总长至少为(59)公里。

A．11

B．14

C．18

D．33

参考答案:

B解析：本题需要在给定的图上寻找最小支撑树。图由若干个结点以及结点之间的连线组成，每条连线上标记了权数(本题为长度)。最小支撑树实际上是其中的一个子图，它包括所有的结点以及部分连线，这些连线需要连接所有的结点，但其总权数(长度)最小。从本题应用看，就是要在上述山路图中确定部分山路，使其能连接6个村，又能使总长度最短。最小支撑树的求解方法：先选择最短的一条线(如有多条，可以任选一条)，它已经连接了2个点。从这2点出发，再找出能连接其他一个点的最短线(如有多条，可以任选一条)。这样，就已经用2条线连接

软考高级