克魯斯卡爾最小生成樹(shù)

1、課 程 設(shè) 計(jì) 報(bào) 告構(gòu)造可以使n個(gè)城市連接的最小生成樹(shù)課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)院 （系）：信息科學(xué)與技術(shù)學(xué)院 專業(yè)班級(jí)： 學(xué) 號(hào)： 姓 名： 指導(dǎo)老師： 目 錄一需求分析31.1問(wèn)題描述：31.2功能要求：3二概要設(shè)計(jì)3三詳細(xì)設(shè)計(jì)33.1數(shù)據(jù)類型定義33.2程序的主要函數(shù)43.3克魯斯卡爾算法思想描述43.4克魯斯卡爾算法設(shè)計(jì)5四測(cè)試分析5五心得體會(huì)8附錄：程序源代碼8 一、 需求分析1.1問(wèn)題描述給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹(shù)，并計(jì)算得到的最小生成樹(shù)的代價(jià)。1.2功能要求城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課

2、本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。 要求在屏幕上顯示得到的最小生成樹(shù)中包括了哪些城市間的道路，并顯示得到的最小生成樹(shù)的代價(jià)。城市間的距離以鄰接矩陣的方式輸入（要求至少6個(gè)城市，10條邊）。二、概要設(shè)計(jì)2.1該程序的主要功能：能實(shí)現(xiàn)根據(jù)輸入城市的信息可以判斷該城市間的距離網(wǎng) 是否構(gòu)成最小生成樹(shù)，遍歷城市生成最小生成樹(shù)，通過(guò)計(jì)算得到最小生成樹(shù)的代價(jià)。2.2該城市間的距離網(wǎng)用鄰接矩陣表示。并且把2個(gè)城市的看成起點(diǎn)和終點(diǎn)，城市之間的距離看成邊，并以此設(shè)計(jì)結(jié)構(gòu)體。定義結(jié)構(gòu)體數(shù)組，將輸入的矩陣轉(zhuǎn)化為相對(duì)應(yīng)的結(jié)構(gòu)體來(lái)存儲(chǔ)城市與城市直接的關(guān)系2.3先用judge

3、()判斷能否生成是否為聯(lián)通圖，再用克魯斯卡爾（Kruskal）算法將輸入的矩陣生立最小生成樹(shù)，打印出來(lái)。創(chuàng)建用鄰接矩陣表示的城市道路網(wǎng)輸入城市數(shù)道路權(quán)值判斷是否可以連通Krushal算法，并將所到的結(jié)果輸出退出三、詳細(xì)設(shè)計(jì)3.1數(shù)據(jù)類型定義typedef struct node /*構(gòu)造一個(gè)結(jié)構(gòu)體*/int str; /*起點(diǎn)*/int end; /*終點(diǎn)*/int dis;/*距離*/node; 為了用鄰接矩陣表示圖 G ，先是定義二維數(shù)組的每一個(gè)元素含道路值然后在圖的定義中定義一個(gè)此二維數(shù)組的結(jié)構(gòu)成員。并且在圖中還定義一個(gè)用來(lái)存放城市的一維數(shù)組及int 型的城市數(shù)級(jí)道路數(shù)。用二維數(shù)組的兩個(gè)

4、下標(biāo)表示道路，這兩個(gè)下標(biāo)又在一位數(shù)組中對(duì)應(yīng)兩個(gè)城市，這樣就建立起了一個(gè)城市到城市之間的鄰接矩陣。將該鄰接矩陣轉(zhuǎn)化為圖示的結(jié)構(gòu)體，用于計(jì)算。 3.2程序的主要函數(shù)能實(shí)現(xiàn)根據(jù)輸入城市的信息可以判斷出該城市間的距離網(wǎng)是否構(gòu)成最小生成樹(shù)，遍歷城市生成最小生成樹(shù)，通過(guò)計(jì)算得到最小生成樹(shù)的代價(jià)主要函數(shù)：a) int menu ( ) 菜單函數(shù)，給用戶提示信息，讓用戶選擇相應(yīng)功能。 b) void create ( ) 輸入城市信息函數(shù)，將用戶輸入的鄰接矩陣以二維數(shù)組的形式存放到內(nèi)存中，為Krushal( )服務(wù)c) void judge ( ) 判斷用戶輸入的鄰接矩陣所轉(zhuǎn)化的圖是否可以生成最小生成樹(shù)d)

5、void find ( ) 判斷當(dāng)前是否構(gòu)成回路的函數(shù) e) void Union ( ) 將能構(gòu)成最小生成樹(shù)的邊添加到一個(gè)集合 ，f） void Krushal( ) 克魯斯算法求最小生成樹(shù)3.3克魯斯卡爾算法思想基本描述： 假設(shè)連通圖N=（V，E），則令最小生成樹(shù)的初始狀態(tài)為只有n 頂點(diǎn)而無(wú)邊的非連通圖T=(V, )，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。以此類推，直至T中所有頂點(diǎn)都在同一個(gè)連通分量上為止3.4克魯斯卡爾算法設(shè)計(jì)a. 設(shè)置計(jì)數(shù)器E，初值為0，記錄已選中的邊數(shù)。

6、將所有邊從小到大排序，存于p 中。b. 從p 中選擇一條權(quán)值最小的邊，檢查其加入到最小生成樹(shù)中是否會(huì)構(gòu)成回路，若是，則此邊不加入生成樹(shù)；否則，加入到生成樹(shù)中，計(jì)數(shù)器E累加1。c. 從E中刪除此最小邊，轉(zhuǎn)b繼續(xù)執(zhí)行，直到k=n-1, 算法結(jié)束 d. 判斷是否構(gòu)成回路的方法： 設(shè)置集合S，其中存放已加入到生成樹(shù)中的邊所連接的頂點(diǎn)集合，當(dāng)一條新的邊要加入到生成樹(shù)中時(shí)，檢查此邊所連接的兩個(gè)頂點(diǎn)是否都已經(jīng)在S中，若是，則表示構(gòu)成回路，否則，若有一個(gè)頂點(diǎn)不在S中 或者兩個(gè)頂點(diǎn)都不在S中，則不夠成回路。四、測(cè)試分析以一個(gè)6個(gè)城市、10條邊的網(wǎng)絡(luò)圖為例進(jìn)行測(cè)試1系統(tǒng)界面：2輸入信息 設(shè)置兩頂點(diǎn)之間無(wú)邊時(shí)權(quán)值為

7、100003數(shù)據(jù)處理(1)、判斷能否構(gòu)成最小生成樹(shù)（2）、遍歷所有城市生成最小生成數(shù) （3）、退出五、體會(huì)心得通過(guò)本周的課程設(shè)計(jì)，終于圓滿完成了課程設(shè)計(jì)的任務(wù)，我也有不少收獲。既鞏固和加深了對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)一門重要的專業(yè)技術(shù)基礎(chǔ)課程，還提高了我綜合運(yùn)用本課程所學(xué)知識(shí)的能力。而且，并不是單純的看看教材就能解決我們的實(shí)際問(wèn)題，所以還要去查找各種我們所需要的資料，所以這次課程設(shè)計(jì)也培養(yǎng)了我選用參考書，查閱手冊(cè)及文獻(xiàn)資料的能力。要完成一個(gè)課程設(shè)計(jì)的課題并不是一次就能編譯成功的，中間會(huì)出現(xiàn)很多的大問(wèn)題小問(wèn)題，改錯(cuò)是個(gè)很繁瑣的問(wèn)題。通過(guò)這次課程設(shè)計(jì)培養(yǎng)了我獨(dú)立思考，深入研究，分

8、析問(wèn)題，解決問(wèn)題的能力。參 考 文 獻(xiàn)1.嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）. 清華大學(xué)出版社，2007 2.譚浩強(qiáng)，張基溫. C語(yǔ)言程序設(shè)計(jì)教程（第三版）北京：高等教育出版社，2006 3.陳維新，林小茶. C+面向?qū)ο蟪绦蛟O(shè)計(jì)教程. 北京：清華大學(xué)出版社，2004 4.蘇仕華等.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì). 北京： 機(jī)械工業(yè)出版社，2005附錄：程序源碼#include <stdio.h>#include <string.h>#include <stdlib.h>#define max 20#define MAX_LNT 10typedef struct no

9、de /*構(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( ) /*菜單函數(shù)*/ int m;printf(" 求最小生成樹(shù)n");printf(" _nn");printf(" 1 輸入城市

10、之間的信息n");printf(" 2 判斷是否能構(gòu)成一個(gè)最小生成樹(shù)n");printf(" 3 遍歷所有城市生成最小生成樹(shù)n");printf(" 4 退出n");printf(" _nn");printf(" 請(qǐng)輸入所選功能1-4n");scanf("%d",&m);return m; /*下面三個(gè)函數(shù)作用是檢驗(yàn)當(dāng)一條邊添加進(jìn)去，是否會(huì)產(chǎn)生回路*/void set(int x)/*初始化*/ prex = x;rankx = 0; int find(in

11、t 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(rankx >= ranky) prey = x; rankx +; else prey = x; void Kruskal( ) int ans = 0,i,j,k = 0;/*ans用來(lái)記錄生成最小樹(shù)的權(quán)總值*/int index;int count = 0;/*記錄打印邊的條數(shù)*/for(i = 1;i <= n;i +

12、) /*初始化數(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 = 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(fi

13、nd(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遍歷所有城市得到最小生成樹(shù)的代價(jià)為: %dnn",ans);void create( )/*輸入城市信息*/int i,j;printf("請(qǐng)輸入城市的個(gè)數(shù):n&qu

14、ot;);scanf("%d",&n); printf("輸入%d個(gè)城市的鄰接矩陣:n",n);for(i = 1;i <= n;i +)for(j = 1;j <= n;j +)scanf("%d",&arcsij);void display( )/*顯示生成的最小生成樹(shù)*/if(n = 0)printf("這里沒(méi)有城市之間的信息n");return; printf("遍歷所有城市得到最小生成樹(shù)為：nnn"); Kruskal( );void judge( )/*判

15、斷是否能夠生成最小生成樹(shù)*/ 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;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(&quo