資源描述：
《最小生成樹問題.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
