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

1、課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：最小生成樹 kruskal 算法院（系）：專 業(yè)：班 級(jí)：學(xué) 號(hào)：姓 名：指導(dǎo)教師： i 目目 錄錄1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹.11.1 課程設(shè)計(jì)內(nèi)容.11.2 課程設(shè)計(jì)要求.12 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理.22.1 課設(shè)題目粗略分析.22.2 原理圖介紹.42.2.1 功能模塊圖.42.2.2 流程圖分析.53 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析.113.1 存儲(chǔ)結(jié)構(gòu).113.2 算法描述.114 4 調(diào)試與分析調(diào)試與分析.134.1 調(diào)試過(guò)程.134.2 程序執(zhí)行過(guò)程.13參考文獻(xiàn)參考文獻(xiàn).16附

2、附 錄（錄（關(guān)關(guān)鍵部分程序清單）鍵部分程序清單）.17 1 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹1.11.1 課程設(shè)計(jì)內(nèi)容課程設(shè)計(jì)內(nèi)容 編寫算法能夠建立帶權(quán)圖，并能夠用 kruskal 算法求該圖的最小生成樹。最小生成樹能夠選擇圖上的任意一點(diǎn)做根結(jié)點(diǎn)。最小生成樹輸出采用頂點(diǎn)集合和邊的集合的形式。1.21.2 課程設(shè)計(jì)要求課程設(shè)計(jì)要求1. 頂點(diǎn)信息用字符串，數(shù)據(jù)可自行設(shè)定。2. 參考相應(yīng)的資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。3. 交規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。 2 2 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。以下是三個(gè)模塊的大體分

3、析：1. 要確定圖的存儲(chǔ)形式，通過(guò)對(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)榭梢园踩匕阉砑拥?a 中而不會(huì)破壞上述條件。3. dijkstra 算法。算法的基本思路是：假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào)（dj,pj）,其中 d 是從起源點(diǎn)到點(diǎn) j 的最短路徑的長(zhǎng)度（從頂點(diǎn)到其本身的最短路徑

4、是零路（沒有弧的路） ，其長(zhǎng)度等于零） ；pj則是從 s 到j(luò) 的最短路徑中 j 點(diǎn)的前一點(diǎn)。求解從起源點(diǎn) s 到點(diǎn) j 的最短路徑算法的基本過(guò)程如下：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 3 式中，lkj是從點(diǎn) k 到 j 的直接連接距離。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 的

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

6、 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é)束結(jié)束 圖 2.2 主函數(shù)流程圖2. insertsort 函數(shù) 6 開始開始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é)束結(jié)束n3. 圖 2.3 insertsort 函數(shù)流程圖 7 3kruskal 函數(shù)開始開始int setmaxe,v

7、1,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é)束結(jié)束nn 圖 2.4 kruskal 函數(shù)流程圖 8 4. dijkstra 函數(shù)開始開始int u,vnum,w,wm;for(w=1;w=n;w+)distw=costv0w; if(costv0w32767) pathw=v0;vnum=1;vnumn-1wm=32767;

8、u=v0;for(w=1;w=n;w+)if(sw=0&distwwm)u=w;wm=distw;su=1;vnum+;for(w=1;w=n;w+)if(sw=0&distu+costuwdistw&costuw!=32767)distw=distu+costuw;pathw=u;y結(jié)束結(jié)束n 圖 2.5 dijkstra 函數(shù)流程圖 9 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

9、,i,v0);結(jié)束結(jié)束yn 圖 2.6 printpath1 函數(shù)流程圖 10 6. printpath2 函數(shù)開始開始int k; k=v1;while(k!=v0)printf(%d-,k);k=pathk; printf(%d:%dn,k,distv1);結(jié)束結(jié)束 圖 2.7 printpath2 函數(shù)流程圖 11 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析3.13.1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)定義一個(gè)結(jié)構(gòu)體數(shù)組，其空間足夠大，可將輸入的字符串存于數(shù)組中。struct edgesint bv; int tv; int w;3.23.2 算法描述算法描述1. kruskal 函數(shù)： 因?yàn)?kruskal 需要一

10、個(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)是被訪問(wèn)過(guò)，并且新起點(diǎn)到該點(diǎn)的權(quán)值加上新起點(diǎn)到源點(diǎn)的權(quán)值小于該點(diǎn)原權(quán)值。因此第一次將其設(shè)為： 12 if（sw=0&costuw+distudistw） 。但是在實(shí)際運(yùn)行中，發(fā)現(xiàn)有些路徑的權(quán)值為負(fù)。經(jīng)過(guò)分析發(fā)現(xiàn)，因?yàn)樵诔绦蛑杏?32767 代替。若 c

11、ostuw=32767，那么 costuw+distu肯定溢出主負(fù)值，因此造成權(quán)值出現(xiàn)負(fù)值。但是如果 costuw=32767，那么 distw肯定不需要重新置數(shù)。所以將條件改為：if(sw=0&costuw+distudistw&costuw!=32767)。修改之后問(wèn)題得到解決。3. printpath1 函數(shù)：該函數(shù)主要用來(lái)輸出源點(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)，一一將 path 數(shù)組中的每一元素回溯至起點(diǎn)即可。其關(guān)鍵在于不同

12、情況下輸出形式的不同。4. printpath2 函數(shù)：該函數(shù)主要用來(lái)輸出兩點(diǎn)間的最短路徑。其主要部分與 printpath1 函數(shù)相同，只是無(wú)需由循環(huán)將所有頂點(diǎn)一一輸出，只需將 path 數(shù)組中下標(biāo)為 v1 的元素回溯至起點(diǎn)并顯示出來(lái)。 13 4 4 調(diào)試與分析調(diào)試與分析4.14.1 調(diào)試過(guò)程調(diào)試過(guò)程在調(diào)試程序時(shí)主要遇到一下幾類問(wèn)題：1. 有時(shí)函數(shù)中一些數(shù)組中的數(shù)據(jù)無(wú)法存儲(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 代替。若 costu

13、w=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+distu0) i=seti; return i;void kruskal(edgeset ge,int n,int e) 18 int setmaxe,v1,v2,i,j; for(i=1;in+1;i+)seti=0; i=1; j=1;while(j=e&i=n-1)v1=seeks(set,gej.bv); v2=seeks(set,

14、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) 19 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;void dijkstra(int costmaxemaxe,int distmaxe,int pathmaxe,int smaxe,int n,int v0)int u,vnu

15、m,w,wm; for(w=1;w=n;w+)distw=costv0w; 20 if(costv0w32767) pathw=v0; vnum=1;while(vnumn-1)wm=32767; u=v0; for(w=1;w=n;w+) if(sw=0&distwwm)u=w; wm=distw; su=1; vnum+; for(w=1;w=n;w+) if(sw=0&distu+costuwdistw&costuw!=32767)distw=distu+costuw; pathw=u; 21 void printpath1(int dist,int path,int s,int n,i

16、nt 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) 22 int k; k=v1;while(k!=v0)printf(%d-,k); k=pathk; printf(%d:%dn,k,distv1);main()edgeset gemaxe; int costmaxemaxe,d

17、istmaxe,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); printf(請(qǐng)輸入邊的信息（起點(diǎn)，終點(diǎn)，權(quán)值）:n); 23 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 b

18、etween two point（終點(diǎn)-起點(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+) 24 i=gek.bv; j=gek.tv; costij=gek.w; for(i=1;i=n;i+) si=0; sv0=1;

19、 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; 25 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(在下列菜單中進(jìn)行選擇：n);