2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(11)

　　最小生成樹(shù)算法之Kruskal算法:

　　算法思想:每次找最小的邊,如果在已有的森林中加入該邊后會(huì)形成回路,則舍棄,否則加入然后合并森林

　　n:點(diǎn)的個(gè)數(shù);

　　edge_cnt:邊的個(gè)數(shù)

　　edge[]:保存邊的數(shù)組

　　edge_arr:保存選擇邊的數(shù)組,可選功能

　　*/

　　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;

　　}

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

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