資源描述:
《最小生成樹問題.doc》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、榆林學(xué)院12屆課程設(shè)計(jì)《最小生成樹問題》課程設(shè)計(jì)說明書學(xué)生姓名:趙佳學(xué)號(hào):1412210112院系:信息工程學(xué)院專業(yè):計(jì)算機(jī)科學(xué)與技術(shù)班級(jí):計(jì)14本1指導(dǎo)教師:答辯時(shí)間:年月日最小生成樹問題一、問題陳述最小生成樹問題設(shè)計(jì)要求:在n個(gè)城市之間建設(shè)網(wǎng)絡(luò),只需保證連通即可,求最經(jīng)濟(jì)的架設(shè)方法。存儲(chǔ)結(jié)構(gòu)采用多種。求解算法多種。二、需求分析1.在n個(gè)城市之間建設(shè)網(wǎng)絡(luò),只需保證連通即可。2.求城市之間最經(jīng)濟(jì)的架設(shè)方法。3.采用多種存儲(chǔ)結(jié)構(gòu),求解算法也采用多種。三、概要設(shè)計(jì)1、功能模塊圖開始創(chuàng)建一個(gè)圖功能選擇1.建立鄰接矩陣2.建立鄰接表3.kruskal算法4.PR
2、IM算法結(jié)束2、功能描述(1)CreateUDG()創(chuàng)建一個(gè)圖:通過給用戶信息提示,讓用戶將城市信息及城市之間的聯(lián)系關(guān)系和連接權(quán)值寫入程序,并根據(jù)寫入的數(shù)據(jù)創(chuàng)建成一個(gè)圖。(2)Switch()功能選擇:給用戶提示信息,讓用戶選擇相應(yīng)功能。(1)Adjacency_Matrix()建立鄰接矩陣:將用戶輸入的數(shù)據(jù)整理成鄰接矩陣并顯現(xiàn)在屏幕上。(2)Adjacency_List()建立鄰接表:將用戶輸入的數(shù)據(jù)整理成臨接表并顯現(xiàn)在屏幕上。(3)MiniSpanTree_KRSL()kruskal算法:利用kruskal算法求出圖的最小生成樹,即:城市之間最經(jīng)濟(jì)的
3、連接方案。(4)MiniSpanTree_PRIM()PRIM算法:利用PRIM算法求出圖的最小生成樹,即:城市之間最經(jīng)濟(jì)的連接方案。二、詳細(xì)設(shè)計(jì)本次課程設(shè)計(jì)采用兩種存儲(chǔ)結(jié)構(gòu)以及兩種求解算法。1、兩種存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)定義如下:typedefstructArcell{doubleadj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];//節(jié)點(diǎn)數(shù)組AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前
4、節(jié)點(diǎn)數(shù)和弧數(shù)}MGraph;typedefstructPnode//用于普利姆算法{charadjvex;//節(jié)點(diǎn)doublelowcost;//權(quán)值}Pnode,Closedge[MAX_VERTEX_NUM];//記錄頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義typedefstructKnode//用于克魯斯卡爾算法中存儲(chǔ)一條邊及其對(duì)應(yīng)的2個(gè)節(jié)點(diǎn){charch1;//節(jié)點(diǎn)1charch2;//節(jié)點(diǎn)2doublevalue;//權(quán)值}Knode,Dgevalue[MAX_VERTEX_NUM];2、求解算法采用Prim算法和Kruskal算法。(1)
5、普里姆算法(Prim)算法普里姆算法(Prim)算法是一種構(gòu)造性算法,生成最小生成樹的步驟如下:初始化U={v}。以v到其他頂點(diǎn)的所有邊為候選邊。重復(fù)一下步驟(n-1)次,使得其他(n-1)個(gè)頂點(diǎn)被加入到U中。從候選邊中挑選權(quán)值最小的邊加入TE,設(shè)該邊在V—U中的頂點(diǎn)是vk,將頂點(diǎn)vk加入到U中;考察當(dāng)前V—U中的所有頂點(diǎn)vj,修改候選邊:若(vk,vj)的權(quán)值小于原來和vj關(guān)聯(lián)的候選邊,則用(vk,vj)取代后者作為候選邊。開始標(biāo)志頂點(diǎn)1加入U(xiǎn)集合尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊形成n-1條邊的生成樹頂點(diǎn)k加入U(xiǎn)修改由頂點(diǎn)k到其他頂點(diǎn)邊
6、的權(quán)值結(jié)束得到最小生成樹(2)克魯斯卡爾(Kruskal)算法克魯斯卡爾(Kruskal)算法是一種按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹的方法。假設(shè)G=(V,E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)連通無向圖,T=(U,TE)是G的最小生成樹,則構(gòu)造最小生成樹的步驟如下:置U的初值等于V(即包含有G中的全部頂點(diǎn)),TE的初值為空集(即圖T中每一個(gè)頂點(diǎn)都構(gòu)成一個(gè)分量)。將圖G中的邊按權(quán)值從小到大的順序依次選取:若選取的邊未使生成樹T形成回路,則加入TE,否則舍棄,直到TE中包含(n-1)條邊為止。3、使用的函數(shù)intCreateUDG(MGraph&G,Dge
7、value&dgevalue);intLocateVex(MGraphG,charch);intMinimum(MGraphG,Closedgeclosedge);voidMiniSpanTree_PRIM(MGraphG,charu);voidSortdge(Dgevalue&dgevalue,MGraphG);voidAdjacency_Matrix(MGraphG);voidAdjacency_List(MGraphG,Dgevaluedgevalue);函數(shù)之間的調(diào)用關(guān)系圖:CreateUDG()main()Adjacency_Matrix()A
8、djacency_List()MiniSpanTree_KRSL()MiniSp