图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千米的线路。
解题技巧:先去边一取小值一无环一全连通。
先去边,把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千米的线路。
你可能感兴趣的试题
A.9.1
B.9.2
C.10.1
D.10.2
A.390
B.450
C.400
D.470


