#definen6#defineMaxNum10000/*定義一個(gè)最大整數(shù)*//*定義鄰接矩陣類型*/typedefint">

普里姆算法(prim)求最小生成樹(shù)c程序

ID:13004626

大小:77.50 KB

頁(yè)數(shù):5頁(yè)

時(shí)間:2018-07-20

普里姆算法(prim)求最小生成樹(shù)c程序_第1頁(yè)
普里姆算法(prim)求最小生成樹(shù)c程序_第2頁(yè)
普里姆算法(prim)求最小生成樹(shù)c程序_第3頁(yè)
普里姆算法(prim)求最小生成樹(shù)c程序_第4頁(yè)
普里姆算法(prim)求最小生成樹(shù)c程序_第5頁(yè)
資源描述:

《普里姆算法(prim)求最小生成樹(shù)c程序》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、1程序測(cè)試用例如下:561425523463465程序運(yùn)行過(guò)程截圖:源程序清單如下:#include#definen6#defineMaxNum10000/*定義一個(gè)最大整數(shù)*//*定義鄰接矩陣類型*/typedefintadjmatrix[n+1][n+1];/*0號(hào)單元沒(méi)用*/typedefstruct{intfromvex,tovex;intweight;}Edge;typedefEdge*EdgeNode;intarcnum;/*邊的個(gè)數(shù)*//*建立圖的鄰接矩陣*/voidCreatMatrix(adjmatri

2、xGA){inti,j,k,e;printf("圖中有%d個(gè)頂點(diǎn)",n);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j){GA[i][j]=0;/*對(duì)角線的值置為0*/}else{GA[i][j]=MaxNum;/*其它位置的值置初始化為一個(gè)最大整數(shù)*/}}}printf("請(qǐng)輸入邊的個(gè)數(shù):");scanf("%d",&arcnum);printf("請(qǐng)輸入邊的信息,按照起點(diǎn),終點(diǎn),權(quán)值的形式輸入:");for(k=1;k<=arcnum;k++){scanf("%d,%d,%d",&i,

3、&j,&e);/*讀入邊的信息*/GA[i][j]=e;GA[j][i]=e;}}/*初始化圖的邊集數(shù)組*/voidInitEdge(EdgeNodeGE,intm){inti;for(i=1;i<=m;i++){GE[i].weight=0;}}/*根據(jù)圖的鄰接矩陣生成圖的邊集數(shù)組*/voidGetEdgeSet(adjmatrixGA,EdgeNodeGE){inti,j,k=1;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(GA[i][j]!=0&&GA[i][j]!=MaxNum){GE[k].

4、fromvex=i;GE[k].tovex=j;GE[k].weight=GA[i][j];k++;}}}}/*按升序排列圖的邊集數(shù)組*/voidSortEdge(EdgeNodeGE,intm){inti,j,k;Edgetemp;for(i=1;iGE[j].weight){k=j;}}if(k!=i){temp=GE[i];GE[i]=GE[k];GE[k]=temp;}}}/*利用普里姆算法從初始點(diǎn)v出發(fā)求鄰接矩陣表示的圖的最小生成樹(shù)*

5、/voidPrim(adjmatrixGA,EdgeNodeT){inti,j,k,min,u,m,w;Edgetemp;/*給T賦初值,對(duì)應(yīng)為v1依次到其余各頂點(diǎn)的邊*/k=1;for(i=1;i<=n;i++){if(i!=1){T[k].fromvex=1;T[k].tovex=i;T[k].weight=GA[1][i];k++;}}/*進(jìn)行n-1次循環(huán),每次求出最小生成樹(shù)中的第k條邊*/for(k=1;k

6、=T[j].weight;m=j;}}/*把最短邊對(duì)調(diào)到k-1下標(biāo)位置*/temp=T[k];T[k]=T[m];T[m]=temp;/*把新加入最小生成樹(shù)T中的頂點(diǎn)序號(hào)賦給j*/j=T[k].tovex;/*修改有關(guān)邊,使T中到T外的每一個(gè)頂點(diǎn)保持一條到目前為止最短的邊*/for(i=k+1;i

7、e){inti;printf("按照起點(diǎn),終點(diǎn),權(quán)值的形式輸出的最小生成樹(shù)為:");for(i=1;i<=e;i++){printf("%d,%d,%d",GE[i].fromvex,GE[i].tovex,GE[i].weight);}}voidmain(){adjmatrixGA;EdgeGE[n*(n-1)/2],T[n];CreatMatrix(GA);InitEdge(GE,arcnum);GetEdgeSet(GA,GE);SortEdge(GE,arcnum);Prim(GA,T);printf("");OutE

8、dge(T,n-1);}

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文

此文檔下載收益歸作者所有

當(dāng)前文檔最多預(yù)覽五頁(yè),下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學(xué)公式或PPT動(dòng)畫(huà)的文件,查看預(yù)覽時(shí)可能會(huì)顯示錯(cuò)亂或異常,文件下載后無(wú)此問(wèn)題,請(qǐng)放心下載。
2. 本文檔由用戶上傳,版權(quán)歸屬用戶,天天文庫(kù)負(fù)責(zé)整理代發(fā)布。如果您對(duì)本文檔版權(quán)有爭(zhēng)議請(qǐng)及時(shí)聯(lián)系客服。
3. 下載前請(qǐng)仔細(xì)閱讀文檔內(nèi)容,確認(rèn)文檔內(nèi)容符合您的需求后進(jìn)行下載,若出現(xiàn)內(nèi)容與標(biāo)題不符可向本站投訴處理。
4. 下載文檔時(shí)可能由于網(wǎng)絡(luò)波動(dòng)等原因無(wú)法下載或下載錯(cuò)誤,付費(fèi)完成后未能成功下載的用戶請(qǐng)聯(lián)系客服處理。
关闭