克鲁斯卡尔 | 普里姆算法和克鲁斯卡尔算法区别

一、普里姆算法和克鲁斯卡尔算法区别

克鲁斯卡尔 | 普里姆算法和克鲁斯卡尔算法区别

1、普里姆算法和克鲁斯卡尔算法区别如下：

2、克鲁斯卡尔算法：是在剩下的一切未选取的边中，找最小边，假设和已选取的边构成回路，则坚持，选取次小边。

3、普里姆算法：异样是在未选取的边中寻觅最小边，但是选取的准绳多了一条，就是该边必需和已选取的边相连，比如，假设边(1, 2)已被选取，那么接上去选取的边，必需是和顶点1，或许顶点2相连的。

二、克鲁斯卡尔算法是贪心算法吗

1、克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为复杂了解的一个。这外面充沛表现了贪心算法的精髓。

2、克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适宜于求边稀疏的网的最小生成树。

3、克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假定连通网G=（V，E），令最小生成树的初始形状为只要n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通重量。

4、在E中选择代价最小的边，若该边依靠的顶点区分在T中不同的连通重量上，则将此边参与到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中一切顶点构成一个连通重量为止。

5、克鲁斯卡尔算法思想设计克鲁斯卡尔算法函数主要包括两个局部：首先是带权图G中e条边的权值的排序；其次是判别新选取的边的两个顶点能否属于同一个连通重量。对带权图G中e条边的权值的排序方法可以有很多种，各自的时间复杂度均不相反。

6、对e条边的权值排序算法时间复杂度较好的算法有快速排序法、堆排序法等，这些排序算法的时间复杂度均可以到达O（elge）。判别新选取的边的两个顶点能否属于同一个连通重量的效果是一个在最多有n个顶点的生成树中遍历寻觅新选取的边的两个顶点能否存在的效果，此算法的时间复杂度最坏状况下为O（n）。

标签：