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

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