




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
1、-作者xxxx-日期xxxxKruskal算法求最小生成樹.doc【精品文檔】荊楚理工學(xué)院課程設(shè)計成果 學(xué)院:_計算機工程學(xué)院_ 班 級: 14計算機科學(xué)與技術(shù)一班 學(xué)生姓名: 陳志杰 學(xué) 號: 設(shè)計地點(單位)_B5101_ _設(shè)計題目:克魯斯卡爾算法求最小生成樹_ 完成日期: 2015年 1月 6日 指導(dǎo)教師評語: _ _ _ _ 成績(五級記分制):_ _ _ 教師簽名:_ _數(shù)據(jù)結(jié)構(gòu)課程設(shè)計評分表班級計科一班姓名陳志杰指導(dǎo)教師李素若題目:克魯斯卡爾算法求最小生成樹評分標(biāo)準(zhǔn)評分標(biāo)準(zhǔn)分?jǐn)?shù)權(quán)重評分的依據(jù)得分AC選題10選題符合大綱要求,題目較新穎,工作量大選題基本符合大綱要求,工作量適中工作
2、態(tài)度10態(tài)度端正,能主動認(rèn)真完成各個環(huán)節(jié)的工作,不遲到早退,出勤好。能夠完成各環(huán)節(jié)基本工作,出勤較好。系統(tǒng)設(shè)計20能正確描述總體系統(tǒng)框架圖,主要函數(shù)有正確的流程圖。能基本正確描述總體系統(tǒng)框架圖,主要函數(shù)基本能給出流程圖。獨立解決問題的能力10具有獨立分析、解決問題能力,有一定的創(chuàng)造性,能夠獨立完成數(shù)據(jù)庫及相關(guān)軟件的設(shè)計與調(diào)試工作,程序結(jié)構(gòu)合理,邏輯嚴(yán)謹(jǐn),功能完善。有一定的分析、解決問題能力。能夠在老師指導(dǎo)下完成軟件的設(shè)計與調(diào)試工作,程序功能較完善。答辨問題回答20能準(zhǔn)確回答老師提出的問題能基本準(zhǔn)確回答老師提出的問題程序運行情況10程序運行正確、界面清晰,測試數(shù)據(jù)設(shè)計合理。程序運行正確、界面較清
3、晰,能給出合適的測試數(shù)據(jù)。課程設(shè)計論文20格式規(guī)范,層次清晰,設(shè)計思想明確,解決問題方法合理,體會深刻。格式較規(guī)范,設(shè)計思想基本明確,解決問題方法較合理??偡种笇?dǎo)教師(簽字):注:介于A和C之間為B級,低于C為D級和E級。按各項指標(biāo)打分后,總分在90100為優(yōu),8089為良,7079為中,6069為及格,60分以下為不及格。目 錄1 需求分析1系統(tǒng)目標(biāo)1主體功能1開發(fā)環(huán)境12 概要設(shè)計1功能模塊劃分12.2 系統(tǒng)流程圖23 詳細(xì)設(shè)計33.1 數(shù)據(jù)結(jié)構(gòu)33.2 模塊設(shè)計34測試34.1 測試數(shù)據(jù)3測試分析45總結(jié)與體會6總結(jié):6體會:6參考文獻7附錄 全部代碼8【精品文檔】1 需求分析 系統(tǒng)目標(biāo)
4、Kruskal算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。其基本思想是:首先選取全部的n個頂點,將其看成n個連通分量;然后按照網(wǎng)中邊的權(quán)值由小到大的順序,不斷的選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依照生成樹的概念,n個結(jié)點的生成樹有n-1條邊,故反復(fù)上述過程,直到選取了n-1條邊為止,就構(gòu)成了一棵最小生成樹。1.2主體功能在城市規(guī)劃設(shè)計中,假設(shè)有n個城市之間建立通信網(wǎng),則連通n個城市只需n-1條線路。這里自然考慮怎樣建立這n-1條路是總費用最省。把這n個城市抽象成一個連通網(wǎng),網(wǎng)的頂點表示各個城市,頂點與頂點之間的邊表示通信線路,各個城市之間的通訊線路看作邊,相應(yīng)的建設(shè)花費作為邊
5、的權(quán),這樣就構(gòu)成了一個網(wǎng)絡(luò)。由于在n個城市之間,可行線路有(n*(n-1)/2條,那么,如果選擇其中的n-1條線路(邊)在n個城市間建成全都能相互通訊的網(wǎng),并且總的建設(shè)花費為最?。窟@就是求該網(wǎng)絡(luò)的最小生成樹問題。本程序的目的是要建立一棵生成樹使總費用最少。開發(fā)環(huán)境裝有Windows 7操作系統(tǒng)的PC機vc+6.0,奔騰4 以上的處理器,編寫的程序需要在32MB的內(nèi)存中運行。推薦在以下基本配置電腦中運行:CPU Intel MMX 233MHz 內(nèi)存:64MB 硬盤空間:1.5GB 顯卡:4MB顯存以上的PCI、AGP顯卡聲卡:最新的PCI聲卡 CD-ROM:8x以上CD-ROM2 概要設(shè)計功能
6、模塊劃分運行程序后,程序在內(nèi)存中申請圖g的鄰接矩陣表示空間,存放作為用整型數(shù)組表示的頂點、邊、權(quán)值的數(shù)據(jù)。程序運行過程中調(diào)用存放在存放在ESP寄存器中的數(shù)據(jù),寄存器中存放著數(shù)據(jù)、地址和函數(shù)傳遞的中間結(jié)果。Kruskal算法在調(diào)用寄存器中的整型數(shù)據(jù),對邊上的權(quán)值進行冒泡排序,將權(quán)值小的邊放在數(shù)組的上面,然后在進行一次循環(huán)打印,循環(huán)過程中調(diào)用vset輔助數(shù)組的數(shù)據(jù)進行比較,兩個數(shù)據(jù)不相等就將該邊打印出來,不斷進行這個過程直至打印出n-1條邊(即頂點數(shù)減一的次數(shù))。具體的功能流程圖如下圖2.1功能流程圖所示。圖2.1 功能流程圖 系統(tǒng)流程圖輸入網(wǎng)圖的信息后,將網(wǎng)圖的邊、頂點、邊上的權(quán)值記錄在一個鄰接
7、矩陣中,在后面的kruskal算法中直接掃描鄰接矩陣,將邊的信息存放在算法定義的邊集數(shù)組中。圖2.2 系統(tǒng)流程圖3詳細(xì)設(shè)計3.1 數(shù)據(jù)結(jié)構(gòu)在Kruskal算法中的數(shù)據(jù)存放和調(diào)用采用整型變量,設(shè)置鄰接矩陣的最大頂點數(shù),設(shè)置圖的頂點信息為字符,設(shè)置邊上權(quán)值為整型,定義鄰接矩陣圖的頂點信息表還有圖的頂點數(shù)和邊數(shù)。Kruskal算法中有一個輔助數(shù)組,這里的存放的頂點信息的一維數(shù)組vexs的類型是用VertexType類型來表示的,這里把它定義成字符,在實際應(yīng)用中可以根據(jù)需要把它重新定義為其他系統(tǒng)預(yù)定義類型或結(jié)構(gòu)類型。此外,鄰接矩陣edges的類型用EdgeType類型表示,這里把它定義為整型。在實際應(yīng)
8、用中,若權(quán)值的類型是其他數(shù)據(jù)類型,則只需簡單修改即可。 模塊設(shè)計1. CreateMGraph創(chuàng)建一個鄰接矩陣存儲的圖。在提示下輸入無向圖的頂點數(shù)和邊數(shù),然后再輸入各個頂點的信息,也就是頂點的編號,再輸入頂點數(shù)組編號的下標(biāo)表示的邊和邊上的權(quán)值,這中間非網(wǎng)圖的邊的權(quán)值為1。2.Kruskal算法在掃描到鄰接矩陣存放的信息后,用冒泡排序?qū)⑦吷系臋?quán)值從小到大排列。定義一個輔助數(shù)組,該數(shù)組是用來判斷生成樹中是否會出現(xiàn)回路,也就是生成正確的最小生成樹。判斷邊的連通分量編號不相等,將這條邊打印出來,并將連通分量編號修改。循環(huán)頂點數(shù)減一次,將最小生成樹打印出來。4 測試4.1 測試數(shù)據(jù)主要的測試過程有兩個:
9、1. 對鄰接矩陣的輸入和存放??唆斔箍査惴ㄟ\行,得出最小生成樹。2. 克魯斯卡爾算法對存放的鄰接矩陣的調(diào)用。輸入圖的信息后算法得到正確結(jié)果。調(diào)試階段最重要的還是耐性和細(xì)心。要有足夠的耐性去對待令人煩躁的錯誤,一步步細(xì)心的調(diào)試,就會查出錯誤的所在。我們進行調(diào)試、測試是為了讓我們的代碼、程序更加健壯,質(zhì)量更高。所以,我們不要畏懼報錯,這是個學(xué)習(xí)進步的過程。3.調(diào)試過程中的輸入數(shù)據(jù)。第一組測試數(shù)據(jù)見表4-1。表4-1 調(diào)試數(shù)據(jù)權(quán)值50604065524550304270頂點i1243364565頂點j0011223334第二組測試數(shù)據(jù):表4-2 調(diào)試數(shù)據(jù)權(quán)值111111頂點i123434頂點j00
10、0012 第三組數(shù)據(jù):表4-3 調(diào)試數(shù)據(jù)權(quán)值164253頂點i123233頂點j000112 測試分析運行程序后輸入圖的信息。按照提示的格式輸入,輸入成功如下圖所示。 圖4.1 輸入圖的信息后的界面輸完信息后,程序運行得到最小生成樹的結(jié)果。圖4.2 求得的最小生成樹運行程序后輸入圖的信息。按照提示的格式輸入,輸入成功如下圖所示。 圖4.3 輸入圖的信息后的界面輸完信息后,程序運行得到最小生成樹的結(jié)果。圖4.4 求得的最小生成樹運行程序后輸入圖的信息。按照提示的格式輸入,輸入成功如下圖4.5所示。圖4.5 輸入圖的信息后的界面輸完信息后,程序運行得到最小生成樹的結(jié)果。圖求得的最小生成樹5 總結(jié)與
11、體會5.1總結(jié):克魯斯卡爾算法中的核心思想就是逐個在邊的集合中找到最小的邊,如果滿足條件就將其構(gòu)造,最后生成一個最小生成樹。它首先是一系列的頂點集合,并沒有邊,然后我們從鄰接矩陣中尋找最小的邊,看看它是否和現(xiàn)有的邊連接成一個環(huán),如果連接成環(huán),則舍棄,另外取其它的邊。如果不連接成環(huán),則接受這個邊,并把其納入集合中。5.2體會:在編程序過程中雖然遇到了很多問題,但也使我學(xué)到了很多東西,在編制程序過程中我學(xué)到了在編程的開始需要總體設(shè)計一下自己的程序需要哪些大的模塊,并想好所要用到的知識及算法,在編程過程中,特別是要畫圖時需要找出坐標(biāo),并研究各坐標(biāo)各結(jié)點之間連線的規(guī)律,通過幾句判斷語句來實現(xiàn)多條連線問
12、題,在編程過好還要反復(fù)調(diào)試程序,找出其中的漏洞并加以改正,在此次編程過程中就存在這樣的問題,在經(jīng)過反復(fù)修改后,終于可將漏洞掃除,正確的輸出結(jié)果。參考文獻1李素若,陳萬華,游明坤. 數(shù)據(jù)結(jié)構(gòu). 北京:中國水利水電出版社,2014.2 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版). 北京:清華大學(xué)出版社,2014.3李素若,任正云,賴玲.C語言程序設(shè)計. 北京::中國水利水電出版社,2014.4鄧文華.數(shù)據(jù)結(jié)構(gòu)(C語言版). 北京:清華大學(xué)出版社,2011.附錄 全部代碼#include#include#define MaxVerNum 100 /設(shè)置鄰接矩陣的最大頂點數(shù)typedef char Vert
13、exType; /設(shè)置圖的頂點信息為整型typedef int EdgeType; /設(shè)置邊上權(quán)值為整型typedef structVertexType vexsMaxVerNum; /圖的頂點信息表EdgeType edgeMaxVerNumMaxVerNum;/圖的鄰接矩陣int n,e; /圖的頂點數(shù)和邊數(shù)MGraph; /圖的鄰接矩陣表示結(jié)構(gòu)定義void CreateMGraph(MGraph *g)/建立圖g的鄰接矩陣表示int i,j,k,w;printf(輸入頂點數(shù)和邊數(shù)(格式為:頂點數(shù),邊數(shù))n); scanf(%d,%d,&g-n,&g-e); printf(輸入頂點的信息:
14、n); for(i=0;in;i+) getchar();scanf(%c,&(g-vexsi); for(i=0;in;i+) /將鄰接矩陣數(shù)組初始化 for(j=0;jn;j+) g-edgeij=0;/圖的遍歷算法初始化該值為0 for(k=0;ke;k+) printf(輸入邊的兩個頂點號的下標(biāo),權(quán)值w(非網(wǎng)圖權(quán)值為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,vestMaxVerNum;/vset輔助數(shù)組 in
15、t v1,v2; struct edgeType/定義邊信息結(jié)構(gòu) int u,v;/每條邊兩個頂點的數(shù)組下標(biāo)號 int w;/權(quán)值 t,*edge; edge=(struct edgeType *)malloc(g-e*sizeof(struct edgeType); k=0; for(i=0;in;i+)/掃描鄰接矩陣,將邊信息存儲到邊集數(shù)組 for(j=0;jn;j+) if(g-edgeij&iedgeij; k+; for(j=1;jk;j+)/對邊集權(quán)值采用冒泡排序 for(i=0;iedgei+1.w) t=edgei; edgei=edgei+1; edgei+1=t; for(i=0;ie;i+)vesti=i;/初始化G中各頂點的vset值 num=1;/構(gòu)造生成樹的第幾條邊,從1開始 j=0;/從邊集數(shù)組下標(biāo)0開始處理 while(numn)/循環(huán)n-1次,構(gòu)造n-1條邊 v1=edgej.u;v2=edgej.v;/取邊的兩個頂點號 s1=vestv1;s2=vestv2;/分別求兩個頂點的連通分量的編號 if(s1!=s2)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 香椿種植轉(zhuǎn)讓合同范本
- 南昌購房合同范本
- 余泥外運合同范本
- 衛(wèi)星定位合同范本
- 合同范本從里
- 不良資產(chǎn)合同范本
- 小型裝修合同范本
- 北京地暖合同范本
- 包工頭和工人簽合同范本
- 合同范本快速打字
- 日本商務(wù)禮儀課件
- 公務(wù)用車申請表
- 中國民間傳說:田螺姑娘
- 淺談鋼琴即興伴奏在教學(xué)中應(yīng)用現(xiàn)狀及提高方法 論文
- 身體功能訓(xùn)練
- 部編人教版四年級語文下冊《全冊全套》課件ppt
- 英文版-你來比劃我來猜游戲
- 皖2015s209 混凝土砌塊式排水檢查井
- 五年級道德與法治下冊 (我參與我奉獻)新課件
- 診所負(fù)責(zé)人聘用合同
- 單層工業(yè)廠房排架結(jié)構(gòu)設(shè)計正文
評論
0/150
提交評論