廣工數據結構課程設計最小生成樹

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

2、4,6）輸出結果：第1條路段為12,權值為2第2條路段為1 3,權值為3遍歷所有城市得到最小生成樹的代價為：5錯誤數據：城市個數3;城市的鄰接矩陣：（-2,5,1;3,0,1;3,2,1）輸出結果：輸入錯誤，請重新輸入2概要設計數據類型定義如下：typedef struct nodeint str; /* 起點 */intend; /* 終點 */int dis;/* 距離 */n ode;node pmax,temp; /*p 記錄城市信息 */int pre100,rank100;/*用于判斷是否構成回路*/權值*/主程序流程如下初始化將昂小生成樹邊集合打印出顯小生成樹 的權值與晟小生成樹

3、的 代價int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市個數，arcs叩記錄城市間是否構成回路？開始1r輸入城市信息1F1求蛀小生成樹退岀i育為連通3詳細設計(1) 克魯斯卡爾算法思想基本描述：假設連通圖N= (V , E)，貝冷最小生成樹的初始狀態(tài)為只有 n頂點而無 邊的非連通圖T=(V, )，圖中每個頂點自成一個連通分量。在 E中選擇代價最 小的邊，若該邊依附的頂點落在 T中不同的連通分量上，則將此邊加入到 T中, 否則舍去此邊而選擇下一條代價最小的邊。以此類推，直至 T中所有頂點都在 同一個連通分量上為止。(2) 克魯斯卡爾算法設計：a. 設置計數器E，初值為0,記錄

4、已選中的邊數。將所有邊從小到大排序， 存于p中。b. 從p中選擇一條權值最小的邊，檢查其加入到最小生成樹中是否會構成 回路，若是，貝吐匕邊不加入生成樹；否則，加入到生成樹中，計數器 E累加1。c. 從E中刪除此最小邊，轉b繼續(xù)執(zhí)行，直到k=n-1,算法結束。判斷是否回路：設置集合S,其中存放已加入到生成樹中的邊所連接的頂點集合，當一條新 的邊要加入到生成樹中時，檢查此邊所連接的兩個頂點是否都已經在 S中，若是, 則表示構成回路，否則，若有一個頂點不在 S中或者兩個頂點都不在S中，則不夠成回路。/*需要的函數聲明*/int mai n ( )/主程序int me nu ( )/菜單函數void

5、create ( )/輸入城市信息函數void judge ( )/判斷是否能夠生成最小生成樹函數void display( )/ 打印輸出void set ( )/初始化 pre,rank函數void find ( )/判斷是否構成回路函數void Union ( )/將能構成最小生成樹的邊添加到一個集合void Krushal()克魯斯算法求最小生成樹/*菜單函數*/int menu() int m;printf("2015年 7 月 2 日nn");printf("求最小生成樹n");prin tf("nn");printf(&

6、quot;1輸入城市之間的信息n");prin tf("2判斷是否能構成一個最小生成樹n");printf("3遍歷所有城市生成最小生成樹n");prin tf("0 退出 n");prin tf("nn");printf("請輸入所選功能0-3n");sea nf("%d",&m);if(m<0|m>3) return 4;return m;/*下面三個函數作用是檢驗當一條邊添加進去，是否會產生回路*/void set(int x)/* 初始化

7、 */prex = x;ran kx = 0;/*找到這個點的祖先*/int fin d(i nt x)if(x != prex)prex = fin d(prex);return prex;/*將這兩個數添加到一個集合里去*/void Union (i nt x,i nt y)x = fin d(x);y = fin d(y);if(ran kx >= ran ky)prey = x;ran kx +;else prey = x;/*克魯斯算法求最小生成樹*/void Kruskal()int ans = O,i,j,k = 0; /*ans用來記錄生成最小樹的權總值*/int in

8、dex;int count = 0;/*記錄打印邊的條數*/for(i = 1;i <= n;i +)/*初始化數組 prex,rankx*/set(i);for(i = 1;i <= n;i +)for(j = i + 1;j <= n;j +)p+k.str = i;pk.e nd = j;pk.dis = arcsij; /*先把所有城市之間的路段看成一個邊*/for(i=1;i<=k;i+)/*把所有的邊按從小到大進行排序*/in dex=i;for(j=i+1;j<=k;j+) if(pj.dis <pi ndex.dis)in dex=j;tem

9、p=pi ndex;pi ndex=pi;pi=temp;for(i = 1;i <= k;i +)if(find(pi.str) != find(pi.end)/*如果這兩點連接在一起不構成一個回路，則 執(zhí)行下面操作*/printf("t第 %d 條路段為：d-%d,權值為 dn",+count,pi.str,pi.end,pi.dis);/*將這條邊的起點、終點打印出來*/ans += pi.dis; /*說明這條路段要用*/Union( pi.str,pi.e nd);printf("t遍歷所有城市得到最小生成樹的代價為：%dnn",ans)

10、;/*輸入城市信息*/void create()int i,j;printf("請輸入城市的個數(1 30):n");sca nf("%d",&n);if(*=0|n>30) printf("輸入錯誤，請重新輸入 n");return ; printf("輸入%d個城市存儲邊(帶權)的數組(數值范圍：1-99, 用 100表示，)：n",n);for(i = 1;i <= n;i +)for(j = 1;j <= n;j +)sea nf("%d",&arcsi

11、j);if(arcsij<1|arcsij>100)printf("輸入錯誤，請重新輸入n");return ;for(i=0;i <n ;i+)for(j=0;j<i;j+)if(arcsij!=arcsji)/* 判斷矩陣是否對稱 */printf("輸入錯誤，請重新輸入n");return ;/*顯示生成的最小生成樹*/void display( )if(n = 0)printf("這里沒有城市之間的信息n");return;printf("遍歷所有城市得到最小生成樹為：nnn");K

12、ruskal();/*判斷是否能夠生成最小生成樹*/void judge()lowj表示離jint close100,low100,i,j,ans = 0;/*closej表示離 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 > lo

13、wj)/* 找到最小的 low值，并記錄 */min = lowj;k = j;for(j = 2;j <= n;j +)if(usej = 0 && lowj > arcskj)Iowj = arcskj; /* 修改 low值和 close值*/closej = k;ans += arcsclosekk;if(ans >= 100000000) printf("不能構成最小生成樹 n");elseprintf("能構成最小生成樹n");/*主函數*/void mai n()while(1)switch( menu()

14、case 1:create( );break;/輸入城市信息 */case 2:judge( );break;/*判斷是否能夠生成最小生成樹 */case 3:display( );break; /*顯示生成的最小生成樹*/case 0:exit();default:prin tf("輸入錯誤，請重新選擇。n");break;4調試分析本課程設計重點在于生成最小生成樹算法?？唆斔箍査惴▽D中邊按其權值由小到大的次序順序選取，若選邊后不形成回路，則保留作為一條邊，若形成回 路則除去，依次選夠（n-1）條邊，即得最小生成樹。在克魯斯卡爾算法中，圖的存 貯結構采用邊集數組，且權

15、值相等的邊在數組中排列次序可以是任意的，該方法 對于邊相對比較多的不是很實用。本課程設計為求最小生成樹，先要構造一個結構體，再用鄰接矩陣的形式表 現出來。城市間的距離網使用鄰接矩陣表示，鄰接矩陣存儲方法（數組存儲方法）， 利用兩個數組來存儲一個圖。用a i j數組，利用鄰接矩陣方式來儲存城市與城 市間信息。5用戶使用說明按順序依次輸入城市之間的信息，判斷是否能構成一個最小生成樹，再生成 遍歷所有城市的最小生成樹。如果輸入過程中出現錯誤，需重新輸入。城市存儲 邊（帶權）矩陣中的*用 100表示，矩陣必須對稱。6測試結果7.源代碼#i nclude<stdio.h>#i nclude

16、<stri ng.h>#i nclude <stdlib.h>#define max 100#defi ne MAX_LNT 30typedef struct node /*構造一個結構體，兩個城市可以看成起點和終點，之間的道 路可以看成一個邊*/int str; /* 起點 */int end; /* 終點 */int dis;/* 距離 */no de;node pmax,temp; /*p 記錄城市信息 */int pre100,rank100;/*用于判斷是否構成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市個數，arcs記錄城市間

17、權值*/int menu( )/* 菜單函數 */ int m;printf("2015年 7 月 2 日nn");printf("求最小生成樹n");prin tf("nn");printf("1輸入城市之間的信息n");prin tf("2判斷是否能構成一個最小生成樹n");printf("3遍歷所有城市生成最小生成樹n");prin tf("0 退出 n");prin tf("nn");printf("請輸入所選功能0-

18、3n");sca nf("%d",&m);if(m<0|m>3) return 4;return m;/*下面三個函數作用是檢驗當一條邊添加進去，是否會產生回路*/void set(int x)/* 初始化 */prex = x;ran kx = 0;int find(int x)/*找到這個點的祖先*/if(x != prex)prex = fin d(prex);return prex;void Union(int x,int y)/*將這兩個添加到一個集合里去 */x = fin d(x);y = fin d(y);if(ran kx &

19、gt;= ran ky)prey = x;ran kx +;else prey = x;/*克魯斯算法求最小生成樹*/void Kruskal()int ans = O,i,j,k = 0; /*ans用來記錄生成最小樹的權總值*/int in dex;int count = 0;/*記錄打印邊的條數*/for(i = 1;i <= n;i +)/*初始化數組 prex,rankx*/set(i);for(i = 1;i <= n;i +)for(j = i + 1;j <= n;j +)p+k.str = i;pk.e nd = j;pk.dis = arcsij; /*先

20、把所有城市之間的路段看成一個邊*/for(i=1;i<=k;i+)/*把所有的邊按從小到大進行排序*/in dex=i;for(j=i+1;j<=k;j+) if(pj.dis <pi ndex.dis) in dex=j;temp=pi ndex;pi ndex=pi;pi=temp;for(i = 1;i <= k;i +)if(find(pi.str) != find(pi.end)/*如果這兩點連接在一起不構成一個回路，則 執(zhí)行下面操作*/printf("t 第 %d 條路段為：d-%d,權值為 dn",+ count,pi.str,pi.e

21、nd,pi.dis);/*將這條邊的起點、終點打印出來*/ans += pi.dis; /*說明這條路段要用*/Union( pi.str,pi.e nd);printf("t遍歷所有城市得到最小生成樹的代價為：%dnn",ans);/*輸入城市信息*/void create()int i,j;printf("請輸入城市的個數(1 30):n");sca nf("%d",&n);if(*=0|n>30) printf("輸入錯誤，請重新輸入 n");return ; printf("輸入%d

22、個城市存儲邊(帶權)的數組(數值范圍：1-99, 用 100表 示，)：n",n);for(i = 1;i <= n;i +)for(j = 1;j <= n;j +)sea nf("%d",&arcsij);if(arcsij<1|arcsij>100)printf("輸入錯誤，請重新輸入n");return ;for(i=0;i <n ;i+)for(j=0;j<i;j+)if(arcsij!=arcsji)/* 判斷矩陣是否對稱 */printf("輸入錯誤，請重新輸入n");return ;/*顯示生成的最小生成樹*/void display()if(n = 0)printf（"這里沒有城市之間的信息n"）;return;printf("遍歷所有城市得到最小生成樹為：nnn");Kruskal();/*判斷是否能夠生成最小生成樹*/voi