列表

详情


某乡8个小村(编号为1~8)之间的距离如下表(单位: km)。 1 号村离水库最近,为5km,从水库开始铺设水管将各村连接起来,最少需要铺设() 长的水管(为便于管理和维修,水管分叉必须设在各村处)。

A. 6.3km

B. 11.3km

C. 11.8km

D. 16.8km

参考答案: B

详细解析:

这里可用普利姆最小生成树算法来进行计算。

初始状态:V是所有顶点的集合,即V={1,2,3,4,5,6,7,8}UT都是空。

1步:将顶点1加入到U中。

    此时,U={1},离顶点1最近的为顶点4,距离为1km,因此将顶点4加入到U中,将1->4的边加入到T中。

2步:将顶点4加入到U中。

   此时,U={14},T={1->4};离顶点1和顶点4最近的为顶点8,距离为1km,因此将顶点8加入到U中,将4->8的边加入到T中。

3步:将顶点8加入到U中。

   此时,U={148},T={1->44->8};离顶点148最近的为顶点7,距离为0.5km,因此将顶点7加入到U中,将8->7的边加入到T中。

4步:将顶点7加入到U中。

    此时,U={1,487},T={1->44->88->7};离顶点1487最近的为顶点6,距离为0.8km,因此将顶点6加入到U中,将7->6的边加入到T中。

5步:将顶点6加入到U中。

    此时,U={14876},T={1->44->88->77->6};离顶点14876最近的为顶点3,距离为1km,因此将顶点3加入到U中,将8->3的边加入到T中。

6步:将顶点3加入到U中。

   此时,U={148763},T={1->44->88->77->68->3};离顶点148763最近的为顶点2,距离为1km,因此将顶点2加入到U中,将3->2的边加入到T中。

7步:将顶点2加入到U中。

   此时,U={1487632},T={1->44->88->77->68->33->2};此时只有顶点5没有连通了,离顶点5最近的为顶点2,距离为1km,因此将顶点5加入到U中,将2->5的边加入到T中。

8步:将顶点5加入到U中。

    此时,U={14876325},T={1->44->88->77->68->33->22->5};满足U=V,各顶点均已连通。

此时,最小生成树构造完成,如图所示:


因为1 号村离水库的距离为5km,所以从水库开始连接各村水管的最小总长度为:5+5×1+0.5+0.8=11.3km。答案为B选项。


上一题