克魯斯卡爾算法求最小生成樹

1、1. 需求分析21.1設(shè)計題目21.2設(shè)計任務(wù)及要求21.3課程設(shè)計思想2 1.4 程序運行流程21.5軟硬件運行環(huán)境及開發(fā)工具22. 概要設(shè)計22.1流程圖22.2抽象數(shù)據(jù)類型MFSet的定義3-2.3主程序42.4抽象數(shù)據(jù)類型圖的定義4-2.5抽象數(shù)據(jù)類型樹的定義5-3. 詳細(xì)設(shè)計73.1程序74. 調(diào)試與操作說明104.1測試結(jié)果10 4.2調(diào)試分析115. 課程設(shè)計總結(jié)與體會115.1總結(jié)11 5.2體會116. 致謝127. 參考文獻(xiàn)12 1. 需求分析1.1設(shè)計題目：最小生成樹1.2設(shè)計任務(wù)及要求：任意創(chuàng)建一個圖，利用克魯斯卡爾算法，求出該圖的 最小生成樹。1.3課程設(shè)計思想：Kr

2、uskal算法采用了最短邊策略(設(shè)G=(V,E)是一個無向 連通網(wǎng)，令T=(U，TE)是G的最小生成樹。最短邊策略從 TE=開始，每一次 貪心選擇都是在邊集E中選擇最短邊(u,v)，如果邊(u,v)加入集合TE中不產(chǎn)生回 路，則將邊(u,v)加入邊集TE中，并將它在集合E中刪去。)，它使生成樹以一種 任意的方式生長，先讓森林中的樹木隨意生長，每生長一次就將兩棵樹合并，最 后合并成一棵樹。1.4程序運行流程：1) 提示輸入頂點數(shù)目；2) 接受輸入，按照項目要求產(chǎn)生邊權(quán)值的隨機矩陣；然后求解最小生成樹；3) 輸出最小生成樹并且退出；1.5軟硬件運行環(huán)境及開發(fā)工具：VC2. 概要設(shè)計2.1流程圖圖1

3、流程圖2.2抽象數(shù)據(jù)類型MFSet的定義：ADT MFSet 數(shù)據(jù)對象：若設(shè)S是MFSet型的集合，則它由n(n>0)個子集Si (i = 1,2,n ) 構(gòu)成，每個子集的成員代表在這個子集中的城市。數(shù)據(jù)關(guān)系：S1 U S2 U S3 U. U Sn = S, Si 包含于 S(i = 1,2,.n )Init (n):初始化集合，構(gòu)造n個集合，每個集合都是單成員，根是其本身。rank 數(shù)組初始化0Find(x):查找x所在集合的代表元素。即查找根，確定x所在的集合，并路徑壓縮。Merge(x, y):檢查x與y是否在同一個集合，如果在同一個集合則返回假，否則 按秩合并這兩個集合并返回真

4、。2.3主程序：int main()初始化；while (條件)接受命令；處理命令;return 0;2.4抽象數(shù)據(jù)類型圖的定義如下：ADT Graph數(shù)據(jù)對象V: V是具有相同特性的數(shù)據(jù)元素的集合，成為頂點集。數(shù)據(jù)關(guān)系 R: R=VR VR=<v,w>|v , w V 且 P(v, w), <v , w> 表示從 v到w的弧，謂詞P (v , w )定義了弧<v , w>的意義或信息 基本操作P:CreateGraph (&G , V, VR)；初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結(jié)果：按V和的VR定義構(gòu)造圖GoDestoryGrap

5、h (&G );初始條件：圖G存在。操作結(jié)果：銷毀圖GoLocateVex (G, u);初始條件：圖G存在，u和G中是頂點有相同特征。操作結(jié)果：若G中存在頂點u，貝U返回該頂點在圖中位置；否則返回其他信 息。GetVex (G，v)；初始條件：圖G存在，v是G中某個頂點。操作結(jié)果：返回v的值。PutVex (&G，v，value )；初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果：對V賦值value ,FirstAdjVex （ G，v）；初始條件：圖G存在，v是G中某個頂點。操作結(jié)果：返回v的第一個鄰接頂點。若頂點在 G中沒有頂點，則返回“空”。NextAdjVex （G

6、，v，w）；初始條件：圖G存在，v是G中某個頂點，w是v的鄰接頂點。操作結(jié)果：返回v的（相對于w的）下一個鄰接頂點。若 w是v的最后一 個鄰接頂點，則返回“空”。InsertVex （&G，v）；初始條件：圖G存在，v和途中頂點有相同特征。 操作結(jié)果：在圖G中添加新頂點v。DeleteVex （ &G，v）；初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果：刪除G中頂點v及其相關(guān)的弧。InsertArc （&G，v，w）；初始條件：圖G存在，v和w是G中兩個頂點。操作結(jié)果：在G中添加弧v，w，若G是無向的，則還增添對稱弧v，w。DeleteArc （ &G，v，

7、w）；初始條件：圖G存在，v和w是G中兩個頂點。操作結(jié)果：在G中刪除弧v，w，若G是無向的，則還刪除對稱弧v ,w。DFSTravrese （G，Visit （）；初始條件：圖G存在，Visit是頂點的應(yīng)用函數(shù)。操作結(jié)果：對圖進(jìn)行深度優(yōu)先遍歷。在遍歷過程中對每個頂點調(diào)用函數(shù)Visit 一次且僅一次。一旦 Visit （）失敗，則操作失敗。BFSTravrese （G，Visit （）;初始條件：圖G存在，Visit是頂點的應(yīng)用函數(shù)。操作結(jié)果：對圖進(jìn)行廣度優(yōu)先遍歷。在遍歷過程中對每個頂點調(diào)用函數(shù) Visit 一次且僅一次。一旦 Visit （）失敗，則操作失敗。ADT Graph2.5抽象數(shù)據(jù)類

8、型樹的定義如下：ADT Tree數(shù)據(jù)對象D:D是具有相同特性數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R:若D為空集，則稱為空樹；若D僅含一個元素數(shù)據(jù)，則R為空集， 否則R=H ， H是如下二兀關(guān)系：(1 )在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；(2) 若 D-root工，則存在 D-root的一個劃分 Di,D2,，Dm(m>0 )， 對任意j枠(1 <j,k <m )有Dj ADk=，且對任意的I (1 <i <m ),惟一存在數(shù)據(jù) 元素 Xi Di 有vroot , xi> H ;(3) 對應(yīng)于 D-root的劃分，H-<root , xi

9、>，<roor , xm>有惟一 的一個劃分 H1, H2，Hm (m >0),對任意 j球(1 <j, k<m)有 HjAHk= 且對任意I (1 <i<m ), Hi是Di上的二元關(guān)系，(Di, Hi)是一棵符合本定義的 樹，稱為跟root的子樹?；静僮鱌:InitTree (&T )；操作結(jié)果：構(gòu)造空樹T。DestoryTree (&T )；初始條件：樹T存在。操作結(jié)果：銷毀樹ToCreateTree (&T , definition )；初始條件：definition 給出樹T的定義。操作結(jié)果：按definiti

10、on 構(gòu)造樹T。ClearTree (&T )；初始條件：樹T存在。操作結(jié)果：將樹T清為空樹。TreeEmptey (T)；初始條件：樹T存在。操作結(jié)果：若T為空樹，則返回TRUE，否則FALSE。TreeDepth (T)；初始條件：樹T存在。 操作結(jié)果：返回T的深度。Root (T)；初始條件：樹T存在。 操作結(jié)果：返回T的跟。Value (T, cur_e)；初始條件：樹T存在，cur_e是T中某個結(jié)點。 操作結(jié)果：返回cur_e的值。Assign （T， cur_e，value）；初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：結(jié)點cur_e賦值為value。Pare

11、nt （ T， cur_e）；初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e是T的非根結(jié)點，則返回它的雙親，否則函數(shù)值為“空”。LeftChild （T，cur_e）；初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e是T的非葉子結(jié)點，則返回它的最左子，否則返回“空”。RightSibling（ T，cur_e）；初始條件：樹T存在，cur_e是T中某個結(jié)點。操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則函數(shù)值為“空”。 InsertChild （&T， &p， I， c）;初始條件：樹T存在，P指向T中某個結(jié)點，1 <i&

12、lt;p所指向的結(jié)點度數(shù)+1， 非空樹c與T不相交。操作結(jié)果：插入c為T中p指結(jié)點的第i棵子樹。DeleteChild （&T，&p，i）；初始條件：樹T存在，p指向T中某個結(jié)點，1 <i<p指結(jié)點的度。 操作結(jié)果：刪除T中p所指結(jié)點的第i棵子樹。TraverseTree （T，Visit （）;初始條件：樹T存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)。操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)visit （） 一次且至多一次。 一旦vista （）失敗，則操作失敗。ADT Tree3. 詳細(xì)設(shè)計3.1程序：如下#i nclude<stdio.h>#i nc

13、lude<stdlib.h>#i nclude<stri ng.h>#defi ne MAX_NAME 5#defi ne MAX_VERTEX_NUM 30typedef char VertexMAX_NAME;/* 頂點名字?jǐn)?shù)組 */鄰接矩typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/* 陣*/typedef struct /* 定義圖 */Vertex vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vex nu m,arc num;MGraph;int LocateVex(MGr

14、aph *G,Vertex u)int i;for(i=0;i<G->vex nu m;+i)if(strcmp(G->vexsi,u)=O)return i;return -1;void CreateGraph(MGraph *G)int i,j,k,w;Vertex va,vb;printf("請輸入無向網(wǎng)G的頂點數(shù)和邊數(shù)(以空格作為間隔):n");scanf("%d %d",&G->vex num,&G->arcnum);printf("請輸入%d個頂點的名字(小于%d個字符):n"

15、,G->vex nu m,MAX_NAME);for(i=0;i<G->vexnum;+i) /*構(gòu)造頂點集 */sca nf("%s",G->vexsi);for(i=0;i<G->vexnum;+i) /*初始化鄰接矩陣 */for(j=0;j<G->vex nu m;+j)G->arcsij=0x7fffffff;printf("請輸入%d條邊的頂點1頂點2權(quán)值(以空格作為間隔):n",G->arc nu m);for(k=0;k<G->arc nu m;+k)sea nf(&

16、quot;%s%s%d%*c",va,vb，&w);i=LocateVex(G,va);j=LocateVex(G,vb);G->arcsij=G->arcsji=w; /* 對稱 */void kruskal(MGraph G)FILE *fpt;fpt = fopen("9.txt","w");/* 打開文檔，寫入 */fprintf(fpt,"最小生成樹的各條邊為:n");int i,j;int k=0,a=0,b=0 ,min=G.arcsab,m in _out;printf("最小生

17、成樹的各條邊為:n");while(k<G.vex num-1)for(i=0;i<G.vex nu m;+i)for(j=i+1;j<G.vex nu m;+j)if(G.arcsij<mi n)mi n=G.arcsij;a=i;b=j;min_out=mi n;min=G.arcsab=0x7fffffff;prin tf("%s-%s-%dn",G.vexsa,G.vexsb,min_out); fprin tf(fpt,"%s-%s-%dn",G.vexsa,G.vexsb,min_out); k+;fclos

18、e(fpt);void mai n()MGraph g;CreateGraph(&g); kruskal(g);4. 調(diào)試與操作說明4.1測試結(jié)果：如下圖圖2測試結(jié)果1圖3測試結(jié)果24.2調(diào)試分析本程序利用克魯斯卡爾算法求最小生成樹數(shù)據(jù)結(jié)構(gòu)清晰因而調(diào)試比較順利。在調(diào)試過程中主要是參數(shù)的傳遞比較不容易掌握。 本程序的關(guān)鍵部分是如何確定一條 邊的兩個端點是否屬于同一連通分支，合并兩個連通分支。5. 課程設(shè)計總結(jié)與體會5.1總結(jié)：克魯斯卡爾算法中的核心思想就是逐個在邊的集合中找到最小的邊，如果滿 足條件就將其構(gòu)造，最后生成一個最小生成樹。它首先是一系列的頂點集合，并 沒有邊，然后我們從鄰接矩陣中尋找最小的邊，看看