2. 从业资格
  3. 煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节

煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节

练习题库2022-08-02  76
问题 煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节点代表各住宅楼和主管道位置，线上数字代表两节点间距离（单位：百米）。则煤气公司铺设的管道总长最短为（　　）米。A.1800B.2200C.2000D.2100
选项 A.1800
B.2200
C.2000
D.2100
答案 B
解析 本考题考查的知识点为最小支撑树问题，即破圈法求解。
题目说的，实际就是最小生成树。两种方法都可以
方法一、破圈法：从图中的任一一个圈中，去掉权值最大的（如果同一圈中有两条或以上最大值，随便取一条去掉），然后重复这个步骤，直到图中不再含有圈。最后得到的，就是最小生成树。
方法二、直接从图中取最小权值的线条，然后重复这个步骤，直到最后将所有的节点都连起来。有个前提条件是，不形成圈。如果未被取的线条有2条以上权值都小，随意取一条。在不形成圈的前提下，最后得到的，就是这图的最小生成树。
去掉98766，只剩下55453，加起来是22千米，所以选B。
转载请注明原文地址:https://tihaiku.com/congyezige/2297606.html
本试题收录于： 高级信息系统项目管理师题库软件水平考试初中高级分类

高级信息系统项目管理师

软件水平考试初中高级

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