數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告最小生成樹Kruskal算法.doc

合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系課程設(shè)計(jì)報(bào)告 2014-2015學(xué)年第二學(xué)期課程數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)名稱Kruskal算法求最小生成樹學(xué)生姓名 姚國棟學(xué)號 1204091021專業(yè)班級 12軟件工程指導(dǎo)教師 何立新2014年9月題目：設(shè)計(jì)程序完成如下功能：對給定過的網(wǎng)和起點(diǎn)，用kruskal算法的基本思想求解其所有的最小生成樹1、問題分析和任務(wù)定義根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。以下是三個(gè)模塊的大體分析：要確定圖的存儲形式，通過對題目要求的具體分析。發(fā)現(xiàn)該題的主要操作是路徑的輸出，因此采用邊集數(shù)組（每個(gè)元素是一個(gè)結(jié)構(gòu)體，包括起點(diǎn)、終點(diǎn)和權(quán)值）和鄰接矩陣比較方便以后的編程。 Kruskal算法。該算法設(shè)置了集合A，該集合一直是某最小生成樹的子集。在每步?jīng)Q定是否把邊（u,v）添加到集合A中，其添加條件是A（u,v）仍然是最小生成樹的子集。我們稱這樣的邊為A的安全邊，因?yàn)榭梢园踩匕阉砑拥紸中而不會(huì)破壞上述條件。2 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)存儲結(jié)構(gòu)定義一個(gè)結(jié)構(gòu)體數(shù)組，其空間足夠大，可將輸入的字符串存于數(shù)組中。struct edgesint bv; int tv; int w;概要設(shè)計(jì)。算法思想：算法會(huì)先按照權(quán)重的非遞減順序?qū)D中的邊進(jìn)行排序。然后從一個(gè)空子圖開始，掃描這個(gè)有序表，試圖把列表中的下一條邊加到當(dāng)前的子圖中。當(dāng)然，這種添加不應(yīng)導(dǎo)致一個(gè)回路，如果產(chǎn)生回路，就把這條邊跳過。當(dāng)圖的所有頂點(diǎn)都包含在所構(gòu)造的樹中以后，算法停止。 算法的基本思路是：K r u s k a l算法每次選擇n- 1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會(huì)產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹。K r u s k a l算法分e 步，其中e 是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來考慮這e 條邊，每次考慮一條邊。當(dāng)考慮某條邊時(shí)，若將其加入到已選邊的集合中會(huì)出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。假設(shè)每個(gè)點(diǎn)都有一對標(biāo)號（dj,pj）,其中d是從起源點(diǎn)到點(diǎn)j的最短路徑的長度（從頂點(diǎn)到其本身的最短路徑是零路（沒有弧的路），其長度等于零）；pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。求解從起源點(diǎn)s到點(diǎn)j的最短路徑算法的基本過程如下：1） 初始化。起源點(diǎn)設(shè)置為：ds=0,ps為空；所有其它點(diǎn)：di=,pi=？；標(biāo)記起源點(diǎn)s，記k=s，其他所有點(diǎn)設(shè)為未標(biāo)記的。2） k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置： dj=mindj, dk+lkj式中，lkj是從點(diǎn)k到j(luò)的直接連接距離。3） 選取下一個(gè)點(diǎn)。從所有未標(biāo)記的結(jié)點(diǎn)中，選取dj中最小的一個(gè)i： di=mindj, 所有未標(biāo)記的點(diǎn)j 點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。4）找到點(diǎn)i的前一點(diǎn)。從已標(biāo)記的點(diǎn)中找到直接連接到i的點(diǎn)j*，作為前一點(diǎn)，設(shè)置： i=j*5)標(biāo)記點(diǎn)i。如果所有點(diǎn)已標(biāo)記，則算法完全推出，否則，記k=i，轉(zhuǎn)到2）再繼續(xù)。而程序中求兩點(diǎn)間最短路徑算法。其主要步驟是： 調(diào)用dijkstra算法。 將path中的第“終點(diǎn)”元素向上回溯至起點(diǎn)，并顯示出來。3詳細(xì)設(shè)計(jì)和編碼功能模塊圖開始輸入頂點(diǎn)個(gè)數(shù)n輸入邊數(shù)e輸入邊集顯示菜單，進(jìn)行選擇。求兩點(diǎn)間最短距離求兩點(diǎn)間最短距離Kruskal算法結(jié)束圖3.1 功能模塊圖 流程圖分析1. 主函數(shù)開始輸入頂點(diǎn)個(gè)數(shù)n輸入邊數(shù)e輸入選項(xiàng)aa=1調(diào)用insertsort，kruskal函數(shù)a=2輸入v0調(diào)用dijkstra，printpath1函數(shù)a=3輸入v0,v1調(diào)用dijkstra，printpath2函數(shù)輸入a=4結(jié)束 圖3.2主函數(shù)流程圖2. insertsort函數(shù)開始int i,jfor(i=2;i=e;i+)gei.wgei-1.wge0=gei; j=i-1;ge0.wgej.wgej+1=gej; j-;Ygej+1=ge0;NY結(jié)束N 圖3.3insertsort函數(shù)流程圖3Kruskal函數(shù)開始int setMAXE,v1,v2,i,j;for(i=1;in+1;i+)seti=0; i=1; j=1;j=e&i=n-1v1!=v2v1=seeks(set,gej.bv);v2=seeks(set,gej.tv);printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+;j+;YY結(jié)束NN 圖3.4 Kruskal函數(shù)流程圖 4 上機(jī)調(diào)試過程調(diào)試過程在調(diào)試程序時(shí)主要遇到一下幾類問題：1. 有時(shí)函數(shù)中一些數(shù)組中的數(shù)據(jù)無法存儲。2. 對其進(jìn)行檢驗(yàn)發(fā)現(xiàn)沒有申請空間大小。3. 在源程序的開頭用#define定義數(shù)值大小，在使用數(shù)組時(shí)亦可知道它的空間大小。4. 此函數(shù)中有時(shí)出現(xiàn)負(fù)值。5. 對其進(jìn)行檢驗(yàn)發(fā)現(xiàn)在程序中由32767代替。若costuw=32767，那么costuw+distu肯定溢出主負(fù)值，因此造成權(quán)值出現(xiàn)負(fù)值。6. 但是當(dāng)costuw=32767，那么distw肯定不需要重新置數(shù)。所以將if（sw=0&costuw+distudistw）改為：if(sw=0&costuw+distudistw&costuw!=32767)。問題得到解決。程序執(zhí)行過程系統(tǒng)使用說明：1. 輸入的數(shù)據(jù)可以是整數(shù)，字符串（如1,2,3）；2. 本系統(tǒng)可以建立帶權(quán)圖，并能夠用Kruskal算法求改圖的最小生成樹。而且能夠選擇圖上的任意一點(diǎn)做根結(jié)點(diǎn)。還能夠求兩點(diǎn)之間的最短距離。 3. 該系統(tǒng)會(huì)有菜單提示，進(jìn)行選項(xiàng)：1.kruskal4.exit5.測試結(jié)果及其分析結(jié)果截圖 圖5.1 輸入形式 圖5.2 kruskal算法輸出圖5.3kruskal算法輸出算法描述1. Kruskal函數(shù)： 因?yàn)镵ruskal需要一個(gè)有序的邊集數(shù)組，所以要先對邊集數(shù)組排序。其次，在執(zhí)行中需要判斷是否構(gòu)成回路，因此還需另有一個(gè)判斷函數(shù)seeks，在Kruskal中調(diào)用seeks。2. dijkstra函數(shù)： 因?yàn)閺囊辉吹狡溆喔鼽c(diǎn)的最短路徑共有n-1條，因此可以設(shè)一變量vnum作為計(jì)數(shù)器控制循環(huán)。該函數(shù)的關(guān)鍵在于dist數(shù)組的重新置數(shù)。該置數(shù)條件是：該頂點(diǎn)是被訪問過，并且新起點(diǎn)到該點(diǎn)的權(quán)值加上新起點(diǎn)到源點(diǎn)的權(quán)值小于該點(diǎn)原權(quán)值。因此第一次將其設(shè)為：if（sw=0&costuw+distudistw）。但是在實(shí)際運(yùn)行中，發(fā)現(xiàn)有些路徑的權(quán)值為負(fù)。經(jīng)過分析發(fā)現(xiàn)，因?yàn)樵诔绦蛑杏?2767代替。若costuw=32767，那么costuw+distu肯定溢出主負(fù)值，因此造成權(quán)值出現(xiàn)負(fù)值。但是如果costuw=32767，那么distw肯定不需要重新置數(shù)。所以將條件改為：if(sw=0&costuw+distudistw&costuw!=32767)。修改之后問題得到解決。6用戶使用說明1. 打開創(chuàng)天中文c+軟件。2. 將寫好的代碼導(dǎo)入軟件中并且運(yùn)行。3. 對照上述說明運(yùn)行并檢查程序。7參考文獻(xiàn)1王昆侖，李紅.數(shù)據(jù)結(jié)構(gòu)與算法北京：中國鐵道出版社，2006年5月2嚴(yán)蔚敏 ，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社.20073張德富. 算法設(shè)計(jì)與分析.國防工業(yè)出版社.20094朱青. 計(jì)算機(jī)算法與程序設(shè)計(jì).清華大學(xué)出版社.20095徐寶文，李志. C程序設(shè)計(jì)語言機(jī)械工業(yè)出版社.20048附 錄（關(guān)鍵部分程序清單）程序代碼#includestdio.h #define MAXE 100 struct edges int bv; /起點(diǎn)int tv; /終點(diǎn)int w;/權(quán)值 ; typedef struct edges edgeset; int seeks(int set,int v) /頂點(diǎn)集，頂點(diǎn)v int i; i=v; while(seti0) i=seti; return i; void kruskal(edgeset ge,int n,int e) /邊集，頂點(diǎn)數(shù)n，邊數(shù)e int setMAXE,v1,v2,i,j,x,y=1; /輸入頂點(diǎn)集edgeset xyMAXE;for(i=1;in+1;i+) seti=0; i=1; j=1; printf(第%d個(gè)最小生成樹:n,1);/判斷第幾個(gè)最小生成樹while(j=e&i=n-1) v1=seeks(set,gej.bv); /起點(diǎn)v2=seeks(set,gej.tv); /終點(diǎn)if(v1!=v2) xyj=gej;printf(%d,%d):%dn,gej.bv,gej.tv,gej.w); setv1=v2; i+; /計(jì)數(shù)器（判斷頂點(diǎn)數(shù)是否溢出） j+; y+;while(gej-1.w=gej.w) /輸出所有最小生成樹printf(第%d個(gè)最小生成樹為:n,y);for(x=1;x=j-2;x+)printf(%d,%d):%dn,xyx.bv,xyx.tv,xyx.w);printf(%d,%d):%dn,gej.bv,gej.tv,gej.w);j+;y+; void insertsort(edgeset ge,int e) /對權(quán)值進(jìn)行排序 int i,j; for(i=2;i=e;i+) if(gei.wgei-1.w) ge0=gei; j=i-1; while(ge0.wgej.w) gej+1=gej; j-; gej+1=ge0; main() edgeset geMAXE; int a,n,e,i; printf(請輸入頂點(diǎn)個(gè)數(shù):); scanf(%d,&n); printf(請輸入邊的條數(shù):); scanf(%d,&e); printf(請輸入邊的信息（起點(diǎn)，終點(diǎn)，權(quán)值）:n); for(i=1;i=e;i+) scanf(%d,%d,%d,&gei.bv,&gei.tv,&gei.w); printf(在下列菜單中進(jìn)行選擇：n); printf(1.kruskal算法（起點(diǎn)，終點(diǎn)）權(quán)