最小生成樹Kruskal算法

1、課 程 設(shè) 計 報 告課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課程設(shè)計題目：最小生成樹Kruskal算法院（系）：專 業(yè)：班 級：學(xué) 號：姓 名：指導(dǎo)教師： 目 錄1 課程設(shè)計介紹11.1 課程設(shè)計內(nèi)容11.2 課程設(shè)計要求12 課程設(shè)計原理22.1 課設(shè)題目粗略分析22.2 原理圖介紹42.2.1 功能模塊圖42.2.2 流程圖分析53 數(shù)據(jù)結(jié)構(gòu)分析113.1 存儲結(jié)構(gòu)113.2 算法描述114 調(diào)試與分析134.1 調(diào)試過程134.2程序執(zhí)行過程13參考文獻16附 錄（關(guān)鍵部分程序清單）17 1 課程設(shè)計介紹1.1 課程設(shè)計內(nèi)容 編寫算法能夠建立帶權(quán)圖，并能夠用Kruskal算法求該圖的最小生成樹。

2、最小生成樹能夠選擇圖上的任意一點做根結(jié)點。最小生成樹輸出采用頂點集合和邊的集合的形式。1.2 課程設(shè)計要求1. 頂點信息用字符串，數(shù)據(jù)可自行設(shè)定。2. 參考相應(yīng)的資料，獨立完成課程設(shè)計任務(wù)。3. 交規(guī)范課程設(shè)計報告和軟件代碼。2 課程設(shè)計原理2.1 課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。以下是三個模塊的大體分析：1. 要確定圖的存儲形式，通過對題目要求的具體分析。發(fā)現(xiàn)該題的主要操作是路徑的輸出，因此采用邊集數(shù)組（每個元素是一個結(jié)構(gòu)體，包括起點、終點和權(quán)值）和鄰接矩陣比較方便以后的編程。2. Kruskal算法。該算法設(shè)置了集合A，該集合一直是某最小生成樹的子集。在每步?jīng)Q定

3、是否把邊（u,v）添加到集合A中，其添加條件是A（u,v）仍然是最小生成樹的子集。我們稱這樣的邊為A的安全邊，因為可以安全地把它添加到A中而不會破壞上述條件。3. Dijkstra算法。算法的基本思路是：假設(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的距

4、離，并設(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中的第“終點”元素向上回溯至起點，并顯示出來。 2.2 原理圖介紹 功能模塊圖開始輸入頂點個數(shù)n輸入邊數(shù)e輸

5、入邊集顯示菜單，進行選擇。求兩點間最短距離求兩點間最短距離Kruskal算法結(jié)束圖2.1 功能模塊圖 2.2.2 流程圖分析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é)束 圖2.2 主函數(shù)流程圖2. insertsort函數(shù)開始int i,jfor(i=2;i<=e;i+)gei.w<gei-1.wge0=gei; j=i-1;ge0.w<gej.wgej+1=gej; j-;Ygej

6、+1=ge0;NY結(jié)束N3. 圖2.3 insertsort函數(shù)流程圖3Kruskal函數(shù)開始int setMAXE,v1,v2,i,j;for(i=1;i<n+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 圖2.4 Kruskal函數(shù)流程圖4. dijkstra函數(shù)開始int u,vnum,w

7、,wm;for(w=1;w<=n;w+)distw=costv0w; if(costv0w<32767) pathw=v0;vnum=1;vnum<n-1wm=32767; u=v0;for(w=1;w<=n;w+)if(sw=0&&distw<wm)u=w;wm=distw;su=1;vnum+;for(w=1;w<=n;w+)if(sw=0&&distu+costuw<distw&&costuw!=32767)distw=distu+costuw;pathw=u;Y結(jié)束N 圖2.5 dijkstra函

8、數(shù)流程圖5. printpath1函數(shù)開始int i,k;for(i=1;i<=n;i+)si=1k=i; while(k!=v0)printf("%d<-",k);k=pathk;printf("%d:%dn",k,disti);printf("%d<-%d:32767n",i,v0);結(jié)束YN 圖2.6 printpath1函數(shù)流程圖 6. printpath2函數(shù)開始int k; k=v1;while(k!=v0)printf("%d<-",k);k=pathk; printf(&qu

9、ot;%d:%dn",k,distv1);結(jié)束 圖2.7 printpath2函數(shù)流程圖3 數(shù)據(jù)結(jié)構(gòu)分析3.1 存儲結(jié)構(gòu)定義一個結(jié)構(gòu)體數(shù)組，其空間足夠大，可將輸入的字符串存于數(shù)組中。struct edgesint bv; int tv; int w;3.2 算法描述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ù)

10、的關(guān)鍵在于dist數(shù)組的重新置數(shù)。該置數(shù)條件是：該頂點是被訪問過，并且新起點到該點的權(quán)值加上新起點到源點的權(quán)值小于該點原權(quán)值。因此第一次將其設(shè)為：if（sw=0&&costuw+distu<distw）。但是在實際運行中，發(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+distu<distw&&costuw!

11、=32767)。修改之后問題得到解決。3. printpath1函數(shù)：該函數(shù)主要用來輸出源點到其余各點的最短路徑。因為在主函數(shù)調(diào)用該函數(shù)前，已經(jīng)調(diào)用了dijkstra函數(shù)，所以所需的dist、path、s數(shù)組已經(jīng)由dijkstra函數(shù)生成，因此在該函數(shù)中，只需用一變量控制循環(huán)，一一將path數(shù)組中的每一元素回溯至起點即可。其關(guān)鍵在于不同情況下輸出形式的不同。4. printpath2函數(shù)：該函數(shù)主要用來輸出兩點間的最短路徑。其主要部分與printpath1函數(shù)相同，只是無需由循環(huán)將所有頂點一一輸出，只需將path數(shù)組中下標為v1的元素回溯至起點并顯示出來。4 調(diào)試與分析4.1 調(diào)試過程在調(diào)試程

12、序時主要遇到一下幾類問題：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+distu<distw）改為：if(sw=0&&costuw+distu<distw

13、&&costuw!=32767)。問題得到解決。1.2 程序執(zhí)行過程系統(tǒng)使用說明：1. 輸入的數(shù)據(jù)可以是整數(shù)，字符串（如1,2,3）；2. 本系統(tǒng)可以建立帶權(quán)圖，并能夠用Kruskal算法求改圖的最小生成樹。而且能夠選擇圖上的任意一點做根結(jié)點。還能夠求兩點之間的最短距離。 3. 該系統(tǒng)會有菜單提示，進行選項：1.kruskal2.shortpath3.shortpath between two point4.exit 4.程序?qū)嶋H運行截圖 圖4.1 輸入形式 圖4.2 kruskal算法輸出 圖4.3 最短距離輸出參考文獻1數(shù)據(jù)結(jié)構(gòu)（C語言版）.嚴蔚敏 ，吳偉民.清華大學(xué)出版社

14、.20072算法設(shè)計與分析.張德富.國防工業(yè)出版社.20093計算機算法與程序設(shè)計.朱青.清華大學(xué)出版社.20094C程序設(shè)計語言.徐寶文，李志.機械工業(yè)出版社.2004附 錄（關(guān)鍵部分程序清單）程序代碼#include"stdafx.h"#define MAXE 100struct edgesint bv; int tv; int w;typedef struct edges edgeset;int seeks(int set,int v) int i; i=v;while(seti>0) i=seti; return i;void kruskal(edgeset

15、ge,int n,int e)int setMAXE,v1,v2,i,j; for(i=1;i<n+1;i+)seti=0; i=1; j=1;while(j<=e&&i<=n-1)v1=seeks(set,gej.bv); v2=seeks(set,gej.tv); if(v1!=v2)printf("(%d,%d):%dn",gej.bv,gej.tv,gej.w); setv1=v2; i+;j+;void insertsort(edgeset ge,int e)int i,j; for(i=2;i<=e;i+) if(gei.

16、w<gei-1.w) ge0=gei; j=i-1;while(ge0.w<gej.w)gej+1=gej; j-; gej+1=ge0;void dijkstra(int costMAXEMAXE,int distMAXE,int pathMAXE,int sMAXE,int n,int v0)int u,vnum,w,wm; for(w=1;w<=n;w+)distw=costv0w; if(costv0w<32767) pathw=v0; vnum=1;while(vnum<n-1)wm=32767; u=v0; for(w=1;w<=n;w+) if

17、(sw=0&&distw<wm)u=w; wm=distw; su=1; vnum+; for(w=1;w<=n;w+) if(sw=0&&distu+costuw<distw&&costuw!=32767)distw=distu+costuw; pathw=u;void printpath1(int dist,int path,int s,int n,int v0)int i,k; for(i=1;i<=n;i+) if(si=1)k=i; while(k!=v0) printf("%d<-",

18、k); k=pathk; printf("%d:%dn",k,disti); else printf("%d<-%d:32767n",i,v0);void printpath2(int dist,int path,int v0,int v1)int k; k=v1;while(k!=v0)printf("%d<-",k); k=pathk; printf("%d:%dn",k,distv1);main()edgeset geMAXE; int costMAXEMAXE,distMAXE,pathMAXE

19、,sMAXE,a,n,e,i,j,k,v0,v1; 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&quo

20、t;); printf("1.kruskal算法（起點，終點）權(quán)值）：n"); printf("2.shortpath（終點<-起點）：n"); printf("3.shortpath between two point（終點<-起點）：n"); printf("4.exit（退出）：n"); scanf("%d",&a);while(a!=4)switch(a)case 1:insertsort(ge,e); kruskal(ge,n,e); break;case 2:pr

21、intf("請輸入起始頂點序號:"); scanf("%d",&v0); for(i=1;i<=n;i+) for(j=1;j<=n;j+) costij=32767; for(k=1;k<=e;k+) i=gek.bv; j=gek.tv; costij=gek.w; for(i=1;i<=n;i+) si=0; sv0=1; dijkstra(cost,dist,path,s,n,v0); printpath1(dist,path,s,n,v0); break;case 3:printf("請輸入起始頂點序號

22、:"); scanf("%d",&v0); printf("請輸入終點序號:"); scanf("%d",&v1); for(i=1;i<=n;i+) for(j=1;j<=n;j+) costij=32767; for(k=1;k<=e;k+) i=gek.bv; j=gek.tv; costij=gek.w; for(i=1;i<=n;i+) si=0; sv0=1; dijkstra(cost,dist,path,s,n,v0); printpath2(dist,path,v0,v1);