05数学(算法)与经济管理

01-最小生成树

2021-08-08 59 1

简介 最小生成树类型的题解

某小区有七栋楼房①~⑦(见下图),各楼房之间可修燃气管道路线的长度(单位:百米)已标记在连线旁。为修建连通各个楼房的燃气管道,该小区内部煤气管道的总长度至少为多少百米?


upfile


乍一看,这题,“无数”种路径,“无数”难度对吧。


我们要连通7栋楼,那么只要连通就可以了,可以考虑“贪心算法”, 先连通两栋楼,这两栋楼之间的距离最短。距离最短的是2百米,3号楼和6号楼距离2百米。

upfile


 再选次短的两栋楼, 1/2号楼和3/7号楼。此时1/2号楼连通,3/6/7号楼连通了。

upfile

  再选次短的两栋楼, 2/6号楼。此时1/2/3/6/7号楼连通了。

upfile


  再选次短的两栋楼, 4/7号楼。此时1/2/3/4/6/7号楼连通了。

upfile



还剩5号楼,选6距离最短,最终结果

upfile

最终答案: 3+6+4+2+3+5 = 23。


 还有“无数”个题,会这一个,其他的还用担心吗?

别问为什么“系统架构设计师”会考这样的题,问就是不会。如果你真的有一天成了“架构师”,你会发现,“数据结构与算法”、计算机组成原理、计算机网络、操作系统是多么的重要。


点赞 1

文章评论

欢迎您:

纸上得来终觉浅,绝知此事要躬行!

112 文章 36783 浏览 3 评论

联系我

  •   QQ:    361352119
  •  Email:  lisimmy@sina.com
  • 微信: