克鲁斯算法原理（十大常用算法之克鲁斯卡尔算法）

1.

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

2.

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

3.

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