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

1、最小生成樹(shù)在城市交通建設(shè)中的應(yīng)用姓 名 XX 學(xué) 號(hào) S 專 業(yè) 計(jì)算機(jī)應(yīng)用技術(shù) 2010年12月4目錄摘 要I緒論12 有關(guān)最小生成樹(shù)的概念23 prim算法介紹34 系統(tǒng)設(shè)計(jì)及其應(yīng)用5一、系統(tǒng)設(shè)計(jì)5二、最小生成樹(shù)應(yīng)用65 總結(jié)9參考文獻(xiàn)10附件：11最小生成樹(shù)在城市交通建設(shè)中的應(yīng)用摘 要連通圖廣泛應(yīng)用于交通建設(shè)，求連通圖的最小生成樹(shù)是最主要的應(yīng)用。比如要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，要考慮的是如何保證n點(diǎn)連通的前提下最節(jié)省經(jīng)費(fèi)，就應(yīng)用到了最小生成樹(shù)。求圖的最小生成樹(shù)有兩種算法，一種是Prim（普里姆）算法，另一種是Kruskal（克魯斯卡爾）算法。本文通過(guò)將城市各地點(diǎn)轉(zhuǎn)換成連通圖，再將連通圖

2、轉(zhuǎn)換成鄰接矩陣。在Microsoft Visual C+上，通過(guò)輸入結(jié)點(diǎn)和權(quán)值，用普里姆算法獲得權(quán)值最小邊來(lái)得到最小生成樹(shù)，從而在保證各個(gè)地點(diǎn)之間能連通的情況下節(jié)省所需費(fèi)用。本文從分析課題的題目背景、題目意義、題目要求等出發(fā)，分別從需求分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、測(cè)試等各個(gè)方面詳細(xì)介紹了系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過(guò)程，最后對(duì)系統(tǒng)的完成情況進(jìn)行了總結(jié)。關(guān)鍵字：PRIM算法、最小生成樹(shù)、鄰接矩陣、交通建設(shè)緒論中國(guó)國(guó)際工程咨詢公司交通業(yè)務(wù)部主任周曉勤指出，“以前的各專業(yè)規(guī)劃主要是按照本行業(yè)交通發(fā)展的需求進(jìn)行研究和規(guī)劃的，在交通設(shè)施總量不足、基本網(wǎng)不完善的時(shí)候，互相之間的矛盾并不突出。但隨著多種運(yùn)輸方式設(shè)施建設(shè)的

3、快速發(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)輸整體結(jié)構(gòu)的調(diào)整，資源節(jié)約和集約利用，對(duì)于交通運(yùn)輸業(yè)的可持續(xù)發(fā)展具有重要和深遠(yuǎn)的意義。”在社會(huì)主義建設(shè)時(shí)期，各個(gè)城市建設(shè)問(wèn)題尤其是交通建設(shè)尤為重要。在保證各個(gè)城市能互相連通的情況下，怎么保證建設(shè)公路，怎么建設(shè)最省錢是建設(shè)工程公司所需考慮的重大情況。從而能節(jié)省更多的錢來(lái)投資其他地方建設(shè)，如農(nóng)村交通建設(shè)。各個(gè)農(nóng)村交通建設(shè)好之后，則可再根據(jù)將農(nóng)村作為一個(gè)結(jié)點(diǎn)和其它農(nóng)村再次運(yùn)用最小生成樹(shù)。最小生成樹(shù)則能有效的解決此

4、問(wèn)題。例如，以盡可能低的總價(jià)建設(shè)若干條高速公路，把n個(gè)城市聯(lián)系在一起。普里姆算法通過(guò)尋找無(wú)向圖中權(quán)值最小的邊，并且將其組合成最小生成樹(shù)，同時(shí)將最小生成樹(shù)以點(diǎn)集的形式輸出，便于觀察。根據(jù)課程設(shè)計(jì)任務(wù)書(shū)要求，本系統(tǒng)開(kāi)發(fā)主要完成以下功能和性能。(1) 輸入無(wú)向圖的方式要盡量簡(jiǎn)單方便。(2) 要能夠形象方便的觀察無(wú)向圖的結(jié)構(gòu)。(3) 要能夠形象地演示PRIM算法求最小生成樹(shù)的過(guò)程。本文第二章主要介紹圖和最小生成樹(shù)、鄰接矩陣等概念。第三章主要介紹prim算法。第四章進(jìn)行系統(tǒng)設(shè)計(jì)與調(diào)試及其在交通建設(shè)中的應(yīng)用。2 有關(guān)最小生成樹(shù)的概念最小生成樹(shù)：連通加權(quán)圖里權(quán)和最小的生成樹(shù)稱為最小生成樹(shù)。從最小生成樹(shù)定義看

5、主要先了解圖、樹(shù)及生成樹(shù)。本文中最小生成樹(shù)在計(jì)算機(jī)中存儲(chǔ)方法是應(yīng)用鄰接矩陣的形式存儲(chǔ)。故也應(yīng)了解鄰接矩陣的定義。定義一（圖）：圖是有一個(gè)非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間的關(guān)系即邊的集合組成。它可以形式化的定義為：G=(V,E)V= | VertexTypeE=|,VP(,)其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是V中頂點(diǎn)偶對(duì)的有限集，這些頂點(diǎn)偶對(duì)稱為邊，VertexType是用于描述頂點(diǎn)類型，集合E中P(,)的含義是：對(duì)有向圖來(lái)說(shuō)用“”表示，對(duì)無(wú)向圖來(lái)說(shuō)用“（）”表示，即從到 兩個(gè)頂點(diǎn)之間存在邊。定義二（樹(shù)）：樹(shù)包含n（n=0）個(gè)節(jié)點(diǎn)。當(dāng)n=0時(shí)表示為空樹(shù)。其定義如下：T=(D,R)其中

6、，D為樹(shù)中節(jié)點(diǎn)的有限集合，關(guān)系R滿足一下條件：1） 有且僅有一個(gè)節(jié)點(diǎn)k0屬于D，它對(duì)于關(guān)系R來(lái)說(shuō)沒(méi)有前趨節(jié)點(diǎn)，結(jié)點(diǎn)k0稱作樹(shù)的根結(jié)點(diǎn)。2） 除根結(jié)點(diǎn)k0之外，D中的每個(gè)結(jié)點(diǎn)僅有一個(gè)前趨結(jié)點(diǎn)，但可以有過(guò)個(gè)后繼結(jié)點(diǎn)。3） D中可以有多個(gè)終端結(jié)點(diǎn)。即除根結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)，其余各結(jié)點(diǎn)都有一個(gè)父結(jié)點(diǎn)和n（n=0）個(gè)子結(jié)點(diǎn)。圖的矩陣表示，本文中只用到了鄰接矩陣，故在這只提出鄰接矩陣的定義，及其圖在鄰接矩陣中的表示。設(shè)圖 A = (V, E)是一個(gè)有 n 個(gè)頂點(diǎn)的圖, 圖的鄰接矩陣是一個(gè)二維數(shù)組 A.edgenn，用來(lái)存放頂點(diǎn)的信息和邊或弧的信息。定義三（鄰接矩陣（Adjacency Matrix）：是表示頂點(diǎn)

7、之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個(gè)圖，其中V=v1,v2,vn。G的鄰接矩陣是一個(gè)具有下列性質(zhì)的n階方陣：（本文主要為無(wú)向圖的鄰接矩陣）（1） 無(wú)向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。（1）無(wú)向圖的鄰接矩陣中第i行第j列表示i結(jié)點(diǎn)到j(luò)結(jié)點(diǎn)的度即權(quán)值，可以表示為某一具體應(yīng)用的數(shù)據(jù)。也表示i結(jié)點(diǎn)是否與j結(jié)點(diǎn)連通。定義四（生成樹(shù)）：如果T是G的一個(gè)生成子圖又是一棵樹(shù)，則稱T是圖G的一棵生成樹(shù)。3 prim算法介紹最小生成樹(shù)的兩個(gè)著名算法：prim算法和克魯斯卡爾算法2 ,本文應(yīng)用的是prim算法。則克魯斯卡爾算法則不進(jìn)行描述了。Prim算法的基本思想：首先，選擇帶最小的邊，

8、把它放進(jìn)生成樹(shù)里，相繼添加帶權(quán)最小的邊，這些邊與已在樹(shù)立的頂點(diǎn)相關(guān)聯(lián)，并且不與已在數(shù)理的邊形成圈，當(dāng)已經(jīng)添加了n-1條邊為止。PRIM算法介紹：設(shè)圖中頂點(diǎn)的全集為V, U中存放已選中過(guò)的點(diǎn),用數(shù)據(jù)結(jié)構(gòu)closedge存放選擇需要的數(shù)據(jù),先把下標(biāo)0對(duì)應(yīng)點(diǎn)放入U(xiǎn)中, closedgei.uxiabiao=0,(因?yàn)閁中只有下標(biāo)0這一個(gè)點(diǎn)), closedgei.lowcost中存放其他點(diǎn)到下標(biāo)為0的點(diǎn)的權(quán),closedge0.lowcost=0;表示下標(biāo)為0的點(diǎn)已在U中了。在closedge按順序找到最先不在U中,且與U中點(diǎn)直接相連的點(diǎn),把此邊的權(quán)賦給min，用擂臺(tái)式比較法選出closedgej.

9、lowcost中最小的,此時(shí)min中存放的是最小值所在下標(biāo),也就是下一個(gè)要放入U(xiǎn)中的點(diǎn)的下標(biāo)。輸出選中的這條邊，它是最小生成樹(shù)中的一條邊。因?yàn)閁中又加入了一個(gè)點(diǎn)，所以要修改closedgei.lowcost的值，比較新選中點(diǎn)與V-U中點(diǎn)的權(quán)和原來(lái)的closedgei.lowcost,取小的那個(gè)存入。然后繼續(xù)如上的選擇,循環(huán)vexnum-1次,就選出了最小生成樹(shù)中的vexnum-1條邊。本程序采用數(shù)組存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，把第一個(gè)點(diǎn)所到的邊記錄下來(lái)，然后把權(quán)值最小的邊存入數(shù)組，同時(shí)將剛才所存邊的的終點(diǎn)作為起點(diǎn)再次記錄該點(diǎn)所到的邊，并記錄權(quán)值最小的邊存入數(shù)組，這個(gè)過(guò)程中，已經(jīng)被訪問(wèn)的點(diǎn)不再訪問(wèn)。知道最

10、后所有的權(quán)值最小的邊全部輸出。這就是PRIM算法求最小生成樹(shù)。Prim算法有兩種形式，其偽代碼如下：算法一：procedure Prim; beginT:=；U:=1;while UV dobegin(u,v):= uU且vV-U的最小權(quán)邊;T:=T(u,v);U:=Uv;end;end;改進(jìn)的prim算法2如下：procedure Prim(var G:adj_matrix;size:integer);G為圖，size為圖的節(jié)點(diǎn)數(shù)目;注意：假設(shè)輸入的圖是連通圖varlowcost:array 1.maxsize of integer;used:array 1.maxsize of boole

11、an;closeset:array1.maxsize of integer;i,j,k,min:integer;beginfor i:=2 to size do 初始化，此時(shí)U只含有頂點(diǎn)1beginlowcosti:= G1,i;closeseti:=1;usedi:=false;end;used1:=true;for i:=2 to size dobeginmin:=maxint;j:=i;for k:=2 to size do 用選擇法尋找頂點(diǎn)分別在V-U與U中權(quán)最小的邊if (not usedk)and(lowcostk beginmin:=lowcostk;j:=k;end;write

12、ln(fout,(,closesetj,j,); 輸出找到的最小生成樹(shù)的一條邊，此處可根據(jù)情況修改usedj:=true; 將j填加到Ufor k:=2 to size do 調(diào)整lowcost和closesetif (not usedk)and(Gj,k beginlowcostk:=Gj,k;closesetk:=j;end;end;end;4 系統(tǒng)設(shè)計(jì)及其應(yīng)用一、系統(tǒng)設(shè)計(jì)數(shù)據(jù)信息以結(jié)構(gòu)體【3】【4】和數(shù)組形式儲(chǔ)存，結(jié)點(diǎn)的信息結(jié)構(gòu)體定義如下：struct graphchar tnode;char hnode;double quanzhi;gr100;char node50= ;圖的存儲(chǔ)結(jié)構(gòu)

13、為：#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最多的頂點(diǎn)個(gè)數(shù)typedef enumDG,DN,UDG,UDN GraphKind; /有向圖、有向網(wǎng)、無(wú)向圖、無(wú)向網(wǎng)typedef struct ArcCell VRType adj; /頂點(diǎn)關(guān)系類型：圖：0、1 網(wǎng)：權(quán)值 InfoType *info;/該弧相關(guān)信息指針ArcCell,AdjMaTrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/頂點(diǎn)向量 AdjMax

14、trix arcs; /鄰接矩陣 int vexnum,arcnum; /頂點(diǎn)數(shù)和弧或邊數(shù) GraphKind kind; /圖的種類標(biāo)志 Mgraph;Prim算法： void prim(mgraph g,int k,int n) /核心算法Prim算法實(shí)現(xiàn)函數(shù)int i,j,min,p; /定義整型變量i,j用于循環(huán) min和p分別用于臨時(shí)存放最小權(quán)值及其下標(biāo)struct /定義型類型數(shù)據(jù)closedge用于臨時(shí)存放下標(biāo)和最小邊int adjvex;int lowcost;closedge100; for(i=1;i=n;i+) /初始化輔助數(shù)組if(i!=k) closedgei.adj

15、vex=k;closedgei.lowcost=g.vki;closedgek.lowcost=0; /將節(jié)點(diǎn)加入生成樹(shù)中for(i=1;in;i+) /循環(huán)比較最小權(quán)值且將最小權(quán)值的點(diǎn)加入生成樹(shù)中并打印輸出p=1; /初始化p min=maxvalue; /初始化最小權(quán)值for(j=1;j=n;j+) /循環(huán)n次比較最小權(quán)值if(closedgej.lowcost!=0&closedgej.lowcostmin) /當(dāng)前節(jié)點(diǎn)不在已生成樹(shù)中且權(quán)值最下min=closedgej.lowcost; /替換最小權(quán)值為當(dāng)前節(jié)點(diǎn)的權(quán)值p=j; /記錄該節(jié)點(diǎn)下標(biāo)printf(%d_ _%dn,closed

16、gep.adjvex,p,min); /打印最小的權(quán)值的下標(biāo)和最小邊closedgep.lowcost=0; /將該節(jié)點(diǎn)加入生成樹(shù)中 for(j=1;j=n;j+) /刷新臨時(shí)存放空間if(g.vpj) (closedgej.lowcost)closedgej.lowcost=g.vpj; /賦值最小邊closedgej.adjvex=p; /賦值最小邊對(duì)應(yīng)下標(biāo) 二、最小生成樹(shù)應(yīng)用C編寫(xiě)的程序測(cè)試【5】數(shù)據(jù)：假設(shè)如圖V2V3V5V7V1V6V4343574151636結(jié)果應(yīng)該如下V3V5V7V1V6V45113V223程序運(yùn)行如圖：5 總結(jié)該算法循序漸進(jìn)，通過(guò)數(shù)組的靈活應(yīng)用，構(gòu)造無(wú)向連通圖并最

17、終輕松實(shí)現(xiàn)了生產(chǎn)最小生成樹(shù)的目的。實(shí)驗(yàn)表明最小生成樹(shù)能具體應(yīng)用到交通建設(shè)上去。這個(gè)程序還有待開(kāi)發(fā)，將其運(yùn)用到交通建設(shè)上，能起到節(jié)約資源和時(shí)間的作用，并且也是交通建設(shè)發(fā)展必要的工具。參考文獻(xiàn)【1】數(shù)據(jù)結(jié)構(gòu)與算法教程第二版，李春葆等，清華大學(xué)出版社?！?】圖論及其算法，殷劍宏等，中國(guó)科學(xué)技術(shù)大學(xué)出版社?！?】C語(yǔ)言程序設(shè)計(jì)(第三版)，譚浩強(qiáng)，清華大學(xué)出版社?！?】數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)，嚴(yán)蔚敏 吳偉民，清華大學(xué)出版社?！?】c語(yǔ)言習(xí)題集與上機(jī)指導(dǎo)第二版，譚浩強(qiáng)，高等教育出版社。附件：程序代碼：#include stdio.h#define maxnum 10#define maxvalue 88ty

18、pedef struct /定義存放各節(jié)點(diǎn)間邊的權(quán)值的二位數(shù)組為新的數(shù)據(jù)類型可稱為圖int vmaxvaluemaxvalue; mgraph; /該數(shù)據(jù)類型用標(biāo)識(shí)符mgraph表示mgraph input(int n) /數(shù)據(jù)輸入函數(shù)用于輸入各節(jié)點(diǎn)間邊的權(quán)值mgraph x; /定義x為mgraph類型while(nmaxnum) /控制輸入出錯(cuò)重新執(zhí)行printf(輸入有誤,請(qǐng)重新輸入:); scanf(%d,&n);for(int i=1;i=n;i+) /雙層循環(huán)控制每個(gè)節(jié)點(diǎn)到其他各節(jié)點(diǎn)的權(quán)值for(int j=0;j=n;j+) int temp; /定義臨時(shí)變量用于存放輸入權(quán)值便于

19、接下的過(guò)濾操作if(i=j) /各節(jié)點(diǎn)到自身的權(quán)重賦為0x.vij=0; else if(ij) /賦值其他各點(diǎn)到比其大的下標(biāo)的節(jié)點(diǎn)printf(請(qǐng)輸入節(jié)點(diǎn)%d到節(jié)點(diǎn)%d的權(quán):,i,j);scanf(%d,&temp); /將輸入臨時(shí)存放在tempwhile(temp=0|temp0) /將符合要求數(shù)據(jù)賦值給tempx.vij=temp; else /temp=-1時(shí)將權(quán)重賦值最大值88 x.vij=maxvalue;else /ij由于權(quán)重是對(duì)稱的即呈上三角或下三角分布故只需將i,j對(duì)換即可x.vij=x.vji;printf(n);return x; /返回圖xvoid print(mgr

20、aph g,int n) /打印函數(shù)int i,j; /定義整型i,jprintf( ); /打印美觀需要for(i=1;i=n;i+) printf(%2d ,i); printf(n);for(i=1;i=n;i+) /雙層循環(huán)按矩陣方式打印輸出各節(jié)點(diǎn)間權(quán)值printf(%d ,i); for(j=1;j=n;j+)printf(%2d ,g.vij); printf(n);void prim(mgraph g,int k,int n) /核心算法Prim算法實(shí)現(xiàn)函數(shù)int i,j,min,p; /定義整型變量i,j用于循環(huán) min和p分別用于臨時(shí)存放最小權(quán)值及其下標(biāo)struct /定義型類型數(shù)據(jù)closedge用于臨時(shí)存放下標(biāo)和最小邊int adjvex;int lowcost;closedgemaxnum; for(i=1;i=n;i+) /初始化輔助數(shù)組if(i!=k) closedgei.adjvex=k;closedgei.lowcost=g.vki;closedgek.lowcost=0