圖論應(yīng)用案例

1、河北工業(yè)大學(xué)2013級(jí)學(xué)生論文：最小生成樹在城市交通建設(shè)中的應(yīng)用題目：最小生成樹在城市交通建設(shè)中的應(yīng)用姓 名： 學(xué) 號(hào)： 指導(dǎo)老師： 專 業(yè)： 機(jī)械工程 2014年3月161目錄摘 要I1 緒論12 有關(guān)最小生成樹的概念23 prim算法介紹34 系統(tǒng)設(shè)計(jì)及其應(yīng)用5一、系統(tǒng)設(shè)計(jì)5二、最小生成樹應(yīng)用65 總結(jié)9參考文獻(xiàn)10附件：11最小生成樹在城市交通建設(shè)中的應(yīng)用摘要：連通圖廣泛應(yīng)用于交通建設(shè)，求連通圖的最小生成樹是最主要的應(yīng)用。比如要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，要考慮的是如何保證n點(diǎn)連通的前提下最節(jié)省經(jīng)費(fèi)，就應(yīng)用到了最小生成樹。求圖的最小生成樹有兩種算法，一種是Prim（普里姆）算法，另一種是

2、Kruskal（克魯斯卡爾）算法。本文通過將城市各地點(diǎn)轉(zhuǎn)換成連通圖，再將連通圖轉(zhuǎn)換成鄰接矩陣。在Microsoft Visual C+上，通過輸入結(jié)點(diǎn)和權(quán)值，用普里姆算法獲得權(quán)值最小邊來得到最小生成樹，從而在保證各個(gè)地點(diǎn)之間能連通的情況下節(jié)省所需費(fèi)用。本文從分析課題的題目背景、題目意義、題目要求等出發(fā)，分別從需求分析、總體設(shè)計(jì)、詳細(xì)設(shè)計(jì)、測試等各個(gè)方面詳細(xì)介紹了系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過程，最后對(duì)系統(tǒng)的完成情況進(jìn)行了總結(jié)。關(guān)鍵字：PRIM算法、最小生成樹、鄰接矩陣、交通建設(shè)AbstractConnected graph is widely applied in traffic construction

3、, connected graph of minimum spanning tree is the main application.Such as to establish a communication network between the n city, want to consider is how to ensure n points connected under the premise of the most save money, apply to the minimum spanning tree.O figure there are two kinds of minimu

4、m spanning tree algorithm, one kind is Prim (she) algorithm, the other is a Kruskal algorithm (Kruskal).In this article, through the city around point into a connected graph, then connected graph is transformed into adjacency matrix.On Microsoft Visual c + +, through the input nodes and the weights,

5、 gain weight minimum edge using she algorithm to get minimum spanning tree, which in the case of guarantee every location between connected to save costs.Based on the analysis topic subject background, significance, subject requirements, etc, from requirements analysis, general design, detailed desi

6、gn, testing, and other aspects detailed introduces the system design and implementation process, finally the completion of the system are summarized. Key words: PRIM algorithm, minimum spanning tree, adjacency matrix, traffic construction1緒論中國國際工程咨詢公司交通業(yè)務(wù)部主任周曉勤指出，“以前的各專業(yè)規(guī)劃主要是按照本行業(yè)交通發(fā)展的需求進(jìn)行研究和規(guī)劃的，在交通

7、設(shè)施總量不足、基本網(wǎng)不完善的時(shí)候，互相之間的矛盾并不突出。但隨著多種運(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)輸整體結(jié)構(gòu)的調(diào)整，資源節(jié)約和集約利用，對(duì)于交通運(yùn)輸業(yè)的可持續(xù)發(fā)展具有重要和深遠(yuǎn)的意義。”在社會(huì)主義建設(shè)時(shí)期，各個(gè)城市建設(shè)問題尤其是交通建設(shè)尤為重要。在保證各個(gè)城市能互相連通的情況下，怎么保證建設(shè)公路，怎么建設(shè)最省錢是建設(shè)工程公司所需考慮的重大情況。從而能節(jié)省更多的錢來投資其他地方建設(shè)，如農(nóng)村交通建設(shè)。各個(gè)農(nóng)村交通建設(shè)好之后

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

9、生成樹的概念最小生成樹：連通加權(quán)圖里權(quán)和最小的生成樹稱為最小生成樹。從最小生成樹定義看主要先了解圖、樹及生成樹。本文中最小生成樹在計(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ì)有向圖來說用“<>”表示，對(duì)無向圖來說用“

10、（）”表示，即從到 兩個(gè)頂點(diǎn)之間存在邊。定義二（樹）：樹包含n（n>=0）個(gè)節(jié)點(diǎn)。當(dāng)n=0時(shí)表示為空樹。其定義如下：T=(D,R)其中，D為樹中節(jié)點(diǎn)的有限集合，關(guān)系R滿足一下條件：1） 有且僅有一個(gè)節(jié)點(diǎn)k0屬于D，它對(duì)于關(guān)系R來說沒有前趨節(jié)點(diǎn)，結(jié)點(diǎn)k0稱作樹的根結(jié)點(diǎn)。2） 除根結(jié)點(diǎn)k0之外，D中的每個(gè)結(jié)點(diǎn)僅有一個(gè)前趨結(jié)點(diǎn)，但可以有過個(gè)后繼結(jié)點(diǎn)。3） D中可以有多個(gè)終端結(jié)點(diǎn)。即除根結(jié)點(diǎn)無父結(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)的圖

11、, 圖的鄰接矩陣是一個(gè)二維數(shù)組 A.edgenn，用來存放頂點(diǎn)的信息和邊或弧的信息。定義三（鄰接矩陣（Adjacency Matrix）：是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個(gè)圖，其中V=v1,v2,vn。G的鄰接矩陣是一個(gè)具有下列性質(zhì)的n階方陣：（本文主要為無向圖的鄰接矩陣）（1） 無向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。（1）無向圖的鄰接矩陣中第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)連通。定義四（生成樹）：如果T是G的一個(gè)生成子圖又是一棵樹，則稱T是圖G的一棵生成樹。3 prim算法介紹最小生成樹的兩個(gè)

12、著名算法：prim算法和克魯斯卡爾算法2 ,本文應(yīng)用的是prim算法。則克魯斯卡爾算法則不進(jìn)行描述了。Prim算法的基本思想：首先，選擇帶最小的邊，把它放進(jìn)生成樹里，相繼添加帶權(quán)最小的邊，這些邊與已在樹立的頂點(diǎn)相關(guān)聯(lián)，并且不與已在數(shù)理的邊形成圈，當(dāng)已經(jīng)添加了n-1條邊為止。PRIM算法介紹：設(shè)圖中頂點(diǎn)的全集為V, U中存放已選中過的點(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;表示下

13、標(biāo)為0的點(diǎn)已在U中了。在closedge按順序找到最先不在U中,且與U中點(diǎn)直接相連的點(diǎn),把此邊的權(quán)賦給min，用擂臺(tái)式比較法選出closedgej.lowcost中最小的,此時(shí)min中存放的是最小值所在下標(biāo),也就是下一個(gè)要放入U(xiǎn)中的點(diǎn)的下標(biāo)。輸出選中的這條邊，它是最小生成樹中的一條邊。因?yàn)閁中又加入了一個(gè)點(diǎn)，所以要修改closedgei.lowcost的值，比較新選中點(diǎn)與V-U中點(diǎn)的權(quán)和原來的closedgei.lowcost,取小的那個(gè)存入。然后繼續(xù)如上的選擇,循環(huán)vexnum-1次,就選出了最小生成樹中的vexnum-1條邊。本程序采用數(shù)組存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，把第一個(gè)點(diǎn)所到的邊記錄下來，然后

14、把權(quán)值最小的邊存入數(shù)組，同時(shí)將剛才所存邊的的終點(diǎn)作為起點(diǎn)再次記錄該點(diǎn)所到的邊，并記錄權(quán)值最小的邊存入數(shù)組，這個(gè)過程中，已經(jīng)被訪問的點(diǎn)不再訪問。知道最后所有的權(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;改進(jìn)的prim算法2如下：procedure Prim(var G:adj_matrix;size:integer);G為圖，size為圖的節(jié)點(diǎn)數(shù)

15、目;注意：假設(shè)輸入的圖是連通圖varlowcost:array 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 初始化，此時(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

16、用選擇法尋找頂點(diǎn)分別在V-U與U中權(quán)最小的邊if (not usedk)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)設(shè)計(jì)及其應(yīng)用一

17、、系統(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)為：#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最多的頂點(diǎn)個(gè)數(shù)typedef enumDG,DN,UDG,UDN GraphKind; /有向圖、有向網(wǎng)、無向圖、無向網(wǎng)typedef struct ArcCell VRType adj; /頂點(diǎn)關(guān)系類型：圖：0、1 網(wǎng)：權(quán)值 In

18、foType *info;/該弧相關(guān)信息指針ArcCell,AdjMaTrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;/頂點(diǎn)向量 AdjMaxtrix 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í)存

19、放最小權(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.adjvex=k;closedgei.lowcost=g.vki;closedgek.lowcost=0; /將節(jié)點(diǎn)加入生成樹中for(i=1;i<n;i+) /循環(huán)比較最小權(quán)值且將最小權(quán)值的點(diǎn)加入生成樹中并打印輸出p=1; /初始化p min=maxvalue; /初始化最小權(quán)值for(j=1;j<=n;j+) /循環(huán)n次比較最小

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

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

22、及其算法，殷劍宏等，中國科學(xué)技術(shù)大學(xué)出版社?！?】C語言程序設(shè)計(jì)(第三版)，譚浩強(qiáng)，清華大學(xué)出版社?！?】數(shù)據(jù)結(jié)構(gòu)(C語言版)，嚴(yán)蔚敏 吳偉民，清華大學(xué)出版社?！?】c語言習(xí)題集與上機(jī)指導(dǎo)第二版，譚浩強(qiáng)，高等教育出版社。附件：程序代碼：#include "stdio.h"#define maxnum 10#define maxvalue 88typedef struct /定義存放各節(jié)點(diǎn)間邊的權(quán)值的二位數(shù)組為新的數(shù)據(jù)類型可稱為圖int vmaxvaluemaxvalue; mgraph; /該數(shù)據(jù)類型用標(biāo)識(shí)符mgraph表示mgraph input(int n) /數(shù)據(jù)輸入

23、函數(shù)用于輸入各節(jié)點(diǎn)間邊的權(quán)值mgraph x; /定義x為mgraph類型while(n<=0|n>maxnum) /控制輸入出錯(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)值便于接下的過濾操作if(i=j) /各節(jié)點(diǎn)到自身的權(quán)重賦為0x.vij=0; else if(i<j) /賦值其他各點(diǎn)到比其大的下標(biāo)的

24、節(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|temp<-1) /過濾輸入數(shù)據(jù)printf("輸入有誤,請(qǐng)重新輸入:n");printf("請(qǐng)輸入%d到%d的權(quán):",i,j);scanf("%d",&temp);if(temp>0) /將符合要求數(shù)據(jù)賦值給tempx.vij=temp; else /temp=-1時(shí)將權(quán)重賦值最大值88 x.vij=maxvalu

25、e;else /i>j由于權(quán)重是對(duì)稱的即呈上三角或下三角分布故只需將i,j對(duì)換即可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é)點(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+)