Kruskal算法求最小生成樹.doc

《Kruskal算法求最小生成樹.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、荊楚理工學(xué)院課程設(shè)計(jì)成果學(xué)院:_______計(jì)算機(jī)工程學(xué)院__________班級(jí):14計(jì)算機(jī)科學(xué)與技術(shù)一班學(xué)生姓名:陳志杰學(xué)號(hào):2014407020137設(shè)計(jì)地點(diǎn)（單位）_____B5101_____________________設(shè)計(jì)題目:克魯斯卡爾算法求最小生成樹__________________________________完成日期：2015年1月6日指導(dǎo)教師評(píng)語:___________________________________________________________________________________________________

2、________________________________________________________________________________________________________________________________________________________成績(jī)(五級(jí)記分制):________________教師簽名:_________________________《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)評(píng)分表班級(jí)?計(jì)科一班姓名陳志杰?指導(dǎo)教師李素若?題目：克魯斯卡爾算法求最小生成樹評(píng)分標(biāo)準(zhǔn)評(píng)分標(biāo)準(zhǔn)分?jǐn)?shù)權(quán)重評(píng)分的依據(jù)得分AC選題10選題符合大綱

3、要求，題目較新穎，工作量大選題基本符合大綱要求，工作量適中?工作態(tài)度10態(tài)度端正，能主動(dòng)認(rèn)真完成各個(gè)環(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ù)庫(kù)及相關(guān)軟件的設(shè)計(jì)與調(diào)試工作，程序結(jié)構(gòu)合理，邏輯嚴(yán)謹(jǐn)，功能完善。有一定的分析、解決問題能力。能夠在老師指導(dǎo)下完成軟件的設(shè)計(jì)與調(diào)試工作，程序功能較完善。?答辨問題回答20能準(zhǔn)確回答老師提出的問題能基本準(zhǔn)確回答老

4、師提出的問題?程序運(yùn)行情況10程序運(yùn)行正確、界面清晰，測(cè)試數(shù)據(jù)設(shè)計(jì)合理。程序運(yùn)行正確、界面較清晰，能給出合適的測(cè)試數(shù)據(jù)。?課程設(shè)計(jì)論文20格式規(guī)范，層次清晰，設(shè)計(jì)思想明確，解決問題方法合理，體會(huì)深刻。格式較規(guī)范，設(shè)計(jì)思想基本明確，解決問題方法較合理。?總分?指導(dǎo)教師（簽字）：注：介于A和C之間為B級(jí)，低于C為D級(jí)和E級(jí)。按各項(xiàng)指標(biāo)打分后，總分在90～100為優(yōu)，80～89為良，70～79為中，60～69為及格，60分以下為不及格。目錄1需求分析11.1系統(tǒng)目標(biāo)11.2主體功能11.3開發(fā)環(huán)境12概要設(shè)計(jì)12.1功能模塊劃分12.2系統(tǒng)流程圖23詳細(xì)設(shè)計(jì)33.1數(shù)據(jù)結(jié)構(gòu)33

5、.2模塊設(shè)計(jì)34測(cè)試34.1測(cè)試數(shù)據(jù)34.2測(cè)試分析45總結(jié)與體會(huì)65.1總結(jié)：65.2體會(huì)：6參考文獻(xiàn)7附錄全部代碼81需求分析1.1系統(tǒng)目標(biāo)Kruskal算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。其基本思想是：首先選取全部的n個(gè)頂點(diǎn)，將其看成n個(gè)連通分量；然后按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷的選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依照生成樹的概念，n個(gè)結(jié)點(diǎn)的生成樹有n-1條邊，故反復(fù)上述過程，直到選取了n-1條邊為止，就構(gòu)成了一棵最小生成樹。1.2主體功能在城市規(guī)劃設(shè)計(jì)中，假設(shè)有n個(gè)城市之間建立通信網(wǎng)，則連通n個(gè)城市只需n-1條線路。這里自然考慮怎

6、樣建立這n-1條路是總費(fèi)用最省。把這n個(gè)城市抽象成一個(gè)連通網(wǎng)，網(wǎng)的頂點(diǎn)表示各個(gè)城市，頂點(diǎn)與頂點(diǎn)之間的邊表示通信線路，各個(gè)城市之間的通訊線路看作邊，相應(yīng)的建設(shè)花費(fèi)作為邊的權(quán)，這樣就構(gòu)成了一個(gè)網(wǎng)絡(luò)。由于在n個(gè)城市之間，可行線路有(n*(n-1))/2條，那么，如果選擇其中的n-1條線路(邊)在n個(gè)城市間建成全都能相互通訊的網(wǎng)，并且總的建設(shè)花費(fèi)為最??？這就是求該網(wǎng)絡(luò)的最小生成樹問題。本程序的目的是要建立一棵生成樹使總費(fèi)用最少。?1.3開發(fā)環(huán)境裝有Windows7操作系統(tǒng)的PC機(jī)vc++6.0，奔騰41.0GHz以上的處理器，編寫的程序需要在32MB的內(nèi)存中運(yùn)行。推薦在以下基本配

7、置電腦中運(yùn)行：CPUIntelMMX233MHz內(nèi)存：64MB硬盤空間：1.5GB顯卡：4MB顯存以上的PCI、AGP顯卡聲卡：最新的PCI聲卡CD-ROM：8x以上CD-ROM2概要設(shè)計(jì)2.1功能模塊劃分運(yùn)行程序后，程序在內(nèi)存中申請(qǐng)圖g的鄰接矩陣表示空間，存放作為用整型數(shù)組表示的頂點(diǎn)、邊、權(quán)值的數(shù)據(jù)。程序運(yùn)行過程中調(diào)用存放在存放在ESP寄存器中的數(shù)據(jù)，寄存器中存放著數(shù)據(jù)、地址和函數(shù)傳遞的中間結(jié)果。Kruskal算法在調(diào)用寄存器中的整型數(shù)據(jù)，對(duì)邊上的權(quán)值進(jìn)行冒泡排序，將權(quán)值小的邊放在數(shù)組的上面，然后在進(jìn)行一次循環(huán)打印，循環(huán)過程