借助可视化工具分析一哈
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，所有节点都已经到达，构成树
放一个伪代码
最后
以上就是寒冷海燕最近收集整理的关于关于最小生成树算法的全部内容，更多相关关于最小生成树算法内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复