克鲁斯卡尔算法 克鲁斯卡尔算法例题图解

一、克鲁斯卡尔算法和普利姆算法求最小生成树哪个更快

不总是一样的，克鲁斯卡尔算法是精确算法，即每次都能求得最优解，但对于规模较大的最小生成树问题，求解速度较慢。而普里姆算法是近似求解算法，虽然对于大多数最小生成树问题都能求得最优解，但相当一部分求得的是近似最优解。这是我个人见解。

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

克鲁斯卡尔算法：

是在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。。

普里姆算法：

同样是在未选取的边中寻找最小边，但是选取的原则多了一条，就是该边必须和已选取的边相连，比如，如果边(1,2)已被选取，那么接下来选取的边，必须是和顶点1，或者顶点2相连的。。就是这样。。

三、克鲁斯算法原理

1.

克鲁斯卡尔(Kruskal)算法,是用来求加权连通图的最小生成树的算法。

2.

基本思想:按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路

3.

具体做法:首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止