引子
村村通,我们想把几个村子(点)修路连接起来,所以肯定是修最小的路数量,同时想要修路的成本最低(权重)
定义
- 是一个树,所以无回路
- V个顶点一定对应V- 1条边
- 是生成树,包含所有顶点,
- 最小生成树,权重之和最小
解决方法
贪心算法
每一步都是最好的(权重最小的)
相关约束:只能用图里面的边,只能用掉v - 1条边,不能有回路
prim算法(针对稠密图):让一颗小树长大,有点像迪佳斯特拉算法
kruskal算法(针对稀疏图):森林合并成树,主要看边!
村村通,我们想把几个村子(点)修路连接起来,所以肯定是修最小的路数量,同时想要修路的成本最低(权重)
贪心算法
每一步都是最好的(权重最小的)
相关约束:只能用图里面的边,只能用掉v - 1条边,不能有回路
prim算法(针对稠密图):让一颗小树长大,有点像迪佳斯特拉算法
kruskal算法(针对稀疏图):森林合并成树,主要看边!
本文标题:最小生成树
本文链接:https://www.haomeiwen.com/subject/ubyqcqtx.html
网友评论