最小生成樹Kruskal算法.doc

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

1、...課程設(shè)計報告課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課程設(shè)計題目：最小生成樹Kruskal算法院（系）：專業(yè)：班級：學(xué)號：姓名：指導(dǎo)教師：.......目錄1課程設(shè)計介紹11.1課程設(shè)計容11.2課程設(shè)計要求12課程設(shè)計原理22.1課設(shè)題目粗略分析22.2原理圖介紹42.2.1功能模塊圖42.2.2流程圖分析53數(shù)據(jù)結(jié)構(gòu)分析113.1存儲結(jié)構(gòu)113.2算法描述114調(diào)試與分析134.1調(diào)試過程134.2程序執(zhí)行過程13參考文獻(xiàn)16附錄（關(guān)鍵部分程序清單）17.......1課程設(shè)計介紹1.1課程設(shè)計容編寫算法能夠建立帶權(quán)圖，并能夠用Kruskal算法求該圖的最小生成樹。最小生成樹能夠選擇圖上

2、的任意一點做根結(jié)點。最小生成樹輸出采用頂點集合和邊的集合的形式。1.2課程設(shè)計要求1.頂點信息用字符串，數(shù)據(jù)可自行設(shè)定。2.參考相應(yīng)的資料，獨立完成課程設(shè)計任務(wù)。3.交規(guī)課程設(shè)計報告和軟件代碼。.......2課程設(shè)計原理2.1課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。以下是三個模塊的大體分析：1.要確定圖的存儲形式，通過對題目要求的具體分析。發(fā)現(xiàn)該題的主要操作是路徑的輸出，因此采用邊集數(shù)組（每個元素是一個結(jié)構(gòu)體，包括起點、終點和權(quán)值）和鄰接矩陣比較方便以后的編程。2.Kruskal算法。該算法設(shè)置了集合A，該集合一直是某最小生成樹的子集。在每步?jīng)Q定是否把邊（u,v）添

3、加到集合A中，其添加條件是A∪{（u,v）}仍然是最小生成樹的子集。我們稱這樣的邊為A的安全邊，因為可以安全地把它添加到A中而不會破壞上述條件。3.Dijkstra算法。算法的基本思路是：假設(shè)每個點都有一對標(biāo)號（dj,pj）,其中d是從起源點到點j的最短路徑的長度（從頂點到其本身的最短路徑是零路（沒有弧的路），其長度等于零）；pj則是從s到j(luò)的最短路徑中j點的前一點。求解從起源點s到點j的最短路徑算法的基本過程如下：1）初始化。起源點設(shè)置為：①ds=0,ps為空；②所有其它點：di=∞,pi=？；③標(biāo)記起源點s，記k=s，其他所有點設(shè)為未標(biāo)記的。2）k到其直接連接的未標(biāo)記的點j的距離，并

4、設(shè)置：.......dj=min[dj,dk+lkj]式中，lkj是從點k到j(luò)的直接連接距離。1）選取下一個點。從所有未標(biāo)記的結(jié)點中，選取dj中最小的一個i：di=min[dj,所有未標(biāo)記的點j]點i就被選為最短路徑中的一點，并設(shè)為已標(biāo)記的。4）找到點i的前一點。從已標(biāo)記的點中找到直接連接到i的點j*，作為前一點，設(shè)置：i=j*5)標(biāo)記點i。如果所有點已標(biāo)記，則算法完全推出，否則，記k=i，轉(zhuǎn)到2）再繼續(xù)。而程序中求兩點間最短路徑算法。其主要步驟是：①調(diào)用dijkstra算法。②將path中的第“終點”元素向上回溯至起點，并顯示出來。.......2.2原理圖介紹2.2.1功能模塊圖開始

5、輸入頂點個數(shù)n輸入邊數(shù)e輸入邊集顯示菜單，進(jìn)行選擇。求兩點間最短距離求兩點間最短距離Kruskal算法結(jié)束圖2.1功能模塊圖.......2.2.2流程圖分析1.主函數(shù)開始輸入頂點個數(shù)n輸入邊數(shù)e輸入選項aa=1調(diào)用insertsort，kruskal函數(shù)a=2輸入v0調(diào)用dijkstra，printpath1函數(shù)a=3輸入v0,v1調(diào)用dijkstra，printpath2函數(shù)輸入a=4結(jié)束圖2.2主函數(shù)流程圖2.insertsort函數(shù).......開始inti,jfor(i=2;i<=e;i++)ge[i].w

6、ge[j].wge[j+1]=ge[j];j--;Yge[j+1]=ge[0];NY結(jié)束N1.圖2.3insertsort函數(shù)流程圖.......3．Kruskal函數(shù)開始intset[MAXE],v1,v2,i,j;for(i=1;i

7、圖.......4.dijkstra函數(shù)開始intu,vnum,w,wm;for(w=1;w<=n;w++){dist[w]=cost[v0][w];if(cost[v0][w]<32767)path[w]=v0;}vnum=1;vnum