数据结构与算法-最小生成树之克鲁斯卡尔(Kruskal)算法

算法步骤

1. 设G = ( V,E ),令最小生成树初始状态为只有n个顶点而无边的非联通图 T=( V,{ } ),每个顶点自成一个连通分量;

2. 在E中选取权值最小的边,若该边依附的顶点落在T中不同的连通分量上,且不构成回路,则将此边加入到T 中,否则,舍去此边,选取下一条权值最小的边;

3. 以此类推,重复第2步,直至T中所有顶点都在同一连通分量上为止。

数据结构与算法-最小生成树之克鲁斯卡尔(Kruskal)算法

 

算法实例

假设现在我们已经通过邻接矩阵得到了边集数组并按权值从小到大排列如下图。

数据结构与算法-最小生成树之克鲁斯卡尔(Kruskal)算法

未完待续。。。