2011年软考程序员考试知识点复习(39)

　　最小生成树算法之Kruskal算法:

　　算法思想:每次找最小的边,如果在已有的森林中加入该边后会形成回路,则舍弃,否则加入然后合并森林

　　n:点的个数;

　　edge_cnt:边的个数

　　edge[]:保存边的数组

　　edge_arr:保存选择边的数组,可选功能

　　*/

　　template

　　TMST_Kruskal(const int & n, const int & edge_cnt,Edge edge[], Edge* edge_arr = NULL)

　　{

　　T ans=0;

　　int i,x,y,p[N],cnt=0;

　　memset(p,-1,sizeof(p));

　　sort(edge,edge+edge_cnt);

　　for(i=0;i

　　{

　　x=FindSet(p,edge[i].from);

　　y=FindSet(p,edge[i].to);

　　if(x!=y)

　　{

　　UnionSet(p,x,y);

　　ans+=edge[i].cost;

　　if(edge_arr)

　　edge_arr[cnt]=edge[i];

　　cnt++;

　　if(cnt==n-1)

　　return ans;

　　}

　　}

　　return -1;

　　}