单选题
题号 #6183565

图1-27—1为某地区的通信线路,图中的节点为8个城市节点间标识的数字为城市间铺设通信线路的长度,为保持八个城市的通讯连接,则至少铺设(  )千米的线路。

进入在线模考

参考答案

D

答案解析

本题考查的是图论中的最小生成树。
解题技巧:先去边一取小值一无环一全连通。
先去边,把A、B、D等先画出来,然后找最小值,最小值为100,有两条路径:A—D、G—H;然后找200的,其路径为:A—B、D—C、B—G、C—G、G—E,连接完之后发现剩下一个F,E—F为300,画出来的图如图l一27—2所示。

全部连接完发现ADCGB形成了一个环,我们需要把它全部连通但是不成环,所以要去掉一个值,去掉B—G路径后形成的线路如图l—27—3。

此时所有的都已经连通,我们将每个路径的值相加:200+100+200+200+100+200+300=1300(千米),所以为保持八个城市的通讯连接,至少需铺设1300千米的线路。
 

你可能感兴趣的试题

找试题 · 找答案 · 找资料 在线模考