美文网首页
最小生成树

最小生成树

作者: Allen的光影天地 | 来源:发表于2018-11-29 22:20 被阅读9次

引子

村村通,我们想把几个村子(点)修路连接起来,所以肯定是修最小的路数量,同时想要修路的成本最低(权重)

定义

  1. 是一个树,所以无回路
  2. V个顶点一定对应V- 1条边
  3. 是生成树,包含所有顶点,
  4. 最小生成树,权重之和最小

解决方法

贪心算法
每一步都是最好的(权重最小的)
相关约束:只能用图里面的边,只能用掉v - 1条边,不能有回路
prim算法(针对稠密图):让一颗小树长大,有点像迪佳斯特拉算法
kruskal算法(针对稀疏图):森林合并成树,主要看边!

相关文章

网友评论

      本文标题:最小生成树

      本文链接:https://www.haomeiwen.com/subject/ubyqcqtx.html