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