选择题 68.  有8口海上油井,相互间距离如下表所示(单位:海里)。其中1号井离海岸最近,为5海里。现要从海岸经1号井铺设油管将各井连接起来,则铺设输油管道的最短长度为______海里。
  1 2 3 4 5 6 7 8
1 0 1.3 2.1 0.9 0.7 1.8 2.0 1.5
2   0 0.9 1.8 1.2 2.6 2.3 1.1
3     0 2.6 1.7 2.5 1.9 1.0
4       0 0.7 1.6 1.5 0.9
5         0 0.9 1.1 0.8
6           0 0.6 1.0
7             0 0.5
8               0
 
【正确答案】 D
【答案解析】 本题实际是求连通图的最小生成树问题。我们采用Krusckal算法。
   第1步,我们在表中找出一个最小值——0.5,可见是顶点8与顶点7间的连接(简记为8~7),我们把这两个点连起来;
   第2步,在表中剩余的连接间再找出一个最小值——0.6,可见是7~6,把这两个点再连起来。
   第3步,在表中剩余的连接之间再找一个最小值——0.7,可见是5~1、5~4,把5与1连起来,再把5与4也连起来。
   第4步,在表中剩余的连接间再找出一个最小值——0.8,可见是8~5,把这两个顶点连起来。
   第5步,在表中剩余的连接间再找出一个最小值——0.9,可见是8~4、4~1、6~5、3~2,但1、4、5、6、8都已经是在同一棵树中,所以无需连接,所以仅需把3和2连起来。
   第6步,在表中剩余的连接间再找出一个最小值——1.0,可见是8~3、8~6,但8与6已经在同一棵树中,所以仅把8和3连接起来。
   至此,所以顶点已经在同一棵树中,这棵树就是最小生成树。我们把所有连接的权值加起来:0.5+0.6+0.7+0.7+0.8+0.9+1.0=5.2
   其中1号油井距离海岸最近,为5海里。因此5.2+5=10.2