最小生成树

引子

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

定义

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

解决方法

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

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容