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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課 程 設(shè) 計(jì) 報(bào) 告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：最小生成樹Kruskal算法院（系）：專 業(yè)：班 級(jí)：學(xué) 號(hào)：姓 名：指導(dǎo)教師： 專心-專注-專業(yè)目 錄 1 課程設(shè)計(jì)介紹1.1 課程設(shè)計(jì)內(nèi)容 編寫算法能夠建立帶權(quán)圖，并能夠用Kruskal算法求該圖的最小生成樹。最小生成樹能夠選擇圖上的任意一點(diǎn)做根結(jié)點(diǎn)。最小生成樹輸出采用頂點(diǎn)集合和邊的集合的形式。1.2 課程設(shè)計(jì)要求1. 頂點(diǎn)信息用字符串，數(shù)據(jù)可自行設(shè)定。2. 參考相應(yīng)的資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。3. 交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。2 課程設(shè)計(jì)原理2.1 課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，擬將整體程

2、序分為三大模塊。以下是三個(gè)模塊的大體分析：1. 要確定圖的存儲(chǔ)形式，通過對(duì)題目要求的具體分析。發(fā)現(xiàn)該題的主要操作是路徑的輸出，因此采用邊集數(shù)組（每個(gè)元素是一個(gè)結(jié)構(gòu)體，包括起點(diǎn)、終點(diǎn)和權(quán)值）和鄰接矩陣比較方便以后的編程。2. Kruskal算法。該算法設(shè)置了集合A，該集合一直是某最小生成樹的子集。在每步?jīng)Q定是否把邊（u,v）添加到集合A中，其添加條件是A（u,v）仍然是最小生成樹的子集。我們稱這樣的邊為A的安全邊，因?yàn)榭梢园踩匕阉砑拥紸中而不會(huì)破壞上述條件。3. Dijkstra算法。算法的基本思路是：假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào)（dj,pj）,其中d是從起源點(diǎn)到點(diǎn)j的最短路徑的長度（從頂點(diǎn)到其本

3、身的最短路徑是零路（沒有弧的路），其長度等于零）；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)

4、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)，并顯示出來。 2.2 原理圖介紹2.2.1 功能模塊圖開始輸入頂點(diǎn)個(gè)數(shù)n輸入邊數(shù)e輸入邊集顯示菜單，進(jìn)行選擇。求兩點(diǎn)間最短距離求兩點(diǎn)間最短距離Kruskal算法結(jié)束圖2.1 功能模塊圖 2.2.2 流程圖分析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ù)

5、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+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=s

6、eeks(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,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

7、<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函數(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);

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

9、ruskal函數(shù)： 因?yàn)镵ruskal需要一個(gè)有序的邊集數(shù)組，所以要先對(duì)邊集數(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+distu<distw）。但是在實(shí)際運(yùn)行中，發(fā)現(xiàn)有些路徑的權(quán)值為負(fù)。經(jīng)過分析發(fā)現(xiàn)，因

10、為在程序中由32767代替。若costuw=32767，那么costuw+distu肯定溢出主負(fù)值，因此造成權(quán)值出現(xiàn)負(fù)值。但是如果costuw=32767，那么distw肯定不需要重新置數(shù)。所以將條件改為：if(sw=0&&costuw+distu<distw&&costuw!=32767)。修改之后問題得到解決。3. printpath1函數(shù)：該函數(shù)主要用來輸出源點(diǎn)到其余各點(diǎn)的最短路徑。因?yàn)樵谥骱瘮?shù)調(diào)用該函數(shù)前，已經(jīng)調(diào)用了dijkstra函數(shù)，所以所需的dist、path、s數(shù)組已經(jīng)由dijkstra函數(shù)生成，因此在該函數(shù)中，只需用一變量控制循環(huán)，一一將

11、path數(shù)組中的每一元素回溯至起點(diǎn)即可。其關(guān)鍵在于不同情況下輸出形式的不同。4. printpath2函數(shù)：該函數(shù)主要用來輸出兩點(diǎn)間的最短路徑。其主要部分與printpath1函數(shù)相同，只是無需由循環(huán)將所有頂點(diǎn)一一輸出，只需將path數(shù)組中下標(biāo)為v1的元素回溯至起點(diǎn)并顯示出來。4 調(diào)試與分析4.1 調(diào)試過程在調(diào)試程序時(shí)主要遇到一下幾類問題：1. 有時(shí)函數(shù)中一些數(shù)組中的數(shù)據(jù)無法存儲(chǔ)。2. 對(duì)其進(jìn)行檢驗(yàn)發(fā)現(xiàn)沒有申請(qǐng)空間大小。3. 在源程序的開頭用#define定義數(shù)值大小，在使用數(shù)組時(shí)亦可知道它的空間大小。4. 此函數(shù)中有時(shí)出現(xiàn)負(fù)值。5. 對(duì)其進(jìn)行檢驗(yàn)發(fā)現(xiàn)在程序中由32767代替。若costuw=

12、32767，那么costuw+distu肯定溢出主負(fù)值，因此造成權(quán)值出現(xiàn)負(fù)值。6. 但是當(dāng)costuw=32767，那么distw肯定不需要重新置數(shù)。所以將if（sw=0&&costuw+distu<distw）改為：if(sw=0&&costuw+distu<distw&&costuw!=32767)。問題得到解決。1.2 程序執(zhí)行過程系統(tǒng)使用說明：1. 輸入的數(shù)據(jù)可以是整數(shù)，字符串（如1,2,3）；2. 本系統(tǒng)可以建立帶權(quán)圖，并能夠用Kruskal算法求改圖的最小生成樹。而且能夠選擇圖上的任意一點(diǎn)做根結(jié)點(diǎn)。還能夠求兩點(diǎn)之間的最短距

13、離。 3. 該系統(tǒng)會(huì)有菜單提示，進(jìn)行選項(xiàng)：1.kruskal2.shortpath3.shortpath between two point4.exit 4.程序?qū)嶋H運(yùn)行截圖 圖4.1 輸入形式 圖4.2 kruskal算法輸出 圖4.3 最短距離輸出參考文獻(xiàn)1數(shù)據(jù)結(jié)構(gòu)（C語言版）.嚴(yán)蔚敏 ，吳偉民.清華大學(xué)出版社.20072算法設(shè)計(jì)與分析.張德富.國防工業(yè)出版社.20093計(jì)算機(jī)算法與程序設(shè)計(jì).朱青.清華大學(xué)出版社.20094C程序設(shè)計(jì)語言.徐寶文，李志.機(jī)械工業(yè)出版社.2004附 錄（關(guān)鍵部分程序清單）程序代碼#include"stdio.h"#define MAXE

14、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 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,

15、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.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,i

16、nt 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(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=

17、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<-",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

18、)int k; k=v1;while(k!=v0)printf("%d<-",k); k=pathk; printf("%d:%dn",k,distv1);main()edgeset geMAXE; int costMAXEMAXE,distMAXE,pathMAXE,sMAXE,a,n,e,i,j,k,v0,v1; printf("請(qǐng)輸入頂點(diǎn)個(gè)數(shù):"); scanf("%d",&n); printf("請(qǐng)輸入邊的條數(shù):"); scanf("%d",&e

19、); printf("請(qǐng)輸入邊的信息（起點(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)值）：n"); printf("2.shortpath（終點(diǎn)<-起點(diǎn)）：n"); printf("3.shortpath between two point（終點(diǎn)&l

20、t;-起點(diǎn)）：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:printf("請(qǐng)輸入起始頂點(diǎn)序號(hào):"); 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

21、; 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("請(qǐng)輸入起始頂點(diǎn)序號(hào):"); scanf("%d",&v0); printf("請(qǐng)輸入終點(diǎn)序號(hào):"); 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); break;printf(