最 小生成树.zip

Kruskal(克鲁斯卡尔算法)算法介绍: 设G=(V,E)是无向带权连通图,V={1,2,...,n};设最小生成树T=(V,TE),该树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),Kruskal算法将这n个顶点看成是n个孤立的连通分支。它首先将所有的边按权值从小到大排序,然后只要T中选中的边数不到n−1,就做如下的贪心选择:在边集E中选取权值最小的边E(i,j),如果将边E(i,j)加入集合TE中不产生回路(圈),则将边E(i,j)加入边集TE中,即用边E(i,j)将这两个连通分支合并连接成一个连通分支;否则继续选择下一条最短边。把边E(i,j)从集合E中删去。继续上面的贪心选择