數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-- KRUSKAL算法實現(xiàn).doc

河南工程學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計成果報告KRUSKAL算法實現(xiàn)學(xué)生學(xué)號： 學(xué)生姓名： 學(xué) 院： 計算機(jī)學(xué)院 專業(yè)班級： 軟件工程1341 專業(yè)課程： 數(shù)據(jù)結(jié)構(gòu)與算法 指導(dǎo)教師： 2014 年 12 月 29 日題 目KRUSKAL算法實現(xiàn)考核項目考核內(nèi)容得分平時考核（30分）出勤情況、態(tài)度、效率；知識掌握情況、基本操作技能、知識應(yīng)用能力、獲取知識能力系統(tǒng)設(shè)計（20分）分析系統(tǒng)的功能模塊編程調(diào)試（20分）實現(xiàn)系統(tǒng)的各個功能模塊，并完成調(diào)試回答問題（15分）回答老師針對課程設(shè)計提出的問題課程設(shè)計報告撰寫（10分）嚴(yán)格按照規(guī)范要求完成課程設(shè)計報告源代碼（5分）按照規(guī)范要求完成課程設(shè)計源代碼的排版總 評 成 績指導(dǎo)教師評語： 日期： 年 月 日目 錄1 課程設(shè)計目標(biāo)11.1 課程設(shè)計目標(biāo)11.2 課程設(shè)計任務(wù)12 分析與設(shè)計22.1 題目需求分析22.2 存儲結(jié)構(gòu)設(shè)計22.3 算法描述22.4 程序流程圖23 程序清單34 測試44.1 測試數(shù)據(jù)44.2 測試結(jié)果分析45 總結(jié)5參考文獻(xiàn)7附 錄81 課程設(shè)計目標(biāo)與任務(wù)1.1 課程設(shè)計目標(biāo)通過本課程設(shè)計，使學(xué)生在數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計與實現(xiàn)方面得到訓(xùn)練，加深對數(shù)據(jù)結(jié)構(gòu)基本內(nèi)容的理解和靈活應(yīng)用，同時，在程序設(shè)計方法及上機(jī)操作方面受到比較系統(tǒng)嚴(yán)格的訓(xùn)練，培養(yǎng)軟件工作所需要的動手能力。（1）能根據(jù)實際問題的具體情況結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲結(jié)構(gòu)，并能設(shè)計出解決問題的有效算法；（2）通過上機(jī)實習(xí),驗證自己設(shè)計的算法的正確性，學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改；（3）培養(yǎng)算法分析能力，分析所設(shè)計算法的時間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計水平；（4）盡可能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復(fù)雜的運行過程以動態(tài)方式顯示出來，獲得算法的直觀感受。1.2 課程設(shè)計任務(wù)根據(jù)提供的實習(xí)題目，認(rèn)真完成軟件設(shè)計的全部過程，并以最終軟件設(shè)計成果來證明其獨立完成實際任務(wù)的能力，從而，反映出理解和運用數(shù)據(jù)結(jié)構(gòu)與算法的水平和能力，最后完成軟件設(shè)計和程序調(diào)試并提交文檔：課程設(shè)計報告書，報告書中包含設(shè)計的算法及部分程序代碼。2 分析與設(shè)計2.1 題目需求分析要求：（1）對給定的圖結(jié)構(gòu)，用KRUSKAL算法基本思想求解出所有最小生成樹；（2）最好能借助語言環(huán)境實現(xiàn)圖形顯示功能，以便將抽象的數(shù)據(jù)結(jié)構(gòu)以圖形方式顯示出來，將復(fù)雜的運行過程以動態(tài)方式顯示出來；（3）給出若干例程，演示通過調(diào)用自己所縮寫程序來實現(xiàn)相關(guān)問題的求解。分析：Dijkstra算法即解決單源最短路徑問題，單源最短路徑問題，即在圖中求出給定頂點到其它任一頂點的最短路徑。在弄清楚如何求算單源最短路徑問題之前，必須弄清楚最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)。如果P(i,j)=Vi.Vk.Vs.Vj是從頂點i到j(luò)的最短路徑，k和s是這條路徑上的一個中間頂點，那么P(k,s)必定是從k到s的最短路徑。2.2 存儲結(jié)構(gòu)設(shè)計 Dijkstra算法中使用較為普遍的堆數(shù)據(jù)結(jié)構(gòu)有二叉堆、二項堆和Fibonacci堆。其中二叉堆在內(nèi)存中被存儲為經(jīng)過特殊排列的完全二叉樹。二叉堆具有以下操作特性： 1）其獲取最小節(jié)點的操作Get_Min時間復(fù)雜度為(1)O，總計算機(jī)指令一條； 2) 將一個新的元素插入堆中的操作Insert時間復(fù)雜度為(log)On，總指令最壞情況下要3*log1n+條； 其插入操作可以通過以下三步來執(zhí)行： 將新元素插入到堆的末尾，計算機(jī)指令一條； 將新元素與其父節(jié)點比較，如果新元素比其父節(jié)點小則交換它與其父節(jié)點，計算機(jī)指令三條； 重復(fù)執(zhí)行第二步直到新元素被提升到樹根或不比其父節(jié)點小。 3）其從堆中去除最小節(jié)點的操作Extract_Min操作時間復(fù)雜度為(log)On，最壞情況下需要3*log2n+條指令； 根據(jù)二叉堆的特點，為了實現(xiàn)剔除最小節(jié)點的操作，只需要進(jìn)行以下四步操作： 將其根節(jié)點從樹中剔除，一條指令； 將樹中的最后一個子孫節(jié)點放在樹根位置，一條指令； 將新的樹根與其子節(jié)點依次比較，如果大于其子節(jié)點就于該子節(jié)點交換，三條； 重復(fù)執(zhí)行第三步，直到新根元素被交換到底或不比其任何一個子節(jié)點大。 4）降低堆中某一元素值的同時也要對該元素進(jìn)行重新定位排序。由于是小頂堆，所以需要將被降低值的元素執(zhí)行向根節(jié)點方向的比較操作，因此其時間復(fù)雜度最壞情況下也為(log)On，最壞需要3*logn條指令。 Fibonacci堆和二項堆的原理十分相似，且Fibonacci堆是緣于二項堆的靈感而創(chuàng)建的，但在時間復(fù)雜度上又優(yōu)于二項堆，因此我們這里只討論Fibonacci堆。Fibonacci堆是Fredman和Tarjan 于1984年發(fā)明的，它是對優(yōu)先隊列一個很好的實現(xiàn)3。它的目的是在計算最小生成樹根最短路徑的過程中將操作步數(shù)最小化。因此我們感興趣的操作有插入，減小鍵值，合并和刪除最小鍵值節(jié)點(合并操作的重要性將在我們敘述Fibonacci堆操作的過程中闡述)。而Fibonacci堆通過一種“懶惰”行為來實現(xiàn)這一目的，即“在不得不做的時候再做”，這樣會使以后的工作更加簡單。 Fibonacci堆H是一些堆排序樹的集合，它具有以下幾個特點： 1）這些樹的根用一個雙向鏈表存儲起來(成為H的根表)； 2）每棵樹的根節(jié)點為樹中權(quán)值最小的節(jié)點(遵循了堆排序樹的特點)； 3）我們通過一個指向全局最小的樹根來訪問堆； 4）對于每個節(jié)點x，我們儲存x的階(也稱為度數(shù))，它代表了節(jié)點x的孩子節(jié)點數(shù)目；另外還有一個mark，是一個布爾值。 5）對于每個節(jié)點，我們最多有四個指針分別指向該節(jié)點的父節(jié)點，其中的一個子節(jié)點，和一左一右兩個兄弟節(jié)點，兄弟節(jié)點之間通過一個雙向循環(huán)鏈表連接起來。 Fibonacci堆具以下7個常用操作： 1）合并樹：設(shè)x和y分別是堆上兩棵樹的根節(jié)點，由于堆的性質(zhì)：樹的根節(jié)點值最小，所以只需要比較x和y的值，如果xy則將x作為y的一棵子樹，由此可知該操作的時間復(fù)雜度為(1)O； 2）插入新元素：將欲插入元素x作為一棵根樹直接插入到堆的根表中，并與根表中原最小的根比較確定最小根，由此可知其時間復(fù)雜度也為(1)O； 3）剪枝操作：若x不是一棵樹的根節(jié)點，將x作為根的子樹從其父節(jié)點剪下放到根表中，并與原根表比較確定新的最小根，時間復(fù)雜度為(1)O； 4）減小節(jié)點值操作：欲減小x節(jié)點的值只需要將x進(jìn)行剪枝后更新x的值，時間復(fù)雜度為(1)O； 5）刪除最小的節(jié)點：我們知道根表中保存了最小節(jié)點的指針，因此只需將最小根樹的根節(jié)點刪除，并將其子樹放到根表中，并搜索整個根表確定新的最小根，時間復(fù)雜度為Om，其中m是根表中根的個數(shù)； 6）標(biāo)記節(jié)點：當(dāng)且僅當(dāng)節(jié)點x不是根且失去了一個孩子的時候我們標(biāo)記x的mark為真，當(dāng)x變?yōu)楦鶗r去除標(biāo)記；當(dāng)節(jié)點x被標(biāo)記時不能失去另一個孩子； 7）合并相同度數(shù)的節(jié)點：為了確保每個節(jié)點的后代數(shù)目不會過多，我們需要對具有相同度數(shù)的根節(jié)點進(jìn)行合并樹操作，并且該操作在插入、剪枝和刪除最小節(jié)點操作后一定會進(jìn)行； 通過對兩種數(shù)據(jù)結(jié)構(gòu)的詳細(xì)探討我們可以看出：雖然Fibonacci堆在插入和減小節(jié)點值操作上的直接時間復(fù)雜度要優(yōu)于二叉堆，但是Fibonacci堆為了實現(xiàn)其“懶惰”的目的進(jìn)行了很多步小開銷的操作來復(fù)雜化數(shù)據(jù)結(jié)構(gòu)。這增大了刪除最小節(jié)點的時間復(fù)雜度（因為其不但要進(jìn)行基本的操作，之后還必須跟隨合并和標(biāo)記操作），并且顯然Fibonacci堆的計算機(jī)指令要遠(yuǎn)遠(yuǎn)多于二叉堆。經(jīng)研究在GIS等的交通網(wǎng)絡(luò)等稀疏圖中Fibonacci堆并不能發(fā)揮其優(yōu)越性。 配對堆的思想來源于Fibonacci堆，但卻比Fibonacci堆要簡單，性能也稍有改進(jìn)。配對堆數(shù)據(jù)結(jié)構(gòu)除了具有根節(jié)點是最小原素的基本堆性質(zhì)外還具有如下性質(zhì)： 1）每個堆節(jié)點除了保存基本元素外，還保存了三個指針，分別指向該節(jié)點的前驅(qū)節(jié)點、左兒子節(jié)點和右兄弟節(jié)點； 2）如果節(jié)點n是某個節(jié)點的最左兒子，則其前驅(qū)節(jié)點指針指向其父節(jié)點，否則應(yīng)指向其左兄弟節(jié)點； 3）任何一個節(jié)點的值均小于等于其最左兒子節(jié)點； 4）同一層次串聯(lián)的兄弟節(jié)點沒有大小順序，但均大于其最左兄弟節(jié)點的父節(jié)點。 配對堆主要有4種基本操作： 1）合并子堆：設(shè)X與Y分別是兩個子配對堆的根節(jié)點，如果XY則令X堆成為Y的最左子堆，反之則令Y成為X的最左子堆，時間復(fù)雜度()1O，需要五條計算機(jī)指令（對比、修改X的最左兒子指針、修改Y的前驅(qū)和右兄弟指針、修改Y右兄弟的前驅(qū)指針）； 2）插入節(jié)點：首先令插入的節(jié)點為一個單節(jié)點子堆，然后將其與欲插入堆進(jìn)行合并操作，時間復(fù)雜度()1O，需要五條計算機(jī)指令； 3）降低節(jié)點值：首先將欲降低的節(jié)點及其子孫從堆中剔除，降低元素的值，然后將降低根節(jié)點值后的堆與原堆進(jìn)行合并操作，時間復(fù)雜度(1)O，需要10條指令； 4）刪除最小節(jié)點：將堆的根節(jié)點刪除，然后將剩余的根的直接子節(jié)點作為根，分成M個子堆，然后所有的子堆合并在一起。該操作的時間復(fù)雜度為()Om，需要27*m+條指令。 通過以上分析我們可以得出兩個結(jié)論： 1）堆數(shù)據(jù)結(jié)構(gòu)是比較適合Dijkstra算法操作特點的數(shù)據(jù)存儲解決方案； 2）從時間復(fù)雜度上直觀的看，配對堆要優(yōu)于二叉堆； 3）在計算實現(xiàn)過程中，配對堆需要7*12m+條計算機(jī)指令（m是根的直接兒子節(jié)點數(shù)）而二叉堆一次運行需要9*log4n+條指令（n是節(jié)點總數(shù)）。 4) 無論是二叉堆還是配對堆，對于在堆中查找搜索已知節(jié)點都沒有很好的解決，只能使用遍歷搜索。2.3 算法描述如果存在一條從i到j(luò)的最短路徑(Vi.Vk,Vj)，Vk是Vj前面的一頂點。那么(Vi.Vk)也必定是從i到k的最短路徑。為了求出最短路徑，Dijkstra就提出了以最短路徑長度遞增，逐次生成最短路徑的算法。譬如對于源頂點V0，首先選擇其直接相鄰的頂點中長度最短的頂點Vi，那么當(dāng)前已知可得從V0到達(dá)Vj頂點的最短距離distj=mindistj,disti+matrixij。根據(jù)這種思路，假設(shè)存在G=，源頂點為V0，U=V0,disti記錄V0到i的最短距離，pathi記錄從V0到i路徑上的i前面的一個頂點。1.從V-U中選擇使disti值最小的頂點i，將i加入到U中；2.更新與i直接相鄰頂點的dist值。(distj=mindistj,disti+matrixij)3.知道U=V，停止。2.4 程序流程圖 圖2.1 KRUSKAL算法流程圖3 程序清單*Dijkstra求單源最短路徑 2010.8.26*/ #include #include#define M 100#define N 100using namespace std;typedef struct node int matrixNM; /鄰接矩陣 int n; /頂點數(shù) int e; /邊數(shù) MGraph; void DijkstraPath(MGraph g,int *dist,int *path,int v0) /v0表示源頂點 int i,j,k; bool *visited=(bool *)malloc(sizeof(bool)*g.n); for(i=0;i0&i!=v0) disti=g.matrixv0i; pathi=v0; /path記錄最短路徑上從v0到i的前一個頂點 else disti=INT_MAX; /若i不與v0直接相鄰，則權(quán)值置為無窮大 pathi=-1; visitedi=false; pathv0=v0; distv0=0; visitedv0=true; for(i=1;ig.n;i+) /循環(huán)擴(kuò)展n-1次 int min=INT_MAX; int u; for(j=0;jg.n;j+) /尋找未被擴(kuò)展的權(quán)值最小的頂點 if(visitedj=false&distjmin) min=distj; u=j; visitedu=true; for(k=0;k0&min+g.matrixukdistk) distk=min+g.matrixuk; pathk=u; void showPath(int *path,int v,int v0) /打印最短路徑上的各個頂點 stack s; int u=v; while(v!=v0) s.push(v); v=pathv; s.push(v); while(!s.empty() couts.top()ne&e!=0) int i,j; int s,t,w; /表示存在一條邊s-t,權(quán)值為w MGraph g; int v0; int *dist=(int *)malloc(sizeof(int)*n); int *path=(int *)malloc(sizeof(int)*n); for(i=0;iN;i+) for(j=0;jM;j+) g.matrixij=0; g.n=n; g.e=e; for(i=0;istw; g.matrixst=w; cinv0; /輸入源頂點 DijkstraPath(g,dist,path,v0); for(i=0;in;i+) if(i!=v0) showPath(path,i,v0); coutdistiendl; return 0;4 測試4.1 測試數(shù)據(jù)測試數(shù)據(jù)：