課程設(shè)計---克魯斯卡爾算法求最小生成樹

1、<p><b>　　課程設(shè)計報告</b></p><p>　　課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</p><p>　　設(shè)計題目： 克魯斯卡爾算法求最小生成樹 </p><p>　　系 別： 計算機系 </p><p>　　專 業(yè)：

2、 </p><p>　　組 別： </p><p>　　學(xué)生姓名： 學(xué) 號: </p><p>　　起止日期: 2011年6月29日 ~2011年7月6日 </p><p&

3、gt;　　指導(dǎo)教師: </p><p><b>　　目 錄</b></p><p>　　1. 需求分析……………………………………………………………………………2</p><p>　　1.1 設(shè)計題目……………………………………………………………………2</p><

4、p>　　1.2 設(shè)計任務(wù)及要求……………………………………………………………2</p><p>　　1.3課程設(shè)計思想………………………………………………………………2</p><p>　　1.4 程序運行流程:……………………………………………………………2</p><p>　　1.5軟硬件運行環(huán)境及開發(fā)工具………………………………………………2</p

5、><p>　　2.概要設(shè)計……………………………………………………………………………2</p><p>　　2.1流程圖………………………………………………………………………2</p><p>　　2.2抽象數(shù)據(jù)類型MFSet的定義………………………………………………3</p><p>　　2.3主程序…………………………………………………………

6、……………3</p><p>　　2.4抽象數(shù)據(jù)類型 圖 的定義…………………………………………………4 </p><p>　　2.5抽象數(shù)據(jù)類型 樹 的定義…………………………………………………6</p><p>　　3. 詳細設(shè)計……………………………………………………………………………8</p><p>　　3.1程序…………………

7、………………………………………………………8</p><p>　　4.調(diào)試與操作說明……………………………………………………………………11</p><p>　　4.1測試結(jié)果……………………………………………………………………11</p><p>　　4.2調(diào)試分析……………………………………………………………………12</p><p>　

8、　5.課程設(shè)計總結(jié)與體會………………………………………………………………12</p><p>　　5.1總結(jié)…………………………………………………………………………12</p><p>　　5.2體會…………………………………………………………………………12</p><p>　　6. 致謝…………………………………………………………………………………13</

9、p><p>　　7. 參考文獻……………………………………………………………………………13</p><p>　　8.附錄…………………………………………………………………………………14</p><p><b>　　1.需求分析</b></p><p>　　1.1 設(shè)計題目：最小生成樹</p><p&g

10、t;　　1.2 設(shè)計任務(wù)及要求：任意創(chuàng)建一個圖，利用克魯斯卡爾算法，求出該圖的最小生成樹。</p><p>　　1.3 課程設(shè)計思想：Kruskal算法采用了最短邊策略(設(shè)G=(V,E)是一個無向連通網(wǎng)，令T=(U，TE)是G的最小生成樹。最短邊策略從TE={}開始，每一次貪心選擇都是在邊集E中選擇最短邊(u,v)，如果邊(u,v)加入集合TE中不產(chǎn)生回路，則將邊(u,v)加入邊集TE中，并將它在集合E中刪去。)

11、，它使生成樹以一種任意的方式生長，先讓森林中的樹木隨意生長，每生長一次就將兩棵樹合并，最后合并成一棵樹。</p><p>　　1.4程序運行流程:</p><p>　　1)提示輸入頂點數(shù)目；</p><p>　　2)接受輸入，按照項目要求產(chǎn)生邊權(quán)值的隨機矩陣；然后求解最小生成樹；</p><p>　　3)輸出最小生成樹并且退出；</p&

12、gt;<p>　　1.5 軟硬件運行環(huán)境及開發(fā)工具：VC</p><p><b>　　2.概要設(shè)計</b></p><p><b>　　2.1流程圖</b></p><p><b>　　圖1流程圖</b></p><p>　　2.2抽象數(shù)據(jù)類型MFSet的定義：&

13、lt;/p><p>　　ADT MFSet {</p><p>　　數(shù)據(jù)對象 ：若設(shè)S是MFSet型的集合，則它由n(n>0)個子集Si（i = 1,2...,n）構(gòu)成，每個子集的成員代表在這個子集中的城市。</p><p>　　數(shù)據(jù)關(guān)系 ： S1 U S2 U S3 U... U Sn = S, Si包含于S（i = 1,2,...n） </p>

14、<p>　　Init (n): 初始化集合，構(gòu)造n個集合，每個集合都是單成員，根是其本身。rank數(shù)組初始化0</p><p>　　Find(x):查找x所在集合的代表元素。即查找根，確定x所在的集合，并路徑壓縮。</p><p>　　Merge(x, y):檢查x與y是否在同一個集合，如果在同一個集合則返回假，否則按秩合并這兩個集合并返回真。</p><p&

15、gt;<b>　　}</b></p><p><b>　　2.3主程序：</b></p><p>　　int main()</p><p><b>　　{</b></p><p><b>　　初始化；</b></p><p>　　w

16、hile (條件)</p><p><b>　　{</b></p><p><b>　　接受命令;</b></p><p><b>　　處理命令;</b></p><p><b>　　}</b></p><p><b>　

17、　return 0;</b></p><p><b>　　}</b></p><p>　　2.4抽象數(shù)據(jù)類型 圖 的定義如下：</p><p>　　ADT Graph{</p><p>　　數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點集。</p><p><b>　

18、　數(shù)據(jù)關(guān)系R：</b></p><p><b>　　R={VR}</b></p><p>　　VR={<v,w>|v，w∈V且P（v，w），<v，w>表示從v到w的弧，謂詞P（v，w）定義了弧<v，w>的意義或信息 }</p><p><b>　　基本操作P：</b><

19、;/p><p>　　CreateGraph（&G，V，VR）；</p><p>　　初始條件：V是圖的頂點集，VR是圖中弧的集合。</p><p>　　操作結(jié)果：按V和的VR定義構(gòu)造圖G。</p><p>　　DestoryGraph（&G）；</p><p>　　初始條件：圖G存在。</p>

20、<p>　　操作結(jié)果：銷毀圖G。</p><p>　　LocateVex（G，u）；</p><p>　　初始條件：圖G存在，u和G中是頂點有相同特征。 </p><p>　　操作結(jié)果：若G中存在頂點u，則返回該頂點在圖中位置；否則返回其他信息。</p><p>　　GetVex（G，v）；</p><p>

21、;　　初始條件：圖G存在，v是G中某個頂點。 </p><p>　　操作結(jié)果：返回v的值。</p><p>　　PutVex（&G，v，value）；</p><p>　　初始條件：圖G存在，v是G中某個頂點。 </p><p>　　操作結(jié)果：對V賦值value，</p><p>　　FirstAdjVex（G

22、，v）；</p><p>　　初始條件：圖G存在，v是G中某個頂點。</p><p>　　操作結(jié)果：返回v的第一個鄰接頂點。若頂點在G中沒有頂點，</p><p><b>　　則返回“空”。</b></p><p>　　NextAdjVex（G，v，w）；</p><p>　　初始條件：圖G存在，

23、v是G中某個頂點，w是v的鄰接頂點。</p><p>　　操作結(jié)果：返回v的（相對于w的）下一個鄰接頂點。若w是v的最后一個鄰接頂點，則返回“空”。</p><p>　　InsertVex（&G，v）；</p><p>　　初始條件：圖G存在，v和途中頂點有相同特征。</p><p>　　操作結(jié)果：在圖G中添加新頂點v。</p&

24、gt;<p>　　DeleteVex（&G，v）；</p><p>　　初始條件：圖G存在，v是G中某個頂點。</p><p>　　操作結(jié)果：刪除G中頂點v及其相關(guān)的弧。</p><p>　　InsertArc（&G，v，w）；</p><p>　　初始條件：圖G存在，v和w是G中兩個頂點。</p>

25、<p>　　操作結(jié)果：在G中添加弧<v，w>，若G是無向的，則還增添 對稱弧<v，w>。</p><p>　　DeleteArc（&G，v，w）；</p><p>　　初始條件：圖G存在，v和w是G中兩個頂點。</p><p>　　操作結(jié)果：在G中刪除弧<v，w>，若G是無向的，則還刪除

26、對稱弧<v，w>。</p><p>　　DFSTravrese（G，Visit（））；</p><p>　　初始條件：圖G存在，Visit是頂點的應(yīng)用函數(shù)。</p><p>　　操作結(jié)果：對圖進行深度優(yōu)先遍歷。在遍歷過程中對每個頂點調(diào)用函數(shù) Visit一次且僅一次。一旦Visit（）失敗，則操作失敗。</p><p>　　BFS

27、Travrese（G，Visit（））；</p><p>　　初始條件：圖G存在，Visit是頂點的應(yīng)用函數(shù)。</p><p>　　操作結(jié)果：對圖進行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點調(diào)用函數(shù)Visit一次且僅一次。一旦Visit（）失敗，則操作失敗。</p><p>　　}ADT Graph</p><p>　　2.5抽象數(shù)據(jù)類型 樹 的

28、定義如下：</p><p><b>　　ADT Tree{</b></p><p>　　數(shù)據(jù)對象D:D是具有相同特性數(shù)據(jù)元素的集合。</p><p>　　數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹； 若D僅含一個元素數(shù) 據(jù)， 則R為空集，否則R={H}，H是如下二元關(guān)系：</p><p>　　（1）在D中存在唯一的稱為根的數(shù)據(jù)元

29、素root，它在關(guān)系H 下無前驅(qū)；</p><p>　?。?）若D-{root}≠，則存在D-{root}的一個劃分D1，D2，…，Dm（m>0），對任意j≠k（1≤j,k≤m）有Dj∩Dk=，且對任意的I（1≤i≤m），惟一存在數(shù)據(jù)元素xi∈Di有<root，xi>∈H；</p><p>　　（3）對應(yīng)于D-{root}的劃分，H-{<roo

30、t，x1>，…，<roor，xm>}有惟一的一個劃分H1，H2，…，Hm（m＞0），對任意j≠k(1≤j，k≤m)有Hj∩Hk=，且對任意I（1≤i≤m），Hi是Di上的二元關(guān)系，（Di，{Hi}）是一棵符合本定義的樹，稱為跟root的子樹。</p><p><b>　　基本操作P：</b></p><p>　　InitTree（&T）；&l

31、t;/p><p>　　操作結(jié)果：構(gòu)造空樹T。</p><p>　　DestoryTree（&T）；</p><p>　　初始條件：樹T存在。</p><p>　　操作結(jié)果：銷毀樹T。</p><p>　　CreateTree（&T，definition）；</p><p>　　初始條

32、件：definition給出樹T的定義。</p><p>　　操作結(jié)果：按definition構(gòu)造樹T。</p><p>　　ClearTree（&T）；</p><p>　　初始條件：樹T存在。</p><p>　　操作結(jié)果：將樹T清為空樹。</p><p>　　TreeEmptey（T）；</p>

33、;<p>　　初始條件：樹T存在。</p><p>　　操作結(jié)果：若T為空樹，則返回TRUE，否則FALSE。</p><p>　　TreeDepth（T）；</p><p>　　初始條件：樹T存在。</p><p>　　操作結(jié)果：返回T的深度。</p><p><b>　　Root（T）；&l

34、t;/b></p><p>　　初始條件：樹T存在。</p><p>　　操作結(jié)果：返回T的跟。</p><p>　　Value（T，cur_e）；</p><p>　　初始條件：樹T存在，cur_e是T中某個結(jié)點。</p><p>　　操作結(jié)果：返回cur_e的值。</p><p>　　

35、Assign（T，cur_e，value）；</p><p>　　初始條件：樹T存在，cur_e是T中某個結(jié)點。</p><p>　　操作結(jié)果：結(jié)點cur_e賦值為value。</p><p>　　Parent（T，cur_e）；</p><p>　　初始條件：樹T存在，cur_e是T中某個結(jié)點。</p><p>　　

36、操作結(jié)果：若cur_e是T的非根結(jié)點，則返回它的雙親，否則函數(shù)值為“空”。</p><p>　　LeftChild（T，cur_e）；</p><p>　　初始條件：樹T存在，cur_e是T中某個結(jié)點。</p><p>　　操作結(jié)果：若cur_e是T的非葉子結(jié)點，則返回它的最左</p><p>　　子，否則返回“空”。</p>

37、<p>　　RightSibling（T，cur_e）；</p><p>　　初始條件：樹T存在，，cur_e是T中某個結(jié)點。</p><p>　　操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。</p><p>　　InsertChild（&T，&p，I，c）；</p><p>　　初始條件：

38、樹T存在，P指向T中某個結(jié)點，1≤i≤p所指向的結(jié)點度數(shù)+1，非空樹c與T不相交。</p><p>　　操作結(jié)果：插入c為T中p指結(jié)點的第i棵子樹。</p><p>　　DeleteChild（&T，&p，i）；</p><p>　　初始條件：樹T存在，p指向T中某個結(jié)點，1≤i≤p指結(jié)點的度。</p><p>　　操作結(jié)果：

39、刪除T中p所指結(jié)點的第i棵子樹。</p><p>　　TraverseTree（T，Visit（））；</p><p>　　初始條件：樹T存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)。</p><p>　　操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)visit（）一次且至多一次。一旦vista（）失敗，則操作失敗。</p><p><b>

40、　　}ADT Tree</b></p><p><b>　　3.詳細設(shè)計</b></p><p><b>　　3.1程序：如下</b></p><p>　　#include<stdio.h>#include<stdlib.h>#include<string.h>#def

41、ine MAX_NAME 5#define MAX_VERTEX_NUM 20 typedef char Vertex[MAX_NAME];/*頂點名字串*/typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*鄰接距陣*/typedef struct /*定義圖*/{ Vertex vexs[MAX_VERTEX_NUM]; AdjMatrix

42、 arcs;  int vexnum,arcnum; } MGraph;typedef struct{   Vertex adjvex; /*當(dāng)前點*/  int lowcost;    /*代價*/}minside[MAX_VERTEX_NUM];int LocateVex(MGraph *G,Vertex u){  int i; 

43、for(i=0;i<G->vexnum;++i)    if(strcmp(G->vexs[i],</p><p>　　4. 調(diào)試與操作說明</p><p>　　4.1測試結(jié)果：如下圖</p><p><b>　　圖2測試結(jié)果1</b></p><p><b>

44、　　圖3測試結(jié)果2</b></p><p><b>　　4.2調(diào)試分析</b></p><p>　　本程序利用克魯斯卡爾算法求最小生成樹數(shù)據(jù)結(jié)構(gòu)清晰因而條是比較順利。在調(diào)試過程中主要是參數(shù)的傳遞比較不容易掌握。本程序的關(guān)鍵部分是如何確定一條邊的兩個端點是否屬于同一連通分支，合并兩個連通分支。</p><p>　　5. 課程設(shè)計總結(jié)與

45、體會</p><p><b>　　5.1總結(jié)：</b></p><p>　　克魯斯卡爾算法中的核心思想就是逐個在邊的集合中找到最小的邊，如果滿足條件就將其構(gòu)造，最后生成一個最小生成樹。它首先是一系列的頂點集合，并沒有邊，然后我們從鄰接矩陣中尋找最小的邊，看看它是否和現(xiàn)有的邊連接成一個環(huán)，如果連接成環(huán)，則舍棄，另外取其它的邊。如果不連接成環(huán)，則接受這個邊，并把其納入集合

46、中。</p><p><b>　　5.2體會：</b></p><p>　?。?）通過求最小生成樹，進一步掌握了圖的含義，掌握了克魯斯卡爾算法的基 本思想及流程。知道了克魯斯卡爾算法與普里姆算法的區(qū)別與聯(lián)系。通過本次課程設(shè)計，鍛煉了我們的實際操作能力，培養(yǎng)了我們嚴(yán)密的思維和嚴(yán)謹?shù)膽B(tài)度。

47、 （2） 在編程序過程中雖然遇到了很多問題，但也使我學(xué)到了很多東西，在編制程序過程中我學(xué)到了在編程的開始需要總體設(shè)計一下自己的程序需要哪些大的模塊，并想好所要用到的知識計算法，在編程過程中，特別是要畫圖時需要找出坐標(biāo)，并研究各坐標(biāo)各結(jié)點之間連線的規(guī)律，通過幾句判斷語句來實現(xiàn)多條連線問題，在編程過好還要反復(fù)調(diào)試程序，找出其中的漏洞并加以改正，在此次編程過程中就存在這樣的問題，在經(jīng)過反復(fù)修改后，終于可將漏洞掃除，正確的

48、輸出結(jié)果。</p><p><b>　　6.致謝</b></p><p>　　在編著過程中，感謝那些幫助我的同學(xué)，有了他們，我的課程設(shè)計才能順利進行下去。</p><p>　　感謝同學(xué)在我的設(shè)計過程中提出的寶貴意見，如果沒有他們的幫助，我在設(shè)計過程中出現(xiàn)的一些錯誤可能無法迅速查出解決，他們的幫助為我節(jié)省了寶貴的時間。</p>&l

49、t;p><b>　　衷心感謝！</b></p><p><b>　　7. 參考文獻</b></p><p>　　[1].嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）. 清華大學(xué)出版社，2007</p><p>　　[2].譚浩強，張基溫. C語言程序設(shè)計教程（第三版）北京：高等教育出版社，2006</p>&