用Kruskal算法求無向圖的最小生成樹.doc

ID:52793889

大小:112.00 KB

頁數(shù):14頁

時(shí)間:2020-03-30

用Kruskal算法求無向圖的最小生成樹.doc_第1頁
用Kruskal算法求無向圖的最小生成樹.doc_第2頁
用Kruskal算法求無向圖的最小生成樹.doc_第3頁
用Kruskal算法求無向圖的最小生成樹.doc_第4頁
用Kruskal算法求無向圖的最小生成樹.doc_第5頁
資源描述:

《用Kruskal算法求無向圖的最小生成樹.doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、用Kruskal算法求無向圖的最小生成樹該圖用鄰接矩陣表示,鄰接表原理與之相同??梢灾赋龅氖?,對(duì)于有向圖,算法可以做得更加簡單,因?yàn)閷?duì)無向圖的“回邊”情況的處理比有向圖回邊情況的處理要復(fù)雜一些。圖1:輸入示例圖二:輸入時(shí)若兩點(diǎn)之間沒有公共邊,則將權(quán)值設(shè)置為-1。程序設(shè)置處理的最大點(diǎn)數(shù)為10。圖三:注意到Kruskal算法的解答結(jié)果有時(shí)候不是唯一的,這個(gè)結(jié)果和對(duì)圖遍歷時(shí)的順序有關(guān),但是必需注意的是所有的最小生成樹其網(wǎng)絡(luò)代價(jià)和是一樣的。下面是源代碼:/*Kruskal.c?Copyright(c)2002,2006byctu

2、_85AllRightsReserved.*//*Iamsorrytosaythatthesituationofunconnectedgraphisnotconcerned*/#include"stdio.h"#definemaxver10#definemaxright100intG[maxver][maxver],record=0,touched[maxver][maxver];intcircle=0;intFindCircle(int,int,int,int);intmain(){intpath[maxver][2]

3、,used[maxver][maxver];inti,j,k,t,min=maxright,exsit=0;intv1,v2,num,temp,status=0;restart:printf("Pleaseenterthenumberofvertex(s)inthegraph:");scanf("%d",&num);if(num>maxver

4、

5、num<0){printf("Error!Pleasereinput!");gotorestart;}for(j=0;j

6、+){if(j==k){G[j][k]=maxright;used[j][k]=1;touched[j][k]=0;}elseif(j=maxright

7、

8、temp<-1){printf("Invalidinput!");gotore;}if(temp==-1)te

9、mp=maxright;G[j][k]=G[k][j]=temp;used[j][k]=used[k][j]=0;touched[j][k]=touched[k][j]=0;}}for(j=0;j

10、++){for(j=0;j

11、ath[t][0]);if(circle){/*ifacircleexsits,rollback*/circle=0;i--;exsit=0;touched[v1][v2]=0;touched[v2][v1]=0;min=maxright;}else{record++;min=maxright;}}}if(!status)printf("Wecannotdealwithitbecausethegraphisnotconnected!");else{for(i=0;i

12、vertex%dtovertex%d",i+1,path[i][0]+1,path[i][1]+1);}return1;}intFindCircle(intstart,intbegin,inttimes,intpre){/*tojudgewhetheracircleisproduced*/inti;for(i=0

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

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

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