2. 计算机
  3. 煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，结点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，结点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

admin2018-10-14  43
问题 煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，结点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为(    )米。
选项 A、1 800
B、2 200
C、2 000
D、2 100
答案B
解析 这是一个典型的无向连通图的最小生成树问题(Minimum Spanning Tree)。
算法如下：
  任取一点，例如①，将其纳入已完成部分。点①与其他各点中的最小距离为①⑤=3，从而将边①⑤以及点⑤纳入已完成部分。
  点①、⑤与其他各点②、③、④、⑥这两个集合之间的最短距离为①④=⑤⑥=5，任选其一，比如①④，从而将边①④与点④纳入已完成部分。
  点①、④、⑤与点②、③、⑥两个集合的最短距离为③④=4，从而将边③④与点③纳入已完成部分。
  点①、③、④、⑤与点②、⑥两个集合之间的最短距离为⑤⑥=5，从而将边⑤⑥与点⑥纳入已完成部分。
  点①、③、④、⑤、⑥与点②两个集合之间的最短距离为②⑥=5，从而将边②⑥与点②纳入已完成部分。
  此时，所有6个点都已经接通，其边为AE、AB．AF、FD．CD，总长度为22(百米)．如下图所示：
转载请注明原文地址:https://kaotiyun.com/show/uvFZ777K
本试题收录于： 信息系统项目管理师上午综合知识考试题库软考高级分类
0

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

软考高级

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