最小生成樹算法之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;

　　}

　　軟考程序員考試歷年真題重點題總結及答案

　　2011年上半年軟考報名時間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)