廣工數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)最小生成樹

1、課程設(shè)計(jì)課程名稱 數(shù)據(jù)結(jié)構(gòu) 學(xué) 院 專業(yè)班級(jí) 學(xué) 號(hào) 學(xué)生姓名 指導(dǎo)教師 2015年7月2日1. 需求分析 題目：最小生成樹問(wèn)題若要在n個(gè)城市之間建設(shè)通訊網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通訊網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問(wèn)題。要求： （1）利用克魯斯卡爾算法求網(wǎng)的最小生成樹。 （2）實(shí)現(xiàn)并查集。以此表示構(gòu)造生成樹過(guò)程中的連通分量。（3） 以文本形式輸出生成樹中各條邊以及他們的權(quán)值。輸入的形式和輸入值的范圍：十進(jìn)制數(shù)，0100。輸出的形式：十進(jìn)制數(shù)。程序所能達(dá)到的功能：遍歷所有城市生成最小生成樹。測(cè)試數(shù)據(jù)： 正確數(shù)據(jù)： 城市個(gè)數(shù)3；3個(gè)城市的鄰接矩陣：(1,2,3;2,1

2、00,4;3,4,6) 輸出結(jié)果：第1條路段為12，權(quán)值為2 第2條路段為13，權(quán)值為3 遍歷所有城市得到最小生成樹的代價(jià)為：5 錯(cuò)誤數(shù)據(jù)：城市個(gè)數(shù)3；城市的鄰接矩陣：(-2,5,1;3,0,1;3,2,1) 輸出結(jié)果：輸入錯(cuò)誤，請(qǐng)重新輸入2.概要設(shè)計(jì) 數(shù)據(jù)類型定義如下： typedef struct node int str; /*起點(diǎn)*/ int end; /*終點(diǎn)*/ int dis;/*距離*/node;node pmax,temp; /*p記錄城市信息*/ int pre100,rank100;/*用于判斷是否構(gòu)成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表

3、示城市個(gè)數(shù)，arcs記錄城市間權(quán)值*/主程序流程如下：3.詳細(xì)設(shè)計(jì) （1）克魯斯卡爾算法思想基本描述：假設(shè)連通圖N=（V，E），則令最小生成樹的初始狀態(tài)為只有n 頂點(diǎn)而無(wú)邊的非連通圖T=(V, )，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。以此類推，直至T中所有頂點(diǎn)都在同一個(gè)連通分量上為止。 （2）克魯斯卡爾算法設(shè)計(jì)：a.  設(shè)置計(jì)數(shù)器E，初值為0，記錄已選中的邊數(shù)。將所有邊從小到大排序，存于p 中。 b. 從p 中選擇一條

4、權(quán)值最小的邊，檢查其加入到最小生成樹中是否會(huì)構(gòu)成回路，若是，則此邊不加入生成樹；否則，加入到生成樹中，計(jì)數(shù)器E累加1。c. 從E中刪除此最小邊，轉(zhuǎn)b繼續(xù)執(zhí)行，直到k=n-1, 算法結(jié)束 。判斷是否回路：設(shè)置集合S，其中存放已加入到生成樹中的邊所連接的頂點(diǎn)集合，當(dāng)一條新的邊要加入到生成樹中時(shí)，檢查此邊所連接的兩個(gè)頂點(diǎn)是否都已經(jīng)在S中，若是，則表示構(gòu)成回路，否則，若有一個(gè)頂點(diǎn)不在S中   或者兩個(gè)頂點(diǎn)都不在S中，則不夠成回路。/*需要的函數(shù)聲明*/int   main (  )&

5、#160;            /主程序int   menu (  )            /菜單函數(shù)void  create (  )         &

6、#160; /輸入城市信息函數(shù)void  judge (  )            /判斷是否能夠生成最小生成樹函數(shù)void  display(  )          /打印輸出void  set (  ) 

7、0;          /初始化pre,rank函數(shù)void  find  (  )         /判斷是否構(gòu)成回路函數(shù)void  Union (  )        /將能構(gòu)成最小生成樹的邊添加到一個(gè)集合void&

8、#160; Krushal(  )       /克魯斯算法求最小生成樹/*菜單函數(shù)*/int menu( ) int m; printf(".2015年7月2日.nn"); printf(" 求最小生成樹n"); printf(" _nn"); printf(" 1 輸入城市之間的信息n"); printf(" 2 判斷是否能構(gòu)成一個(gè)最小生成樹n"); printf(" 3 遍歷所有城

9、市生成最小生成樹n"); printf(" 0 退出n"); printf(" _nn"); printf(" 請(qǐng)輸入所選功能0-3n"); scanf("%d",&m); if(m<0|m>3) return 4; return m; /*下面三個(gè)函數(shù)作用是檢驗(yàn)當(dāng)一條邊添加進(jìn)去，是否會(huì)產(chǎn)生回路*/void set(int x)/*初始化*/ prex = x; rankx = 0;/*找到這個(gè)點(diǎn)的祖先*/ int find(int x) if(x != prex) prex = fi

10、nd(prex); return prex; /*將這兩個(gè)數(shù)添加到一個(gè)集合里去*/ void Union(int x,int y) x = find(x); y = find(y); if(rankx >= ranky) prey = x; rankx +; else prey = x;/*克魯斯算法求最小生成樹*/void Kruskal( ) int ans = 0,i,j,k = 0; /*ans用來(lái)記錄生成最小樹的權(quán)總值*/ int index; int count = 0; /*記錄打印邊的條數(shù)*/ for(i = 1;i <= n;i +) /*初始化數(shù)組prex,ra

11、nkx*/ set(i); for(i = 1;i <= n;i +) for(j = i + 1;j <= n;j +) p+k.str = i; pk.end = j; pk.dis = arcsij; /*先把所有城市之間的路段看成一個(gè)邊*/ for(i=1;i<=k;i+) /*把所有的邊按從小到大進(jìn)行排序*/ index=i; for(j=i+1;j<=k;j+) if(pj.dis <pindex.dis) index=j; temp=pindex; pindex=pi; pi=temp; for(i = 1;i <= k;i +) if(fin

12、d(pi.str) != find(pi.end)/*如果這兩點(diǎn)連接在一起不構(gòu)成一個(gè)回路，則執(zhí)行下面操作*/ printf("t第%d條路段為：%d-%d,權(quán)值為%dn",+ count,pi.str,pi.end,pi.dis);/*將這條邊的起點(diǎn)、終點(diǎn)打印出來(lái)*/ ans += pi.dis; /*說(shuō)明這條路段要用*/ Union(pi.str,pi.end); printf("t遍歷所有城市得到最小生成樹的代價(jià)為: %dnn",ans);/*輸入城市信息*/ void create( ) int i,j; printf("請(qǐng)輸入城市的個(gè)數(shù)

13、（130）:n"); scanf("%d",&n); if(n<=0|n>30) printf("輸入錯(cuò)誤，請(qǐng)重新輸入n");return ; printf("輸入%d個(gè)城市存儲(chǔ)邊(帶權(quán))的數(shù)組（數(shù)值范圍：1-99，用100表示，）:n",n); for(i = 1;i <= n;i +) for(j = 1;j <= n;j +) scanf("%d",&arcsij); if(arcsij<1|arcsij>100) printf("輸入錯(cuò)

14、誤，請(qǐng)重新輸入n"); return ; for(i=0;i<n;i+) for(j=0;j<i;j+) if(arcsij!=arcsji) /*判斷矩陣是否對(duì)稱*/ printf("輸入錯(cuò)誤，請(qǐng)重新輸入n"); return ;/*顯示生成的最小生成樹*/void display( ) if(n = 0) printf("這里沒(méi)有城市之間的信息n"); return; printf("遍歷所有城市得到最小生成樹為：nnn"); Kruskal( );/*判斷是否能夠生成最小生成樹*/void judge( )

15、 int close100,low100,i,j,ans = 0;/*closej表示離j最近的頂點(diǎn)，lowj表示離j最短的距離*/ int use100; use1 = 1; for(i = 2;i <= n;i +) lowi = arcs1i; /*初始化*/ closei = 1; usei = 0; for(i = 1;i < n;i +) int min = 100000000,k = 0; for(j = 2;j <= n;j +) if(usej = 0 && min > lowj)/*找到最小的low值，并記錄*/ min = lowj

16、; k = j; for(j = 2;j <= n;j +) if(usej = 0 && lowj > arcskj) lowj = arcskj; /*修改low值和close值*/ closej = k; ans += arcsclosekk; if(ans >= 100000000) printf("不能構(gòu)成最小生成樹n"); else printf("能構(gòu)成最小生成樹n");/*主函數(shù)*/void main() while(1) switch( menu( ) ) case 1:create( );break;

17、/*輸入城市信息*/ case 2:judge( );break;/*判斷是否能夠生成最小生成樹*/ case 3:display( );break; /*顯示生成的最小生成樹*/ case 0:exit( ); default: printf("輸入錯(cuò)誤，請(qǐng)重新選擇。n"); break; 4.調(diào)試分析本課程設(shè)計(jì)重點(diǎn)在于生成最小生成樹算法?？唆斔箍査惴▽D中邊按其權(quán)值由小到大的次序順序選取,若選邊后不形成回路,則保留作為一條邊,若形成回路則除去，依次選夠(n-1)條邊,即得最小生成樹。在克魯斯卡爾算法中，圖的存貯結(jié)構(gòu)采用邊集數(shù)組,且權(quán)值相等的邊在數(shù)組中排列次序可以是任意

18、的，該方法對(duì)于邊相對(duì)比較多的不是很實(shí)用。本課程設(shè)計(jì)為求最小生成樹，先要構(gòu)造一個(gè)結(jié)構(gòu)體，再用鄰接矩陣的形式表現(xiàn)出來(lái)。城市間的距離網(wǎng)使用鄰接矩陣表示，鄰接矩陣存儲(chǔ)方法（數(shù)組存儲(chǔ)方法），利用兩個(gè)數(shù)組來(lái)存儲(chǔ)一個(gè)圖。用a i j數(shù)組，利用鄰接矩陣方式來(lái)儲(chǔ)存城市與城市間信息 。5.用戶使用說(shuō)明 按順序依次輸入城市之間的信息，判斷是否能構(gòu)成一個(gè)最小生成樹，再生成遍歷所有城市的最小生成樹。如果輸入過(guò)程中出現(xiàn)錯(cuò)誤，需重新輸入。城市存儲(chǔ)邊(帶權(quán))矩陣中的用100表示，矩陣必須對(duì)稱。6.測(cè)試結(jié)果7. 源代碼#include<stdio.h>#include <stri

19、ng.h> #include <stdlib.h>#define max 100#define MAX_LNT 30typedef struct node /*構(gòu)造一個(gè)結(jié)構(gòu)體，兩個(gè)城市可以看成起點(diǎn)和終點(diǎn)，之間的道路可以看成一個(gè)邊*/ int str; /*起點(diǎn)*/ int end; /*終點(diǎn)*/ int dis;/*距離*/node;node pmax,temp; /*p記錄城市信息*/ int pre100,rank100;/*用于判斷是否構(gòu)成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市個(gè)數(shù)，arcs記錄城市間權(quán)值*/int menu( )

20、/*菜單函數(shù)*/ int m; printf(".2015年7月2日.nn"); printf(" 求最小生成樹n"); printf(" _nn"); printf(" 1 輸入城市之間的信息n"); printf(" 2 判斷是否能構(gòu)成一個(gè)最小生成樹n"); printf(" 3 遍歷所有城市生成最小生成樹n"); printf(" 0 退出n"); printf(" _nn"); printf(" 請(qǐng)輸入所選功能0-3n

21、"); scanf("%d",&m); if(m<0|m>3) return 4; return m; /*下面三個(gè)函數(shù)作用是檢驗(yàn)當(dāng)一條邊添加進(jìn)去，是否會(huì)產(chǎn)生回路*/void set(int x)/*初始化*/ prex = x; rankx = 0; int find(int x)/*找到這個(gè)點(diǎn)的祖先*/ if(x != prex) prex = find(prex); return prex; void Union(int x,int y)/*將這兩個(gè)添加到一個(gè)集合里去*/ x = find(x); y = find(y); if(rank

22、x >= ranky) prey = x; rankx +; else prey = x;/*克魯斯算法求最小生成樹*/void Kruskal( ) int ans = 0,i,j,k = 0; /*ans用來(lái)記錄生成最小樹的權(quán)總值*/ int index; int count = 0; /*記錄打印邊的條數(shù)*/ for(i = 1;i <= n;i +) /*初始化數(shù)組prex,rankx*/ set(i); for(i = 1;i <= n;i +) for(j = i + 1;j <= n;j +) p+k.str = i; pk.end = j; pk.dis

23、 = arcsij; /*先把所有城市之間的路段看成一個(gè)邊*/ for(i=1;i<=k;i+) /*把所有的邊按從小到大進(jìn)行排序*/ index=i; for(j=i+1;j<=k;j+) if(pj.dis <pindex.dis) index=j; temp=pindex; pindex=pi; pi=temp; for(i = 1;i <= k;i +) if(find(pi.str) != find(pi.end)/*如果這兩點(diǎn)連接在一起不構(gòu)成一個(gè)回路，則執(zhí)行下面操作*/ printf("t第%d條路段為：%d-%d,權(quán)值為%dn",+ c

24、ount,pi.str,pi.end,pi.dis);/*將這條邊的起點(diǎn)、終點(diǎn)打印出來(lái)*/ ans += pi.dis; /*說(shuō)明這條路段要用*/ Union(pi.str,pi.end); printf("t遍歷所有城市得到最小生成樹的代價(jià)為: %dnn",ans);/*輸入城市信息*/ void create( ) int i,j; printf("請(qǐng)輸入城市的個(gè)數(shù)（130）:n"); scanf("%d",&n); if(n<=0|n>30) printf("輸入錯(cuò)誤，請(qǐng)重新輸入n");r

25、eturn ; printf("輸入%d個(gè)城市存儲(chǔ)邊(帶權(quán))的數(shù)組（數(shù)值范圍：1-99，用100表示，）:n",n); for(i = 1;i <= n;i +) for(j = 1;j <= n;j +) scanf("%d",&arcsij); if(arcsij<1|arcsij>100) printf("輸入錯(cuò)誤，請(qǐng)重新輸入n"); return ; for(i=0;i<n;i+) for(j=0;j<i;j+) if(arcsij!=arcsji) /*判斷矩陣是否對(duì)稱*/ printf("輸入錯(cuò)誤，請(qǐng)重新輸入n"); return ;/*顯示生成的最小生成樹*/ void display( ) if(n = 0) printf("這里沒(méi)有城市之間的信息n"); re