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

　　#include

　　#include

　　#define MAXVEX 30

　　#define MAXCOST 1000

　　/*

　　每一步掃描數(shù)組lowcost，在V-U中找出離U最近的頂點(diǎn)，令其為k，并打印邊(k,closest[k]), 然后修改lowcost和closest，標(biāo)記k已經(jīng)假如U。c表示圖鄰接矩陣，弱不存在邊(i,j),則c[i][j]的值為一個(gè)大于任何權(quán)而小于無(wú)限打的闡述，這里用MAXCOST表示

　　*/

　　/*一直圖的頂點(diǎn)為{1,2,...,n},c[i][j]為(i,j)的權(quán)，打印最小生成樹(shù)的每條邊*/

　　void prim (int c[MAXVEX][MAXVEX], int n)

　　{

　　int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX];

　　for(i=2;i<=n;i++) /*從頂點(diǎn)1開(kāi)始*/

　　{

　　lowcost[i]=c[1][i];

　　closest[i]=1;

　　}

　　closest[1]=0;

　　for(i=2;i<=n;i++) /*從U之外求離U中某一頂點(diǎn)最近的頂點(diǎn)*/

　　{

　　min=MAXCOST;

　　j=1;

　　k=i;

　　while(j<=n)

　　{

　　if(lowcost[j]

　　{

　　min=lowcost[j];

　　k=j;

　　}

　　j++;

　　}

　　printf("(%d,%d)",closest[k],k); /*打印邊*/

　　closest[k]=0;/* k假如到U中 */

　　for(j=2;j<=n;j++)

　　if(closest[j]!=0 && c[k][j]

　　{

　　lowcost[j]=c[k][j];

　　closest[j]=k;

　　}

　　}

　　}

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

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

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