prim算法和kruskal算法的区别

Question

如题所述

Answer 1

Prim算法和Kruskal算法的区别对比，主要是在实现过程的不同，Kruskal算法比Prim算法更效率。

Prim算法是通过直接查找，多次查找权重比值的最小值，来计算出最终答案。而Kruskal算法，是通过对权重排序后，再重新查找最小值实现的。

从效率上来说，Kruskal在算法比Prim算法快很多的。这是由于，Kruskal算法只需一次排序，就可以立马找到最小值，而Prim算法却要复杂的很多，需要多次排序，才能找到最小值。Prim算法的实现过程，在求值过程中，先以一个点作为最小的初始起点，然后以迭代的方式，找出各结点中，所占权重最小的边，并加到最小的系列中。

当所有的计算结点，都已经加入到预先设计的最小数列中，我们只需找出了这个连通图的最小结点，就能求出最小值。

Kruskal算法的实现过程，Kruskal算法是通过排序的方式，找到最小结点。在开始寻找之前，需要对权重从小到大进行排序。将排序好的权重，依次加入到序列中，而当所有的结点都加入到序列中后，我们就成功找到了这个最小值，速度方面要快很多。

Kruskal算法的时间复杂度

克鲁斯卡尔（Kruskal）算法的时间复杂度是O（ElogE），其中E是边的数量。具体的解释如下：

1、根据Kruskal算法的基本思想，需要将n个节点看成n颗单节点树，时间复杂度为O（n）；

2、构造各个边的时间复杂度为O（E）；

3、将所有边按权值排序的时间复杂度为O（ElogE）；

4、处理每一条边的时间复杂度为O（logn），总的时间复杂度为O（Elogn）；

综上所述，Kruskal算法的总时间复杂度为O（ElogE）。