圖論 最小生成樹在城市交通建設中的應用

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

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

3、多種運輸方式設施建設的快速發(fā)展，各行業(yè)交通網(wǎng)絡的逐步完善，多種運輸方式網(wǎng)絡之間的疊加，難免顯現(xiàn)出各種運輸方式在通道和樞紐銜接上的不協(xié)調(diào)。其結(jié)果是，資源浪費，效率低下，使用不便利。而綜合交通網(wǎng)發(fā)展規(guī)劃的頒布有利于運輸整體結(jié)構(gòu)的調(diào)整，資源節(jié)約和集約利用，對于交通運輸業(yè)的可持續(xù)發(fā)展具有重要和深遠的意義。”在社會主義建設時期，各個城市建設問題尤其是交通建設尤為重要。在保證各個城市能互相連通的情況下，怎么保證建設公路，怎么建設最省錢是建設工程公司所需考慮的重大情況。從而能節(jié)省更多的錢來投資其他地方建設，如農(nóng)村交通建設。各個農(nóng)村交通建設好之后，則可再根據(jù)將農(nóng)村作為一個結(jié)點和其它農(nóng)村再次運用最小生成樹。最小

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

5、樹。從最小生成樹定義看主要先了解圖、樹及生成樹。本文中最小生成樹在計算機中存儲方法是應用鄰接矩陣的形式存儲。故也應了解鄰接矩陣的定義。定義一（圖）：圖是有一個非空的頂點集合和一個描述頂點之間的關(guān)系即邊的集合組成。它可以形式化的定義為：G=(V,E)V= | VertexTypeE=<,>|,VP(,) 其中，G表示一個圖，V是圖G中頂點的集合，E是V中頂點偶對的有限集，這些頂點偶對稱為邊，VertexType是用于描述頂點類型，集合E中P(,)的含義是：對有向圖來說用“<>”表示，對無向圖來說用“（）”表示，即從到 兩個頂點之間存在邊。定義二（樹）：樹包含n（

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

7、信息和邊或弧的信息。定義三（鄰接矩陣（Adjacency Matrix）：是表示頂點之間相鄰關(guān)系的矩陣。設G=(V,E)是一個圖，其中V=v1,v2,vn。G的鄰接矩陣是一個具有下列性質(zhì)的n階方陣：（本文主要為無向圖的鄰接矩陣）（1） 無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。（1）無向圖的鄰接矩陣中第i行第j列表示i結(jié)點到j結(jié)點的度即權(quán)值，可以表示為某一具體應用的數(shù)據(jù)。也表示i結(jié)點是否與j結(jié)點連通。定義四（生成樹）：如果T是G的一個生成子圖又是一棵樹，則稱T是圖G的一棵生成樹。3 prim算法介紹最小生成樹的兩個著名算法：prim算法和克魯斯卡爾算法2 ,本文應用的是prim

8、算法。則克魯斯卡爾算法則不進行描述了。Prim算法的基本思想：首先，選擇帶最小的邊，把它放進生成樹里，相繼添加帶權(quán)最小的邊，這些邊與已在樹立的頂點相關(guān)聯(lián)，并且不與已在數(shù)理的邊形成圈，當已經(jīng)添加了n-1條邊為止。PRIM算法介紹：設圖中頂點的全集為V, U中存放已選中過的點,用數(shù)據(jù)結(jié)構(gòu)closedge存放選擇需要的數(shù)據(jù),先把下標0對應點放入U中, closedgei.uxiabiao=0,(因為U中只有下標0這一個點), closedgei.lowcost中存放其他點到下標為0的點的權(quán),closedge0.lowcost=0;表示下標為0的點已在U中了。在closedge按順序找到最先不在U中,

9、且與U中點直接相連的點,把此邊的權(quán)賦給min，用擂臺式比較法選出closedgej.lowcost中最小的,此時min中存放的是最小值所在下標,也就是下一個要放入U中的點的下標。輸出選中的這條邊，它是最小生成樹中的一條邊。因為U中又加入了一個點，所以要修改closedgei.lowcost的值，比較新選中點與V-U中點的權(quán)和原來的closedgei.lowcost,取小的那個存入。然后繼續(xù)如上的選擇,循環(huán)vexnum-1次,就選出了最小生成樹中的vexnum-1條邊。本程序采用數(shù)組存儲結(jié)構(gòu)進行存儲，把第一個點所到的邊記錄下來，然后把權(quán)值最小的邊存入數(shù)組，同時將剛才所存邊的的終點作為起點再次記錄

10、該點所到的邊，并記錄權(quán)值最小的邊存入數(shù)組，這個過程中，已經(jīng)被訪問的點不再訪問。知道最后所有的權(quán)值最小的邊全部輸出。這就是PRIM算法求最小生成樹。Prim算法有兩種形式，其偽代碼如下：算法一：procedure Prim; beginT:=；U:=1;while U<>V dobegin(u,v):= uU且vV-U的最小權(quán)邊;T:=T(u,v);U:=Uv;end;end;改進的prim算法2如下：procedure Prim(var G:adj_matrix;size:integer);G為圖，size為圖的節(jié)點數(shù)目;注意：假設輸入的圖是連通圖varlowcost:array

11、1.maxsize of integer;used:array 1.maxsize of boolean;closeset:array1.maxsize of integer;i,j,k,min:integer;beginfor i:=2 to size do 初始化，此時U只含有頂點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 用選擇法尋找頂點分別在V-U與U中權(quán)最小的邊if (not us

12、edk)and(lowcostk beginmin:=lowcostk;j:=k;end;writeln(fout,'(',closesetj,',',j,')'); 輸出找到的最小生成樹的一條邊，此處可根據(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)設計及其應用一、系統(tǒng)設計數(shù)據(jù)信息以結(jié)構(gòu)體【3】【4】和數(shù)組形式儲存，結(jié)點的信息

13、結(jié)構(gòu)體定義如下：struct graphchar tnode;char hnode;double quanzhi;gr100;char node50=" "圖的存儲結(jié)構(gòu)為：#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最多的頂點個數(shù)typedef enumDG,DN,UDG,UDN GraphKind; /有向圖、有向網(wǎng)、無向圖、無向網(wǎng)typedef struct ArcCell VRType adj; /頂點關(guān)系類型：圖：0、1 網(wǎng)：權(quán)值 InfoType *info;/該弧相關(guān)信息指針ArcCell,Ad

14、jMaTrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/頂點向量 AdjMaxtrix arcs; /鄰接矩陣 int vexnum,arcnum; /頂點數(shù)和弧或邊數(shù) GraphKind kind; /圖的種類標志 Mgraph;Prim算法： void prim(mgraph g,int k,int n) /核心算法Prim算法實現(xiàn)函數(shù)int i,j,min,p; /定義整型變量i,j用于循環(huán) min和p分別用于臨時存放最小權(quán)值及其下標struct /定義型類型數(shù)據(jù)closedge

15、用于臨時存放下標和最小邊int adjvex;int lowcost;closedge100; for(i=1;i<=n;i+) /初始化輔助數(shù)組if(i!=k) closedgei.adjvex=k;closedgei.lowcost=g.vki;closedgek.lowcost=0; /將節(jié)點加入生成樹中for(i=1;i<n;i+) /循環(huán)比較最小權(quán)值且將最小權(quán)值的點加入生成樹中并打印輸出p=1; /初始化p min=maxvalue; /初始化最小權(quán)值for(j=1;j<=n;j+) /循環(huán)n次比較最小權(quán)值if(closedgej.lowcost!=0&&a

16、mp;closedgej.lowcost<min) /當前節(jié)點不在已生成樹中且權(quán)值最下min=closedgej.lowcost; /替換最小權(quán)值為當前節(jié)點的權(quán)值p=j; /記錄該節(jié)點下標printf("%d_ _%dn",closedgep.adjvex,p,min); /打印最小的權(quán)值的下標和最小邊closedgep.lowcost=0; /將該節(jié)點加入生成樹中 for(j=1;j<=n;j+) /刷新臨時存放空間if(g.vpj) < (closedgej.lowcost)closedgej.lowcost=g.vpj; /賦值最小邊closedge

17、j.adjvex=p; /賦值最小邊對應下標 二、最小生成樹應用C編寫的程序測試【5】數(shù)據(jù)：假設如圖V2V3V5V7V1V6V4343574151636結(jié)果應該如下V3V5V7V1V6V45113V223程序運行如圖：5 總結(jié)該算法循序漸進，通過數(shù)組的靈活應用，構(gòu)造無向連通圖并最終輕松實現(xiàn)了生產(chǎn)最小生成樹的目的。實驗表明最小生成樹能具體應用到交通建設上去。這個程序還有待開發(fā)，將其運用到交通建設上，能起到節(jié)約資源和時間的作用，并且也是交通建設發(fā)展必要的工具。參考文獻【1】數(shù)據(jù)結(jié)構(gòu)與算法教程第二版，李春葆等，清華大學出版社。【2】圖論及其算法，殷劍宏等，中國科學技術(shù)大學出版社。【3】C語言程序設計

18、(第三版)，譚浩強，清華大學出版社?！?】數(shù)據(jù)結(jié)構(gòu)(C語言版)，嚴蔚敏 吳偉民，清華大學出版社?！?】c語言習題集與上機指導第二版，譚浩強，高等教育出版社。附件：程序代碼：#include "stdio.h"#define maxnum 10#define maxvalue 88typedef struct /定義存放各節(jié)點間邊的權(quán)值的二位數(shù)組為新的數(shù)據(jù)類型可稱為圖int vmaxvaluemaxvalue; mgraph; /該數(shù)據(jù)類型用標識符mgraph表示mgraph input(int n) /數(shù)據(jù)輸入函數(shù)用于輸入各節(jié)點間邊的權(quán)值mgraph x; /定義x為mgr

19、aph類型while(n<=0|n>maxnum) /控制輸入出錯重新執(zhí)行printf("輸入有誤,請重新輸入:"); scanf("%d",&n);for(int i=1;i<=n;i+) /雙層循環(huán)控制每個節(jié)點到其他各節(jié)點的權(quán)值for(int j=0;j<=n;j+) int temp; /定義臨時變量用于存放輸入權(quán)值便于接下的過濾操作if(i=j) /各節(jié)點到自身的權(quán)重賦為0x.vij=0; else if(i<j) /賦值其他各點到比其大的下標的節(jié)點printf("請輸入節(jié)點%d到節(jié)點%d的權(quán):&q

20、uot;,i,j);scanf("%d",&temp); /將輸入臨時存放在tempwhile(temp=0|temp<-1) /過濾輸入數(shù)據(jù)printf("輸入有誤,請重新輸入:n");printf("請輸入%d到%d的權(quán):",i,j);scanf("%d",&temp);if(temp>0) /將符合要求數(shù)據(jù)賦值給tempx.vij=temp; else /temp=-1時將權(quán)重賦值最大值88 x.vij=maxvalue;else /i>j由于權(quán)重是對稱的即呈上三角或下三角分

21、布故只需將i,j對換即可x.vij=x.vji;printf("n");return x; /返回圖xvoid print(mgraph 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é)點間權(quán)值printf("%d ",i); for(j=1;j<=n;j+)prin

22、tf("%2d ",g.vij); printf("n");void prim(mgraph g,int k,int n) /核心算法Prim算法實現(xiàn)函數(shù)int i,j,min,p; /定義整型變量i,j用于循環(huán) min和p分別用于臨時存放最小權(quán)值及其下標struct /定義型類型數(shù)據(jù)closedge用于臨時存放下標和最小邊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; /將節(jié)點加入生成樹中for(i=1;i<n;i+) /循環(huán)比較最小權(quán)值且將