Kruskal算法求最小生成樹doc

1、荊楚理工學院課程設計成果 學院:_計算機工程學院_ 班 級: 14計算機科學與技術一班 學生姓名: 陳志杰 學 號: 設計地點（單位）_B5101_ _設計題目:克魯斯卡爾算法求最小生成樹_ 完成日期： 2015年 1月 6日 指導教師評語: _ _ _ _ 成績(五級記分制):_ _ _ 教師簽名:_ _數(shù)據(jù)結構課程設計評分表班級 計科一班姓名陳志杰 指導教師李素若 題目：克魯斯卡爾算法求最小生成樹評分標準評分標準分數(shù)權重評分的依據(jù)得分AC選題10選題符合大綱要求，題目較新穎，工作量大選題基本符合大綱要求，工作量適中 工作態(tài)度10態(tài)度端正，能主動認真完

2、成各個環(huán)節(jié)的工作，不遲到早退，出勤好。能夠完成各環(huán)節(jié)基本工作，出勤較好。 系統(tǒng)設計20能正確描述總體系統(tǒng)框架圖，主要函數(shù)有正確的流程圖。能基本正確描述總體系統(tǒng)框架圖，主要函數(shù)基本能給出流程圖。 獨立解決問題的能力10具有獨立分析、解決問題能力，有一定的創(chuàng)造性，能夠獨立完成數(shù)據(jù)庫及相關軟件的設計與調(diào)試工作，程序結構合理，邏輯嚴謹，功能完善。有一定的分析、解決問題能力。能夠在老師指導下完成軟件的設計與調(diào)試工作，程序功能較完善。 答辨問題回答20能準確回答老師提出的問題能基本準確回答老師提出的問題 程序運行情況10程序運行正確、界面清晰，測試數(shù)據(jù)設計合理。程序

3、運行正確、界面較清晰，能給出合適的測試數(shù)據(jù)。 課程設計論文20格式規(guī)范，層次清晰，設計思想明確，解決問題方法合理，體會深刻。格式較規(guī)范，設計思想基本明確，解決問題方法較合理。 總分 指導教師（簽字）：注：介于A和C之間為B級，低于C為D級和E級。按各項指標打分后，總分在90100為優(yōu)，8089為良，7079為中，6069為及格，60分以下為不及格。目 錄1 需求分析11.1系統(tǒng)目標11.2主體功能11.3開發(fā)環(huán)境12 概要設計12.1功能模塊劃分12.2 系統(tǒng)流程圖23 詳細設計33.1 數(shù)據(jù)結構33.2 模塊設計34測試34.1 測試數(shù)據(jù)34.2測試分析45總結

4、與體會65.1總結：65.2體會：6參考文獻7附錄 全部代碼81 需求分析 1.1系統(tǒng)目標Kruskal算法是一種按照網(wǎng)中邊的權值遞增的順序構造最小生成樹的方法。其基本思想是：首先選取全部的n個頂點，將其看成n個連通分量；然后按照網(wǎng)中邊的權值由小到大的順序，不斷的選取當前未被選取的邊集中權值最小的邊。依照生成樹的概念，n個結點的生成樹有n-1條邊，故反復上述過程，直到選取了n-1條邊為止，就構成了一棵最小生成樹。1.2主體功能在城市規(guī)劃設計中，假設有n個城市之間建立通信網(wǎng)，則連通n個城市只需n-1條線路。這里自然考慮怎樣建立這n-1條路是總費用最省。把這n個城市抽象成一個連通網(wǎng)，網(wǎng)的頂點表示各

5、個城市，頂點與頂點之間的邊表示通信線路，各個城市之間的通訊線路看作邊，相應的建設花費作為邊的權，這樣就構成了一個網(wǎng)絡。由于在n個城市之間，可行線路有(n*(n-1)/2條，那么，如果選擇其中的n-1條線路(邊)在n個城市間建成全都能相互通訊的網(wǎng)，并且總的建設花費為最??？這就是求該網(wǎng)絡的最小生成樹問題。本程序的目的是要建立一棵生成樹使總費用最少。 1.3開發(fā)環(huán)境裝有Windows 7操作系統(tǒng)的PC機vc+6.0，奔騰4 1.0GHz以上的處理器，編寫的程序需要在32MB的內(nèi)存中運行。推薦在以下基本配置電腦中運行：CPU Intel MMX 233MHz 內(nèi)存：64MB 硬盤空間：1.5

6、GB 顯卡：4MB顯存以上的PCI、AGP顯卡聲卡：最新的PCI聲卡 CD-ROM：8x以上CD-ROM2 概要設計2.1功能模塊劃分運行程序后，程序在內(nèi)存中申請圖g的鄰接矩陣表示空間，存放作為用整型數(shù)組表示的頂點、邊、權值的數(shù)據(jù)。程序運行過程中調(diào)用存放在存放在ESP寄存器中的數(shù)據(jù)，寄存器中存放著數(shù)據(jù)、地址和函數(shù)傳遞的中間結果。Kruskal算法在調(diào)用寄存器中的整型數(shù)據(jù)，對邊上的權值進行冒泡排序，將權值小的邊放在數(shù)組的上面，然后在進行一次循環(huán)打印，循環(huán)過程中調(diào)用vset輔助數(shù)組的數(shù)據(jù)進行比較，兩個數(shù)據(jù)不相等就將該邊打印出來，不斷進行這個過程直至打印出n-1條邊（即頂點數(shù)減一的次數(shù)）。具體的功能

7、流程圖如下圖2.1功能流程圖所示。圖2.1 功能流程圖2.2 系統(tǒng)流程圖輸入網(wǎng)圖的信息后，將網(wǎng)圖的邊、頂點、邊上的權值記錄在一個鄰接矩陣中，在后面的kruskal算法中直接掃描鄰接矩陣，將邊的信息存放在算法定義的邊集數(shù)組中。圖2.2 系統(tǒng)流程圖3詳細設計3.1 數(shù)據(jù)結構在Kruskal算法中的數(shù)據(jù)存放和調(diào)用采用整型變量，設置鄰接矩陣的最大頂點數(shù)，設置圖的頂點信息為字符，設置邊上權值為整型，定義鄰接矩陣圖的頂點信息表還有圖的頂點數(shù)和邊數(shù)。Kruskal算法中有一個輔助數(shù)組，這里的存放的頂點信息的一維數(shù)組vexs的類型是用VertexType類型來表示的，這里把它定義成字符，在實際應用中可以根據(jù)需

8、要把它重新定義為其他系統(tǒng)預定義類型或結構類型。此外，鄰接矩陣edges的類型用EdgeType類型表示，這里把它定義為整型。在實際應用中，若權值的類型是其他數(shù)據(jù)類型，則只需簡單修改即可。3.2 模塊設計1. CreateMGraph創(chuàng)建一個鄰接矩陣存儲的圖。在提示下輸入無向圖的頂點數(shù)和邊數(shù)，然后再輸入各個頂點的信息，也就是頂點的編號，再輸入頂點數(shù)組編號的下標表示的邊和邊上的權值，這中間非網(wǎng)圖的邊的權值為1。2.Kruskal算法在掃描到鄰接矩陣存放的信息后，用冒泡排序?qū)⑦吷系臋嘀祻男〉酱笈帕?。定義一個輔助數(shù)組，該數(shù)組是用來判斷生成樹中是否會出現(xiàn)回路，也就是生成正確的最小生成樹。判斷邊的連通分量

9、編號不相等，將這條邊打印出來，并將連通分量編號修改。循環(huán)頂點數(shù)減一次，將最小生成樹打印出來。4 測試4.1 測試數(shù)據(jù)主要的測試過程有兩個：1. 對鄰接矩陣的輸入和存放。克魯斯卡爾算法運行，得出最小生成樹。2. 克魯斯卡爾算法對存放的鄰接矩陣的調(diào)用。輸入圖的信息后算法得到正確結果。調(diào)試階段最重要的還是耐性和細心。要有足夠的耐性去對待令人煩躁的錯誤，一步步細心的調(diào)試，就會查出錯誤的所在。我們進行調(diào)試、測試是為了讓我們的代碼、程序更加健壯，質(zhì)量更高。所以，我們不要畏懼報錯，這是個學習進步的過程。3.調(diào)試過程中的輸入數(shù)據(jù)。第一組測試數(shù)據(jù)見表4-1。表4-1 調(diào)試數(shù)據(jù)權值5060406552455030

10、4270頂點i1243364565頂點j0011223334第二組測試數(shù)據(jù)：表4-2 調(diào)試數(shù)據(jù)權值111111頂點i123434頂點j000012 第三組數(shù)據(jù)：表4-3 調(diào)試數(shù)據(jù)權值164253頂點i123233頂點j000112 4.2測試分析1.第一組數(shù)據(jù)測試結果運行程序后輸入圖的信息。按照提示的格式輸入，輸入成功如下圖4.1所示。 圖4.1 輸入圖的信息后的界面輸完信息后，程序運行得到最小生成樹的結果。圖4.2 求得的最小生成樹2.第二組數(shù)據(jù)測試結果運行程序后輸入圖的信息。按照提示的格式輸入，輸入成功如下圖4.3所示。 圖4.3 輸入圖的信息后的界面輸完信息后，程序運行得到最小生成樹的結

11、果。圖4.4 求得的最小生成樹3.第三組數(shù)據(jù)測試結果運行程序后輸入圖的信息。按照提示的格式輸入，輸入成功如下圖4.5所示。圖4.5 輸入圖的信息后的界面輸完信息后，程序運行得到最小生成樹的結果。圖4.6求得的最小生成樹5 總結與體會5.1總結：克魯斯卡爾算法中的核心思想就是逐個在邊的集合中找到最小的邊，如果滿足條件就將其構造，最后生成一個最小生成樹。它首先是一系列的頂點集合，并沒有邊，然后我們從鄰接矩陣中尋找最小的邊，看看它是否和現(xiàn)有的邊連接成一個環(huán)，如果連接成環(huán)，則舍棄，另外取其它的邊。如果不連接成環(huán)，則接受這個邊，并把其納入集合中。5.2體會：在編程序過程中雖然遇到了很多問題，但也使我學到

12、了很多東西，在編制程序過程中我學到了在編程的開始需要總體設計一下自己的程序需要哪些大的模塊，并想好所要用到的知識及算法，在編程過程中，特別是要畫圖時需要找出坐標，并研究各坐標各結點之間連線的規(guī)律，通過幾句判斷語句來實現(xiàn)多條連線問題，在編程過好還要反復調(diào)試程序，找出其中的漏洞并加以改正，在此次編程過程中就存在這樣的問題，在經(jīng)過反復修改后，終于可將漏洞掃除，正確的輸出結果。參考文獻1李素若，陳萬華，游明坤. 數(shù)據(jù)結構. 北京：中國水利水電出版社，2014. 2 嚴蔚敏，吳偉民.數(shù)據(jù)結構（C語言版）. 北京：清華大學出版社，2014.3李素若，任正云，賴玲.C語言程序設計.  北

13、京:：中國水利水電出版社， 2014.4鄧文華.數(shù)據(jù)結構（C語言版）. 北京：清華大學出版社，2011.附錄 全部代碼#include<stdio.h>#include<stdlib.h>#define MaxVerNum 100 /設置鄰接矩陣的最大頂點數(shù)typedef char VertexType; /設置圖的頂點信息為整型typedef int EdgeType; /設置邊上權值為整型typedef structVertexType vexsMaxVerNum; /圖的頂點信息表EdgeType edgeMaxVerNumMaxVerNum;/圖的鄰接

14、矩陣int n,e; /圖的頂點數(shù)和邊數(shù)MGraph; /圖的鄰接矩陣表示結構定義void CreateMGraph(MGraph *g)/建立圖g的鄰接矩陣表示int i,j,k,w;printf("輸入頂點數(shù)和邊數(shù)(格式為:頂點數(shù),邊數(shù))n"); scanf("%d,%d",&g->n,&g->e); printf("輸入頂點的信息:n"); for(i=0;i<g->n;i+) getchar();scanf("%c",&(g->vexsi); for(i

15、=0;i<g->n;i+) /將鄰接矩陣數(shù)組初始化 for(j=0;j<g->n;j+) g->edgeij=0;/圖的遍歷算法初始化該值為0 for(k=0;k<g->e;k+) printf("輸入邊的兩個頂點號的下標，權值w(非網(wǎng)圖權值為1)(格式為*,*,*):n"); scanf("%d,%d,%d",&i,&j,&w); g->edgeij=w; g->edgeji=w; void kruskal(MGraph *g) int i,j,k,s1,s2,num,ves

16、tMaxVerNum;/vset輔助數(shù)組 int v1,v2; struct edgeType/定義邊信息結構 int u,v;/每條邊兩個頂點的數(shù)組下標號 int w;/權值 t,*edge; edge=(struct edgeType *)malloc(g->e*sizeof(struct edgeType); k=0; for(i=0;i<g->n;i+)/掃描鄰接矩陣，將邊信息存儲到邊集數(shù)組 for(j=0;j<g->n;j+) if(g->edgeij&&i<j) edgek.u=i;edgek.v=j; edgek.w=g-

17、>edgeij; k+; for(j=1;j<k;j+)/對邊集權值采用冒泡排序 for(i=0;i<k-j;i+) if(edgei.w>edgei+1.w) t=edgei; edgei=edgei+1; edgei+1=t; for(i=0;i<g->e;i+)vesti=i;/初始化G中各頂點的vset值 num=1;/構造生成樹的第幾條邊，從1開始 j=0;/從邊集數(shù)組下標0開始處理 while(num<g->n)/循環(huán)n-1次，構造n-1條邊 v1=edgej.u;v2=edgej.v;/取邊的兩個頂點號 s1=vestv1;s2=vestv2;/分別求兩個頂點的連通分量的編號 if(s1!=s2) printf("(%c,