文件名称：最小生成树Kruskal
文件大小：2KB
文件格式：CPP
更新时间：2015-12-01 04:26:08
Kruskal算法
Kruskal算法 1.首先将G的n个顶点看成n个孤立的连通分支，将所有的边按权从小到大排序e1,e2,e3...em 2.从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接两个不同的两同分支 3.当查看到第K条边ek=(v,w)时，若v,w分别在两个不同而连通分支T1和T2中，用边（v,w）将T1,T2连接成一个连通分支，然后继续查看k+1条边 若v和w在当前的同一个连通分支中，就直接查看第k+1条边（既构成圈，就放弃ek） 这个过程一直进行到之剩下一个连通分支时为止。此时，这个连通分支就是G的一颗最小生成树了