克鲁斯卡尔(kruskal)算法——十大算法

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