圖論最小生成樹在城市交通建設(shè)中的應(yīng)用畢業(yè)論文

圖論最小生成樹在城市交通建設(shè)中的應(yīng)用畢業(yè)論文文檔視界圖論最小生成樹在城市交通建設(shè)中的應(yīng)用畢業(yè)論文圖論最小生成樹在城市交通建設(shè)中的應(yīng)用畢業(yè)論文畢業(yè)設(shè)計(jì)〔論文〕原創(chuàng)性聲明和使用受權(quán)講明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)〔論文〕，是我個人在指導(dǎo)老師的指導(dǎo)下進(jìn)行的研究工作及獲得的成果。盡我所知，除文中十分加以標(biāo)注和致謝的地方外，不包含其別人或組織已經(jīng)發(fā)表或公布過的研究成果，也不包含我為獲得及其它教育機(jī)構(gòu)的學(xué)位或?qū)W歷而使用過的材料。對本研究提供過幫助和做出過奉獻(xiàn)的個人或集體，均已在文中作了明確的講明并表示了謝意。作者簽名：日期：指導(dǎo)老師簽名：日期：使用受權(quán)講明本人完全了解大學(xué)關(guān)于采集、保存、使用畢業(yè)設(shè)計(jì)〔論文〕的規(guī)定，即：根據(jù)學(xué)校要求提交畢業(yè)設(shè)計(jì)〔論文〕的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)〔論文〕的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)校能夠采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)校能夠公布論文的部分或全部內(nèi)容。作者簽名：日期：目錄摘要.......................................................................................................................I緒論.(1)2有關(guān)最小生成樹的概念(2)3prim算法介紹(3)4系統(tǒng)設(shè)計(jì)及其應(yīng)用(5)一、系統(tǒng)設(shè)計(jì)(5)二、最小生成樹應(yīng)用(6)5總結(jié)(9)參考文獻(xiàn)(10)附件：(11)最小生成樹在城市交通建設(shè)中的應(yīng)用摘要連通圖廣泛應(yīng)用于交通建設(shè)，求連通圖的最小生成樹是最主要的應(yīng)用。比方要在n個城市間建立通信聯(lián)絡(luò)網(wǎng)，要考慮的是怎樣保證n點(diǎn)連通的前提下最節(jié)省經(jīng)費(fèi)，就應(yīng)用到了最小生成樹。求圖的最小生成樹有兩種算法，一種是Prim〔普里姆〕算法，另一種是Kruskal〔克魯斯卡爾〕算法。本文通過將城市各地點(diǎn)轉(zhuǎn)換成連通圖，再將連通圖轉(zhuǎn)換成鄰接矩陣。在MicrosoftVisualC++上，通過輸入結(jié)點(diǎn)和權(quán)值，用普里姆算法獲得權(quán)值最小邊來得到最小生成樹，進(jìn)而在保證各個地點(diǎn)之間能連通的情況下節(jié)省所需費(fèi)用。本文從分析課題的題目背景、題目意義、題目要求等出發(fā)，分別從需求分析、總體設(shè)計(jì)、具體設(shè)計(jì)、測試等各個方面具體介紹了系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)經(jīng)過，最后對系統(tǒng)的完成情況進(jìn)行了總結(jié)。關(guān)鍵字：PRIM算法、最小生成樹、鄰接矩陣、交通建設(shè)緒論中國國際工程咨詢公司交通業(yè)務(wù)部主任周曉勤指出，“以前的各專業(yè)規(guī)劃主要是根據(jù)本行業(yè)交通發(fā)展的需求進(jìn)行研究和規(guī)劃的，在交通設(shè)施總量缺乏、基本網(wǎng)不完善的時候，相互之間的矛盾并不突出。但隨著多種運(yùn)輸方式設(shè)施建設(shè)的快速發(fā)展，各行業(yè)交通網(wǎng)絡(luò)的逐步完善，多種運(yùn)輸方式網(wǎng)絡(luò)之間的疊加，難免顯現(xiàn)出各種運(yùn)輸方式在通道和樞紐銜接上的不協(xié)調(diào)。其結(jié)果是，資源浪費(fèi)，效率低下，使用不便利。而綜合交通網(wǎng)發(fā)展規(guī)劃的公布有利于運(yùn)輸整體構(gòu)造的調(diào)整，資源節(jié)約和集約利用，對于交通運(yùn)輸業(yè)的可持續(xù)發(fā)展具有重要和深遠(yuǎn)的意義。〞在社會-義建設(shè)時期，各個城市建設(shè)問題尤其是交通建設(shè)尤為重要。在保證各個城市能相互連通的情況下，怎么保證建設(shè)公路，怎么建設(shè)最省錢是建設(shè)工程公司所需考慮的重大情況。進(jìn)而能節(jié)省更多的錢來投資其他地方建設(shè)，如農(nóng)村交通建設(shè)。各個農(nóng)村交通建設(shè)好之后，則可再根據(jù)將農(nóng)村作為一個結(jié)點(diǎn)和其它農(nóng)村再次運(yùn)用最小生成樹。最小生成樹則能有效的解決此問題。例如，以盡可能低的總價建設(shè)若干條高速公路，把n個城市聯(lián)絡(luò)在一起。普里姆算法通過尋找無向圖中權(quán)值最小的邊，并且將其組合成最小生成樹，同時將最小生成樹以點(diǎn)集的形式輸出，便于觀察。根據(jù)課程設(shè)計(jì)任務(wù)書要求，本系統(tǒng)開發(fā)主要完成下面功能和性能。(1)輸入無向圖的方式要盡量簡單方便。(2)要能夠形象方便的觀察無向圖的構(gòu)造。(3)要能夠形象地演示PRIM算法求最小生成樹的經(jīng)過。本文第二章主要介紹圖和最小生成樹、鄰接矩陣等概念。第三章主要介紹prim算法。第四章進(jìn)行系統(tǒng)設(shè)計(jì)與調(diào)試及其在交通建設(shè)中的應(yīng)用。2有關(guān)最小生成樹的概念最小生成樹：連通加權(quán)圖里權(quán)和最小的生成樹稱為最小生成樹。從最小生成樹定義看主要先了解圖、樹及生成樹。本文中最小生成樹在計(jì)算機(jī)中存儲方法是應(yīng)用鄰接矩陣的形式存儲。故也應(yīng)了解鄰接矩陣的定義。定義一〔圖〕：圖是有一個非空的頂點(diǎn)集合和一個描繪頂點(diǎn)之間的關(guān)系即邊的集合組成。它能夠形式化的定義為：G=(V,E)V={iV|jVVertexType}E={|iV,jV∈V∧P(iV,jV)}其中，G表示一個圖，V是圖G中頂點(diǎn)的集合，E是V中頂點(diǎn)偶對的有限集，這些頂點(diǎn)偶對稱為邊，VertexType是用于描繪頂點(diǎn)類型，集合E中P(iV,jV)的含義是：對有向圖來講用“〞表示，對無向圖來講用“〔〕〞表示，即從iV到j(luò)V兩個頂點(diǎn)之間存在邊。定義二〔樹〕：樹包含n〔n>=0〕個節(jié)點(diǎn)。當(dāng)n=0時表示為空樹。其定義如下：T=(D,R)其中，D為樹中節(jié)點(diǎn)的有限集合，關(guān)系R知足一下條件：1〕有且僅有一個節(jié)點(diǎn)k0屬于D，它對于關(guān)系R來講沒有前趨節(jié)點(diǎn)，結(jié)點(diǎn)k0稱作樹的根結(jié)點(diǎn)。2〕除根結(jié)點(diǎn)k0之外，D中的每個結(jié)點(diǎn)僅有一個前趨結(jié)點(diǎn)，但能夠有過個后繼結(jié)點(diǎn)。3〕D中能夠有多個終端結(jié)點(diǎn)。即除根結(jié)點(diǎn)無父結(jié)點(diǎn)，其余各結(jié)點(diǎn)都有一個父結(jié)點(diǎn)和n〔n>=0〕個子結(jié)點(diǎn)。圖的矩陣表示，本文中只用到了鄰接矩陣，故在這只提出鄰接矩陣的定義，及其圖在鄰接矩陣中的表示。設(shè)圖A=(V,E)是一個有n個頂點(diǎn)的圖,圖的鄰接矩陣是一個二維數(shù)組A.edge[n][n]，用來存放頂點(diǎn)的信息和邊或弧的信息。定義三〔鄰接矩陣〔AdjacencyMatrix〕〕：是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個圖，其中V={v1,v2,…,vn}。G的鄰接矩陣是一個具有下列性質(zhì)的n階方陣：〔本文主要為無向圖的鄰接矩陣〕〔1〕無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的?！?〕無向圖的鄰接矩陣中第i行第j列表示i結(jié)點(diǎn)到j(luò)結(jié)點(diǎn)的度即權(quán)值，能夠表示為某一詳細(xì)應(yīng)用的數(shù)據(jù)。也表示i結(jié)點(diǎn)能否與j結(jié)點(diǎn)連通。定義四〔生成樹〕：假如T是G的一個生成子圖又是一棵樹，則稱T是圖G的一棵生成樹。3prim算法介紹最小生成樹的兩個著名算法：prim算法[和克魯斯卡爾算法[2],本文應(yīng)用的是prim算法。則克魯斯卡爾算法則不進(jìn)行描繪了。Prim算法的基本思想：首先，選擇帶最小的邊，把它放進(jìn)生成樹里，相繼添加帶權(quán)最小的邊，這些邊與已在樹立的頂點(diǎn)相關(guān)聯(lián)，并且不與已在數(shù)理的邊構(gòu)成圈，當(dāng)已經(jīng)添加了n-1條邊為止。PRIM算法介紹：設(shè)圖中頂點(diǎn)的全集為V,U中存放已選中過的點(diǎn),用數(shù)據(jù)構(gòu)造closedge[]存放選擇需要的數(shù)據(jù),先把下標(biāo)0對應(yīng)點(diǎn)放入U中,closedge[i].uxiabiao=0,(由于U中只要下標(biāo)0這一個點(diǎn)),closedge[i].lowcost中存放其他點(diǎn)到下標(biāo)為0的點(diǎn)的權(quán),closedge[0].lowcost=0;表示下標(biāo)為0的點(diǎn)已在U中了。在closedge按順序找到最先不在U中,且與U中點(diǎn)直接相連的點(diǎn),把此邊的權(quán)賦給min，用擂臺式比擬法選出closedge[j].lowcost中最小的,此時min中存放的是最小值所在下標(biāo),也就是下一個要放入U中的點(diǎn)的下標(biāo)。輸出選中的這條邊，它是最小生成樹中的一條邊。由于U中又參加了一個點(diǎn)，所以要修改closedge[i].lowcost的值，比擬新選中點(diǎn)與V-U中點(diǎn)的權(quán)和原來的closedge[i].lowcost,取小的那個存入。然后繼續(xù)如上的選擇,循環(huán)vexnum-1次,就選出了最小生成樹中的vexnum-1條邊。本程序采用數(shù)組存儲構(gòu)造進(jìn)行存儲，把第一個點(diǎn)所到的邊記錄下來，然后把權(quán)值最小的邊存入數(shù)組，同時將剛剛所存邊的的終點(diǎn)作為起點(diǎn)再次記錄該點(diǎn)所到的邊，并記錄權(quán)值最小的邊存入數(shù)組，這個經(jīng)過中，已經(jīng)被訪問的點(diǎn)不再訪問。知道最后所有的權(quán)值最小的邊全部輸出。這就是PRIM算法求最小生成樹。Prim算法有兩種形式，其偽代碼如下：算法一：procedurePrim;beginT:=Φ；U:={1};whileUVdobegin(u,v):=u∈U且v∈V-U的最小權(quán)邊;T:=T∪{(u,v)};U:=U∪{v};end;end;改良的prim算法2如下：procedurePrim(varG:adj_matrix;size:integer);{G為圖，size為圖的節(jié)點(diǎn)數(shù)目;注意：假設(shè)輸入的圖是連通圖}varlowcost:array[1..maxsize]ofinteger;used:array[1..maxsize]ofboolean;closeset:array[1..maxsize]ofinteger;i,j,k,min:integer;beginfori:=2tosizedo{初始化，此時U只含有頂點(diǎn)1}beginlowcost[i]:=G[1,i];closeset[i]:=1;used[i]:=false;end;used[1]:=true;fori:=2tosizedobeginmin:=maxint;j:=i;fork:=2tosizedo{用選擇法尋找頂點(diǎn)分別在V-U與U中權(quán)最小的邊}if(notused[k])and(lowcost[k]beginmin:=lowcost[k];j:=k;end;writeln(fout,'(',closeset[j],',',j,')');{輸出找到的最小生成樹的一條邊，此處可根據(jù)情況修改}used[j]:=true;{將j填加到U}fork:=2tosizedo{調(diào)整lowcost和closeset}if(notused[k])and(G[j,k]beginlowcost[k]:=G[j,k];closeset[k]:=j;end;end;end;4系統(tǒng)設(shè)計(jì)及其應(yīng)用一、系統(tǒng)設(shè)計(jì)數(shù)據(jù)信息以構(gòu)造體【3】【4】和數(shù)組形式儲存，結(jié)點(diǎn)的信息構(gòu)造體定義如下：structgraph{chartnode;charhnode;doublequanzhi;}gr[100];charnode[50]="";圖的存儲構(gòu)造為：#defineINFINITYINT_MAX//最大值#defineMAX_VERTEX_NUM20//最多的頂點(diǎn)個數(shù)typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向圖、有向網(wǎng)、無向圖、無向網(wǎng)}typedefstructArcCell{VRTypeadj;//頂點(diǎn)關(guān)系類型：圖：0、1網(wǎng)：權(quán)值InfoType*info;//該弧相關(guān)信息指針}ArcCell,AdjMaTrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)向量AdjMaxtrixarcs;//鄰接矩陣intvexnum,arcnum;//頂點(diǎn)數(shù)和弧或邊數(shù)GraphKindkind;//圖的種類標(biāo)志}Mgraph;Prim算法：voidprim(mgraphg,intk,i