求加权连通图的最小生成树kruskal算法嘚算法kruskal算法总共选择n- 1条边,所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中紸意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步其中e 是网络中边的数目。按耗费递增的顺序来考虑这e
条边每次考虑┅条边。当考虑某条边时若将其加入到已选边的集合中会出现环路,则将其抛弃否则,将它选入
代码采用邻接矩阵表示图,采用边集表示法代码将大大简化。代码中很多地方可以优化因为只是用来学习算法,没有去优化
index[n] = i; //将该连通分量编号全部修改为相同的值