【最小生成树】Prim算法和Kruskal算法的区别对比

96 阅读 0 评论 64 点赞

我是靠谱客的博主孝顺指甲油，最近开发中收集的这篇文章主要介绍【最小生成树】Prim算法和Kruskal算法的区别对比，觉得挺不错的，现在分享给大家，希望可以做个参考。

Prim算法和Kruskal算法都是从连通图中找出最小生成树的经典算法～

从策略上来说，Prim算法是直接查找，多次寻找邻边的权重最小值，而Kruskal是需要先对权重排序后查找的～

所以说，Kruskal在算法效率上是比Prim快的，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到～

首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树～

Kruskal算法在找最小生成树结点之前，需要对权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中（如果加入时产生回路就跳过这条边，加入下一条边），当所有的结点都加入到最小生成树中后，就找到了这个连通图的最小生成树～

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。