概述
借助可视化工具分析一哈
https://visualgo.net
Kruskal（克鲁斯卡尔）算法
根据我的理解，就是每次选择一条权重最小的边，且加入这条边后不构成环路，最后组成一棵树
以下图的情形为例
- 初始状态
- 节点1 、 2之间权重最小，加入这条边
- 节点0 、1 与节点0 、 2之间权重都为4，加入其中一条
-
首先尝试将0 2 这条边加入，但是此时会构成回路
选择将权重为6的边加入
- 将权重为6的节点加入，此时每个节点都访问到了，最小生成树构成。
Prime算法
还是以上面的情形为例
- 我们一0为起始点，节点1 为节点0最少代价能到达的节点，将节点1加入
- 此时节点2为节0 或1 节点经过最少代价能到达的节点，将节点二2加入
- 此时节点2为节0 或1 节点经过最少代价能到达的节点，将节点二2加入
- 此时节点0 与 节点2 之间权重最小，但是会构成回路；选择节点3加入
- 加入节点4，所有节点都已经到达，构成树
- 加入节点4，所有节点都已经到达，构成树
放一个伪代码
最后
以上就是寒冷海燕为你收集整理的关于最小生成树算法的全部内容，希望文章能够帮你解决关于最小生成树算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复