2. 计算机
  3. 某地区的通信线路图如图18-1所示，假设其中标注的数字代表通信线路的长度(单位为km)，则至少要架设( )km长的线路，才能保持六个城市的通信连通。

某地区的通信线路图如图18-1所示，假设其中标注的数字代表通信线路的长度(单位为km)，则至少要架设( )km长的线路，才能保持六个城市的通信连通。

admin2015-05-22  47
问题 某地区的通信线路图如图18-1所示，假设其中标注的数字代表通信线路的长度(单位为km)，则至少要架设(       )km长的线路，才能保持六个城市的通信连通。
选项 A、1 000
B、1 300
C、1 600
D、2 000
答案B
解析 从图论上看，本题要求得到图18-1的最小生成树(即选取部分边，使其保持连通，又使其总长度最小)。
    下面的算法(普里姆算法)可以逐步实现这个要求。
    任取一点，例如A，将其纳入已完成部分。A点与其他各点中的最小距离为AE=200，从而将边AE以及点E纳入已完成部分。
    点A、E与其他各点B、C、D、F这两个集合之间的最段距离为AB=AF=300，从而可以将边AB与点B(或边AF与点F)纳入已完成部分。
    点A、B、E与点C、D、F两个集合的最短距离为．AF=BF=300，从而可以将边AF(或边BF)与点F纳入已完成部分。
    点A、B、E、F与点C、D两个集合之间的最段距离为FD=200，从而将边：FD与点D纳入已完成部分。
    点A、B、E、F、D与点C两个集合之间的最短距离为CD=300，从而将边CD与点C纳入已完成部分。
    此时，所有六个点都已经接通，其边为AE、AB、AF、FD、CD的总长度为l 300km。
转载请注明原文地址:https://kaotiyun.com/show/PeGZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

信息系统项目管理师上午综合知识考试

软考高级

相关试题推荐
随机试题
最新回复(0)