克鲁斯卡尔(Kruskal)算法
基本介绍
克鲁斯卡尔算法是用来求加权连通图的最小生成树的算法。
基本思想
按照权值从小到大的顺序选择n-1条边,并保证这n-1条边不构成回路。
首先构造一个只含n个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止
问题举例
1、某城市新增7个站点(A, B, C, D, E, F, G) ,现在需要修路把7个站点连通
2、各个站点的距离用边线表示(权) ,比如 A – B 距离 12公里
3、问:如何修路保