Kruskal算法求最小生成樹

WordWord文檔WordWord文檔荊楚理工學(xué)院課程設(shè)計(jì)成果學(xué)院:班級:14計(jì)算機(jī)科學(xué)與技術(shù)一班學(xué)生姓名：志杰學(xué)號:設(shè)計(jì)地點(diǎn)（單位）B5101設(shè)計(jì)題目:克魯斯卡爾算法求最小生成樹完成日期：2015年1月6日指導(dǎo)教師評語:成績（五級記分制）:教師簽名:

數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)評分表班級計(jì)科一班姓名志杰1指導(dǎo)教師素若題目：克魯斯卡爾算法求最小生成樹評分標(biāo)準(zhǔn)評分標(biāo)準(zhǔn)分?jǐn)?shù)權(quán)重評分的依據(jù)得分AC選題10選題符合大綱要求，題目較新穎，工作量大選題基本符合大綱要求，工作量適中工作態(tài)度10態(tài)度端正，能主動認(rèn)真完成各個環(huán)節(jié)的工作，不遲到早退，出勤好。能夠完成各環(huán)節(jié)基本工作，出勤較好。系統(tǒng)設(shè)計(jì)20能正確描述總體系統(tǒng)框架圖，主要函數(shù)有正確的流程圖。能基本正確描述總體系統(tǒng)框架圖，主要函數(shù)基本能給出流程圖。獨(dú)立解決問題的能力10具有獨(dú)立分析、解決問題能力，有一定的創(chuàng)造性，能夠獨(dú)立完成數(shù)據(jù)庫及相關(guān)軟件的設(shè)計(jì)與調(diào)試工作，程序結(jié)構(gòu)合理，邏輯嚴(yán)謹(jǐn)，功能完善。有一定的分析、解決問題能力。能夠在老師指導(dǎo)下完成軟件的設(shè)計(jì)與調(diào)試工作，程序功能較元善。答辨問題回答20能準(zhǔn)確回答老師提出的問題能基本準(zhǔn)確回答老師提出的問題程序運(yùn)行情況10程序運(yùn)行正確、界面清晰，測試數(shù)據(jù)設(shè)計(jì)合理。程序運(yùn)行正確、界面較清晰，能給出合適的測試數(shù)據(jù)。課程設(shè)計(jì)論文20格式規(guī)，層次清晰，設(shè)計(jì)思想明確，解決問題方法合理，體會深刻。格式較規(guī)，設(shè)計(jì)思想基本明確，解決問題方法較合理?？偡种笇?dǎo)教師（簽字）：注：介于A和C之間為B級，低于C為D級和E級。按各項(xiàng)指標(biāo)打分后，總分在90~100為優(yōu),80~89為良，70?79為中，60?69為及格，60分以下為不及格。目錄TOC\o"1-5"\h\z需求分析11.1系統(tǒng)目標(biāo)11.2主體功能11.3開發(fā)環(huán)境1概要設(shè)計(jì)12.1功能模塊劃分1系統(tǒng)流程圖2詳細(xì)設(shè)計(jì)3數(shù)據(jù)結(jié)構(gòu)3模塊設(shè)計(jì)3測試3測試數(shù)據(jù)34.2測試分析4總結(jié)與體會65.1總結(jié)：65.2體會：6參考文獻(xiàn)7WordWord文檔WordWord文檔需求分析系統(tǒng)目標(biāo)Kruskal算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。其基本思想是：首先選取全部的n個頂點(diǎn)，將其看成n個連通分量；然后按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷的選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依照生成樹的概念，n個結(jié)點(diǎn)的生成樹有n-1條邊，故反復(fù)上述過程，直到選取了n-1條邊為止，就構(gòu)成了一棵最小生成樹。主體功能在城市規(guī)劃設(shè)計(jì)中，假設(shè)有n個城市之間建立通信網(wǎng)，則連通n個城市只需n-1條線路。這里自然考慮怎樣建立這n-1條路是總費(fèi)用最省。把這n個城市抽象成一個連通網(wǎng)，網(wǎng)的頂點(diǎn)表示各個城市，頂點(diǎn)與頂點(diǎn)之間的邊表示通信線路，各個城市之間的通訊線路看作邊，相應(yīng)的建設(shè)花費(fèi)作為邊的權(quán)，這樣就構(gòu)成了一個網(wǎng)絡(luò)。由于在n個城市之間，可行線路有（n*（n-1））/2條，那么，如果選擇其中的n-1條線路（邊）在n個城市間建成全都能相互通訊的網(wǎng)，并且總的建設(shè)花費(fèi)為最??？這就是求該網(wǎng)絡(luò)的最小生成樹問題。本程序的目的是要建立一棵生成樹使總費(fèi)用最少。開發(fā)環(huán)境裝有Windows7操作系統(tǒng)的PC機(jī)vc++6.0,奔騰41.0GHz以上的處理器，編寫的程序需要在32MB的存中運(yùn)行。推薦在以下基本配置電腦中運(yùn)行：CPUIntelMMX233MHz存：64MB硬盤空間：1.5GB顯卡：4MB顯存以上的PCI、AGP顯卡聲卡：最新的PCI聲卡CD-ROM:8x以上CD-ROM概要設(shè)計(jì)2.1功能模塊劃分運(yùn)行程序后，程序在存中申請圖g的鄰接矩陣表示空間，存放作為用整型數(shù)組表示的頂點(diǎn)、邊、權(quán)值的數(shù)據(jù)。程序運(yùn)行過程中調(diào)用存放在存放在ESP寄存器中的數(shù)據(jù)，寄存器中存放著數(shù)據(jù)、地址和函數(shù)傳遞的中間結(jié)果。Kruskal算法在調(diào)用寄存器中的整型數(shù)據(jù)，對邊上的權(quán)值進(jìn)行冒泡排序，將權(quán)值小的邊放在數(shù)組的上面，然后在進(jìn)行一次循環(huán)打印，循環(huán)過程中調(diào)用vset輔助數(shù)組的數(shù)據(jù)進(jìn)行比較，兩個數(shù)據(jù)不相等就將該邊打印出來，不斷進(jìn)行這個過程直至打印出n-1條邊（即

頂點(diǎn)數(shù)減一的次數(shù)）。具體的功能流程圖如下圖2.1功能流程圖所示圖2.1功能流程圖2?2系統(tǒng)流程圖輸入網(wǎng)圖的信息后，將網(wǎng)圖的邊、頂點(diǎn)、邊上的權(quán)值記錄在一個鄰接矩陣中，在后

面的kruskal算法中直接掃描鄰接矩陣，將邊的信息存放在算法定義的邊集數(shù)組中。圖2.2系統(tǒng)流程圖詳細(xì)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)在Kruskal算法中的數(shù)據(jù)存放和調(diào)用采用整型變量，設(shè)置鄰接矩陣的最大頂點(diǎn)數(shù)，設(shè)置圖的頂點(diǎn)信息為字符，設(shè)置邊上權(quán)值為整型，定義鄰接矩陣圖的頂點(diǎn)信息表還有圖的頂點(diǎn)數(shù)和邊數(shù)。Kruskal算法中有一個輔助數(shù)組，這里的存放的頂點(diǎn)信息的一維數(shù)組vexs的類型是用VertexType類型來表示的，這里把它定義成字符，在實(shí)際應(yīng)用中可以根據(jù)需要把它重新定義為其他系統(tǒng)預(yù)定義類型或結(jié)構(gòu)類型。此外，鄰接矩陣edges的類型用EdgeType類型表示，這里把它定義為整型。在實(shí)際應(yīng)用中，若權(quán)值的類型是其他數(shù)據(jù)類型，則只需簡單修改即可。模塊設(shè)計(jì)CreateMGraph創(chuàng)建一個鄰接矩陣存儲的圖。在提示下輸入無向圖的頂點(diǎn)數(shù)和邊數(shù)，然后再輸入各個頂點(diǎn)的信息，也就是頂點(diǎn)的編號，再輸入頂點(diǎn)數(shù)組編號的下標(biāo)表示的邊和邊上的權(quán)值，這中間非網(wǎng)圖的邊的權(quán)值為1。Kruskal算法在掃描到鄰接矩陣存放的信息后，用冒泡排序?qū)⑦吷系臋?quán)值從小到大排列。定義一個輔助數(shù)組，該數(shù)組是用來判斷生成樹中是否會出現(xiàn)回路，也就是生成正確的最小生成樹。判斷邊的連通分量編號不相等，將這條邊打印出來，并將連通分量編號修改。循環(huán)頂點(diǎn)數(shù)減一次，將最小生成樹打印出來。測試4.1測試數(shù)據(jù)主要的測試過程有兩個：1.對鄰接矩陣的輸入和存放?？唆斔箍査惴ㄟ\(yùn)行，得出最小生成樹。2.克魯斯卡爾算法對存放的鄰接矩陣的調(diào)用。輸入圖的信息后算法得到正確結(jié)果。調(diào)試階段最重要的還是耐性和細(xì)心。要有足夠的耐性去對待令人煩躁的錯誤，一步步細(xì)心的調(diào)試，就會查出錯誤的所在。我們進(jìn)行調(diào)試、測試是為了讓我們的代碼、程序更加健壯，質(zhì)量更高。所以，我們不要畏懼報(bào)錯，這是個學(xué)習(xí)進(jìn)步的過程。調(diào)試過程中的輸入數(shù)據(jù)。第一組測試數(shù)據(jù)見表4-1。表4-1調(diào)試數(shù)據(jù)權(quán)值50604065524550304270頂點(diǎn)i1243364565頂點(diǎn)j0011223334第二組測試數(shù)據(jù)：

表4-2調(diào)試數(shù)據(jù)權(quán)值111111頂點(diǎn)i123434頂點(diǎn)j000012第三組數(shù)據(jù)：表4-3調(diào)試數(shù)據(jù)權(quán)值164253頂點(diǎn)i123233頂點(diǎn)j0001124.2測試分析1?第一組數(shù)據(jù)測試結(jié)果運(yùn)行程序后輸入圖的信息。按照提示的格式輸入，輸入成功如下圖4.1所示A扁人邊的兩T西點(diǎn)號m下標(biāo).權(quán)值W非兩宙段荷為1&娜?"日”1”50*>■；：'■■T■■號白f.?*S；"fy*>■「.仏"可-I?迫，?宀可丄'：H「.仏"可-I?迫，?宀可丄'：H「：■心「.迫可丄八迫JI'-'nnCL-:.：5一1”|"+一?.權(quán)值E阿囲拘訃端養(yǎng)為幡人辿的両「號的下標(biāo),I.i.i-.；!-.十“r--；-'I-.?■.3^m："f--；-'I'■；：：■:嚴(yán)rr「T-■J.4.Lt瞼人迪的兩牛頂點(diǎn)號曲下標(biāo)，；/■'；r：|--I.r-■?：..■：：：1x1“；.囂'T'fT:~h_l-.F7i..c：：_T^'n-i:k|■i.h.vx圖4.1輸入圖的信息后的界面輸完信息后，程序運(yùn)行得到最小生成樹的結(jié)果<d,f〉一一ueight=30<b,e〉--uei^lit=40<d,g>--ueiglit=42<c,g?一一ueiglit=45<a,h?~ueiglit=50<d,e〉—ueight=50潔按任意鍵繼縝??圖4.2求得的最小生成樹2?第二組數(shù)據(jù)測試結(jié)果運(yùn)行程序后輸入圖的信息。按照提示的格式輸入，輸入成功如下圖4.3所示。WordWord文檔WordWord文檔輸入頂點(diǎn)數(shù)和邊數(shù)(格式為:頂點(diǎn)數(shù)亠邊數(shù)〉5,6輸入頂點(diǎn)的信息：125輸入邊的兩個頂點(diǎn)號的下標(biāo),0,1,1輸入邊的兩個頂點(diǎn)號的下標(biāo),0,2,1輸入邊的兩個頂點(diǎn)號的下標(biāo),0,3,1輸入邊的兩個頂點(diǎn)號的下標(biāo),0,4,1輸入邊的兩個頂點(diǎn)號的下標(biāo),5輸入邊的兩個頂點(diǎn)號的下標(biāo),0,1,1輸入邊的兩個頂點(diǎn)號的下標(biāo),0,2,1輸入邊的兩個頂點(diǎn)號的下標(biāo),0,3,1輸入邊的兩個頂點(diǎn)號的下標(biāo),0,4,1輸入邊的兩個頂點(diǎn)號的下標(biāo),1.3.1輸入邊的兩個頂點(diǎn)號的下標(biāo),2.4.1權(quán)值點(diǎn)非網(wǎng)圖權(quán)值為1X格式為*,*,*>:權(quán)值點(diǎn)非網(wǎng)圖權(quán)值為1X格式為巴巴*>:權(quán)值點(diǎn)非網(wǎng)圖權(quán)值為1X格式為*,*>:權(quán)值點(diǎn)非網(wǎng)圖權(quán)值為1X格式為*,*,*>:圖4.3輸入圖的信息后的界面輸完信息后，程序運(yùn)行得到最小生成樹的結(jié)果。(1,2、—ueig-ht=1<1,3、—ueig-ht=1<1,4>--vieisfht=1<1,5>--i?eisfht=1請按任意鍵繼繕???■圖4.4求得的最小生成樹3?第三組數(shù)據(jù)測試結(jié)果運(yùn)行程序后輸入圖的信息。按照提示的格式輸入，輸入成功如下圖4.5所示輜?頂.占第三：遼第訂頂.占第.遼第》4Phfel人頂點(diǎn)的信息:I：1輸k邊的兩個頂盧號的下標(biāo)，權(quán)值旅非網(wǎng)圖權(quán)值対：池格式対匚匚唧:r頂盧半］下民仁匸譏眉可二出⑴訂腎心mi、頂盧半］下民仁匸譏眉可二出⑴訂頂盧半］下民仁匸譏眉可二出⑴訂旳m、頂盧半］下民仁匸譏眉可二出⑴訂r頂盧半］下民仁匸譏眉可二出⑴訂x：i.：i圖4.5輸入圖的信息后的界面輸完信息后，程序運(yùn)行得到最小生成樹的結(jié)果<1,2〉—ueigflit=1<2,35—ueiglit=2<3,4>--ueiglit=3請按任意犍繼繕??圖4.6求得的最小生成樹5總結(jié)與體會5?1總結(jié)：克魯斯卡爾算法中的核心思想就是逐個在邊的集合中找到最小的邊，如果滿足條件就將其構(gòu)造，最后生成一個最小生成樹。它首先是一系列的頂點(diǎn)集合，并沒有邊，然后我們從鄰接矩陣中尋找最小的邊，看看它是否和現(xiàn)有的邊連接成一個環(huán)，如果連接成環(huán)，則舍棄，另外取其它的邊。如果不連接成環(huán)，則接受這個邊，并把其納入集合中。5?2體會：在編程序過程中雖然遇到了很多問題，但也使我學(xué)到了很多東西，在編制程序過程中我學(xué)到了在編程的開始需要總體設(shè)計(jì)一下自己的程序需要哪些大的模塊，并想好所要用到的知識及算法，在編程過程中，特別是要畫圖時需要找出坐標(biāo)，并研究各坐標(biāo)各結(jié)點(diǎn)之間連線的規(guī)律，通過幾句判斷語句來實(shí)現(xiàn)多條連線問題，在編程過好還要反復(fù)調(diào)試程序，找出其中的漏洞并加以改正，在此次編程過程中就存在這樣的問題，在經(jīng)過反復(fù)修改后，終于可將漏洞掃除，正確的輸出結(jié)果。WordWord文檔WordWord文檔參考文獻(xiàn)素若，萬華，游明坤.數(shù)據(jù)結(jié)構(gòu).北京：中國水利水電出版社，2014.嚴(yán)蔚敏，吳偉民?數(shù)據(jù)結(jié)構(gòu)（C語言版）?北京：清華大學(xué)出版社，2014.素若，任正云，賴玲.C語言程序設(shè)計(jì).北京：：中國水利水電出版社，2014.鄧文華?數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版社，2011.附錄全部代碼#include<stdio.h>#include<stdlib.h>#defineMaxVerNum100//設(shè)置鄰接矩陣的最大頂點(diǎn)數(shù)typedefcharVertexType;//設(shè)置圖的頂點(diǎn)信息為整型typedefintEdgeType;//設(shè)置邊上權(quán)值為整型typedefstruct{VertexTypevexs[MaxVerNum];//圖的頂點(diǎn)信息表EdgeTypeedge[MaxVerNum][MaxVerNum];//圖的鄰接矩陣intn,e;//圖的頂點(diǎn)數(shù)和邊數(shù)}MGraph;//圖的鄰接矩陣表示結(jié)構(gòu)定義voidCreateMGraph(MGraph*g)//建立圖g的鄰接矩陣表示{inti,j,k,w;printf(”輸入頂點(diǎn)數(shù)和邊數(shù)(格式為:頂點(diǎn)數(shù)，邊數(shù))\n");scanf("%d,%d",&g->n,&g->e);printf(”輸入頂點(diǎn)的信息:\n");for(i=0;i<g->n;i++){getchar();scanf("%c",&(g->vexs[i]));}for(i=0;i<g->n;i++)//將鄰接矩陣數(shù)組初始化for(j=0;j<g->n;j++)g->edge[i][j]=0;//圖的遍歷算法初始化該值為0for(k=0;k<g->e;k++){printf(”輸入邊的兩個頂點(diǎn)號的下標(biāo)，權(quán)值w(非網(wǎng)圖權(quán)值為1)(格式為*,*,*):\n");scanf("%d,%d,%d",&i,&j,&w);g->edge[i][j]=w;g->edge[j][i]=w;}voidkruskal(MGraph*g){inti,j,k,s1,s2,num,vest[MaxVerNum];//vset輔助數(shù)組intv1,v2;structedgeType{〃定義邊信息結(jié)構(gòu)intu,v;//每條邊兩個頂點(diǎn)的數(shù)組下標(biāo)號intw;//權(quán)值}t,*edge;edge=(structedgeType*)malloc(g->e*sizeof(structedgeType));k=0;for(i=O;i<g->n;i++)〃掃描鄰接矩陣，將邊信息存儲到邊集數(shù)組for(j=0;j<g->n;j++)if(g->edge[i][j]&&i<j){edge[k].u=i;edge[k].v=j;ed