圖論論文最小生成樹算法城市高速公路問題中的應(yīng)用

1、xxxx研究生堂下考試答卷2012-2013學(xué)年第 1 學(xué)期2012年 12 月 18 日最小生成樹在城市高速公路問題中的應(yīng)用摘 要： 城市高速公路問題就是以最短高速路程連接一組城市的問題，在城市規(guī)劃和建設(shè)中應(yīng)用廣泛。本文以最小生成樹在城市高速公路問題中的應(yīng)用為例，利用最小生成樹的三種算法的分析和研究，闡明了最小生成樹在最優(yōu)化方面的作用。關(guān)鍵詞：城市高速公路問題 prim算法 kruskal算法 簡(jiǎn)易算法一 引言圖論是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。在圖論的課程體系中，圖結(jié)構(gòu)是一種非常重要的非線性數(shù)據(jù)結(jié)構(gòu)。帶權(quán)圖的最小生成樹尤其被廣泛應(yīng)用在解決工程技術(shù)及科學(xué)管理等各個(gè)領(lǐng)域的最優(yōu)化問題中。二

2、背景知識(shí)1 圖和樹：圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。樹是五圈連通無向圖，如果樹t的節(jié)點(diǎn)數(shù)為n，那么樹的邊數(shù)為n-1。2 生成樹：連通圖 g 上的一個(gè)子圖，該子圖連通，無回路且包含圖g 的所有節(jié)點(diǎn)，稱為連通圖的極小連通子圖。一個(gè)連通圖可以有多棵不同的生成樹。3 最小生成樹：對(duì)一個(gè)帶權(quán)連通圖，也有多可不同的生成樹。由于該圖是帶權(quán)圖，各邊的權(quán)值不一定相等，因此這些生成樹的各邊權(quán)值之和也不一定相同，其中權(quán)值最小的生成樹被稱為該帶權(quán)連通圖的最小生成樹。4 高速公路問題：假設(shè)有

3、 n 個(gè)城市，第 i 個(gè)城市的位置笛卡爾坐標(biāo)為 (xi，yi)，每條公路可以連接兩個(gè)城市。目前原有的公路有m 條，但是不能實(shí)現(xiàn)所有城市之間的連通，因此需要繼續(xù)修建公路，在費(fèi)用最低的原則下，實(shí)現(xiàn) n 個(gè)城市的連通，還需要修建哪些條公路。由于修路的費(fèi)用與公路的長(zhǎng)短是成正比的，所以這個(gè)問題就可以轉(zhuǎn)化成求修建哪幾條公路能夠?qū)崿F(xiàn)所有城市的連通，同時(shí)滿足所修公路總長(zhǎng)最短。三 最小生成樹的求解方法構(gòu)造最小生成樹可以有多種算法。大多數(shù)圖論教材中介紹了其中的兩種算法 prim 算法和 kruskal 算法，本文另介紹一種簡(jiǎn)易算法來實(shí)現(xiàn)最小生成樹的構(gòu)造。1 prim 算法思想：普里姆算法通過逐個(gè)往生成樹上添加頂點(diǎn)

4、來構(gòu)造連通網(wǎng)的最小生成樹。算法具體步驟：（1） 開始：選取連通網(wǎng)中的任意一個(gè)頂點(diǎn)添加到最小生成樹中。（2） 重復(fù)執(zhí)行以下操作：1） 連通網(wǎng)的頂點(diǎn)集合分成兩個(gè)部分：已經(jīng)添加到最小生成樹中的頂點(diǎn)集合和尚未添加到最小生成樹中的頂點(diǎn)集合；2） 找出所有連通這兩個(gè)集合中頂點(diǎn)的邊；3） 從中選取一條權(quán)值最小的邊添加到生成樹中，同時(shí)將與這條邊相連的頂點(diǎn)也添加到生成樹中。（3）結(jié)束：所有的頂點(diǎn)都被添加到最小生成樹中。2 kruskal 算法思想：通過逐個(gè)往生成樹上添加邊來構(gòu)造連通網(wǎng)的最小生成樹。算法具體步驟：（1） 將連通網(wǎng)中的所有頂點(diǎn)添加到最小生成樹中，構(gòu)造一個(gè)森林；（2） 將各邊按照權(quán)值從小到大排序；（3

5、） 按照排好的順序向生成樹中添加不使森林中產(chǎn)生回路的邊 (若構(gòu)成回路則不添加，繼續(xù)考察下一條邊)。直至該森林變成一棵樹為止。3 簡(jiǎn)易算法思想：通過逐個(gè)從連通網(wǎng)中刪除邊來構(gòu)造最小生成樹。算法具體步驟：（1） 將連通網(wǎng)中各邊按照權(quán)值從大到小排序；（2） 按照排好的順序從連通網(wǎng)中刪除權(quán)值最大的邊，條件是使刪除該邊后的子圖仍然保持連通(若刪除后子圖不連通則改邊保留，繼續(xù)刪除下一條邊)。直至子圖中任何一條邊都不能刪除 （即刪除任意一條邊都會(huì)造成該子圖不連通）為止。4 三種算法的比較（1） 普里姆算法：主要是對(duì)頂點(diǎn)進(jìn)行操作；采用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，在行過程中對(duì)連通網(wǎng)中的每一個(gè)頂點(diǎn)都考察到了，因此普里姆算

6、法的時(shí)間復(fù)雜度為（n 為連通網(wǎng)中頂點(diǎn)的個(gè)數(shù)）。普里姆算法適用于求邊稠密的連通網(wǎng)的最小生成樹。（2） 克魯斯卡爾算法：主要是對(duì)邊進(jìn)行操作，時(shí)間復(fù)雜度主要取決于對(duì)邊按照權(quán)值進(jìn)行排序的時(shí)間，邊的個(gè)數(shù)為e，排序的時(shí)間復(fù)雜度可以做到o (eloge)，因此算法的時(shí)間復(fù)雜度為 o(eloge)?？唆斔箍査惴ㄟm用于求邊稀疏的連通網(wǎng)的最小生成樹。（3） 簡(jiǎn)易算法：主要是對(duì)邊進(jìn)行操作，時(shí)間復(fù)雜度主要取決于對(duì)邊按照權(quán)值進(jìn)行排序的時(shí)間，邊的個(gè)數(shù)為e，排序的時(shí)間復(fù)雜度可以做到 o (eloge)，因此算法的時(shí)間復(fù)雜度為 o(eloge)。該算法適用于求邊稀疏的連通網(wǎng)的最小生成樹。四 應(yīng)用利用最小生成樹來解決高速公路

7、問題，將高速公路問題中的城市看做圖中的頂點(diǎn)，城市之間修建的道路看做圖中頂點(diǎn)之間的邊，城市之間所修修建的公路的長(zhǎng)度看做是圖中個(gè)邊上的權(quán)值。這樣我們就把高速公路問題轉(zhuǎn)換成了求一個(gè)有向連通網(wǎng)的最小生成樹問題。此時(shí)假設(shè)城市個(gè)數(shù)為6，分別為a，b，c，d，e，f。并設(shè)其對(duì)應(yīng)城市之間的公路距離權(quán)值及初始狀態(tài)的連通無向圖如下所示：邊(a,b）(a,c）(a,d）(b,c)(b,e) (c,d)(c,e)(c,f)(d,f)(e,f)權(quán)值61553564261 簡(jiǎn)易算法來求解最小生成樹（1） 實(shí)現(xiàn)步驟：從權(quán)值最大的邊開始進(jìn)行刪除 (e,f),(c,e) ,(a,b),(a,d)被刪除后都沒有破壞連通性，所以這

8、些邊可以從圖中刪除，得下圖：當(dāng)刪除第五條邊(b,c)時(shí)，造成了圖的連通性的破壞，所以該條邊不能被刪除必須保留。下圖為最終構(gòu)造好的最小生成樹：（2） 算法實(shí)現(xiàn)：1）連通網(wǎng)的存儲(chǔ)結(jié)構(gòu)表示城市高速公路網(wǎng)絡(luò)的無向連通網(wǎng)采用鄰接矩陣的存儲(chǔ)方式進(jìn)行存儲(chǔ)。由于需要區(qū)分已經(jīng)存在的公路和需要修建的公路，所以在每條邊上增加一個(gè)標(biāo)志位，同時(shí)為了給所有的邊排序，因此單獨(dú)建立一個(gè)表示邊信息的結(jié)構(gòu)體數(shù)組結(jié)構(gòu)。具體實(shí)現(xiàn)如下：typedef char towntype; typedef float roadtype;typedef struct int n; /*圖的頂點(diǎn)個(gè)數(shù) */int m; /* 圖的邊個(gè)數(shù) */town

9、type towns maxvex ; /* 頂點(diǎn)信息 */roadtype roadsmaxvexmaxvex ;/*邊信息 */ graphmatrix;typedef struct int start_town, stop_town; /* 邊的起點(diǎn)和終點(diǎn) */roadtype weight; /* 邊的權(quán) */enum exist,unexist ex;/*區(qū)別已經(jīng)建好的公路和未修建的公路 */ edge;edge mst 50 ;2） 判斷圖的連通性函數(shù)判斷無向圖的的連通性有很多方法，這里采用的是通過對(duì)圖進(jìn)行深度優(yōu)先搜索，統(tǒng)計(jì)遍歷過的頂點(diǎn)個(gè)數(shù)，如果頂點(diǎn)個(gè)數(shù)比圖中頂點(diǎn)個(gè)數(shù)少，說明該圖不

10、連通，相反說明該圖是連通圖。具體實(shí)現(xiàn)如下：void dfsmatrix (graphmatrix gm, int i, int n , int &visited ) int j;printf “(%d”,i) ;visited i =1;for (int j=0;jn;j+)if ( gm i j ! =0 & gm i j ! =maxvalue& ! visited j)dfsmatrix (gm,j,n) ;遍歷結(jié)束后可以通過統(tǒng)計(jì) visited 數(shù)組中的值為 1 的元素的個(gè)數(shù) v 來確定訪問過的結(jié)點(diǎn)個(gè)數(shù)，如果 vn 說明該無向圖不連通，反之說明該無向圖連通。graphthrough (

11、graphmatrix gm)for (i=0;in;i+) visited i =0dfsmatrix (gm, 0, n , visited) ;for (i=0;in;i+)if ( visited i =1) num+;if (num=n) return 1;else return 0;3） 對(duì)權(quán)值進(jìn)行由大到小排序由于整個(gè)算法的時(shí)間復(fù)雜度主要取決于排序算法的效率高低，因此在這里我們采用的是快速排序算法qsort (edge&mst, int i, int j )，排序的時(shí)間復(fù)雜度可以做到o (eloge)。具體算法實(shí)現(xiàn)就不再贅述。4） 簡(jiǎn)易算法的主體部分int easy (graphm

12、atrix &gm , edge mst )int i, j, num = 0, th,weight;for (i=0;igm.m;i+)if (mst i .ex=unexist)weight=gm. roads start_town stop_town ;gm. roads start_town stop_town =0;th=graphthrough (gm) ;if (th=1) continue;else gm. roads start_town stop_town =weight;2 prim算法求解最小生成樹（1）實(shí)現(xiàn)步驟：從節(jié)點(diǎn)a開始，依次添加節(jié)點(diǎn)c，f，d，b，e，并依次添加

13、對(duì)應(yīng)的邊，各個(gè)步驟如下圖所示：（2） 算法實(shí)現(xiàn)：#include#include#include#define infinity 1000#define max_name 50#define max_vertex_num 50typedef char vertexmax_name;/頂點(diǎn)名字串typedef int adjmatrixmax_vertex_nummax_vertex_num;/鄰接距陣typedef struct vertex adjvex; /鄰接矩陣 int lowcost; /權(quán)值closemax_vertex_num;/定義一個(gè)結(jié)構(gòu)以便在后面closedge 使用typ

14、edef struct/定義圖 vertex vexsmax_vertex_num; /頂點(diǎn)集 adjmatrix arcs; /邊 int vexnum,arcnum;/點(diǎn)個(gè)數(shù)，邊個(gè)數(shù)mgraph;int locatevex(mgraph g,vertex u)/若g中存在頂點(diǎn)u,則返回該點(diǎn)在圖中位置;否則返回其他信息; int i; for(i=0;ig.vexnum;+i) if(strcmp(u,g.vexsi)=0) return i; return 1;void creategraph(mgraph &g) int i,j,k,w; vertex v1,v2; printf(輸入無

15、向圖頂點(diǎn)數(shù)和邊數(shù): n); scanf(%d %d,&g.vexnum,&g.arcnum); printf(輸入各頂點(diǎn)的值：n, g.vexnum); for(i=0;ig.vexnum;+i) /構(gòu)造頂點(diǎn)集 scanf(%s,&g.vexsi); for(i=0;ig.vexnum;+i) /初始化鄰接方陣 for(j=0;jg.vexnum;+j) g.arcsij=infinity; printf(輸入一條邊依附的頂點(diǎn)及權(quán)值： n,g.arcnum);/輸入一條邊依附的頂點(diǎn)及權(quán)值 for(k=0;kg.arcnum;+k) scanf(%s%s%d,v1,v2,&w); i=locat

16、evex(g,v1);/v1在圖中位置 j=locatevex(g,v2);/v2在圖中位置 g.arcsij=g.arcsji=w; /置于對(duì)稱弧 int minimum(close c,mgraph g)/求出下一個(gè)節(jié)點(diǎn) 第k個(gè)頂點(diǎn) int i=0,j,k,min; min=infinity; /初始化 k=-1; for(j=0;j=g.vexnum;j+)/求最小 if(cj.lowcost0) min=cj.lowcost; k=j; return k;void prim(mgraph g,vertex u) int i,j,k=0; close closedge;/一個(gè)結(jié)構(gòu) boo

17、l isbreak=false; k=locatevex(g,u);/u在圖中位置 返回g.vexsi中下標(biāo) for(j=0;j=g.vexnum;+j) /輔助數(shù)組初始化 closedge從o 開始 if(j!=k)/沒有自己到自己的 closedgek.lowcost=0; strcpy(closedgej.adjvex,u); closedgej.lowcost=g.arcskj;/列 int flag1000; flag0=0; int count=1; for(i=1;ig.vexnum;+i) k=minimum(closedge,g); if(k=-1)isbreak=true;

18、break;printf(%s-%s%dn,closedgek.adjvex,g.vexsk,g.arcsklocatevex(g,closedgek.adjvex); /輸出生成樹的邊 closedgek.lowcost=0; / 第k個(gè)頂點(diǎn)并入u集flagcount=k;count+; for(j=0;jg.vexnum;+j) if(g.arcskjclosedgej.lowcost)/新頂點(diǎn)并入u后重新選擇最小邊 strcpy(closedgej.adjvex,g.vexsk); closedgej.lowcost=g.arcskj; if(isbreak) printf(此圖不連通，

19、無最小支撐樹 ！n訪問過的點(diǎn)為：n);for(i=0;icount;i+) printf(%s ,g.vexsflagi);printf(n); void main() mgraph g; creategraph(g); printf(最小生成樹的各條邊為: n); prim(g,g.vexs0); 3 kruskal算法求解最小生成樹（1）實(shí)現(xiàn)步驟：依次添加邊（a,c）, （d,f）, （b,e）, （c,f）, （b,c），并依次添加對(duì)應(yīng)節(jié)點(diǎn)，各個(gè)步驟結(jié)果如下圖：（2） 算法實(shí)現(xiàn)：#include#include#define m 20#define max 20typedef struc

20、t /構(gòu)造邊 int begin; int end; int weight; /權(quán)值edge;typedef struct int adj; int weight;adjmatrixmaxmax;typedef struct adjmatrix arc; int vexnum, arcnum; /頂點(diǎn)數(shù)和邊數(shù)mgraph;void creatgraph(mgraph *); /函數(shù)申明 構(gòu)造圖void sort(edge* ,mgraph *); /函數(shù)申明 對(duì)邊的排序void minispantree(mgraph *); /最小生成樹int find(int *, int ); void

21、swapn(edge *, int, int); /交換兩條邊的權(quán)值和它們的起點(diǎn)和終點(diǎn) void creatgraph(mgraph *g) /構(gòu)件圖g int i, j,n, m; printf(請(qǐng)輸入圖的頂點(diǎn)數(shù)和邊數(shù):); scanf(%d %d,&g-vexnum,&g-arcnum); for (i = 1; i vexnum; i+) /初始化圖 for ( j = 1; j vexnum; j+) g-arcij.adj = g-arcji.adj = 0; for ( i = 1; i arcnum; i+) /輸入邊和權(quán)值 printf(n請(qǐng)輸入邊的起始點(diǎn)和終點(diǎn):); scan

22、f(%d %d,&n,&m); while(n g-vexnum | m g-vexnum) printf( n);printf( n); printf(輸入的數(shù)字不符合要求 請(qǐng)重新輸入:); scanf(%d%d,&n,&m); g-arcnm.adj = g-arcmn.adj = 1; getchar(); printf(n請(qǐng)輸入%d與%d之間的權(quán)值: , n, m); scanf(%d,&g-arcnm.weight); /輸入權(quán)值 void sort(edge edges,mgraph *g) /對(duì)權(quán)值進(jìn)行排序 int i, j; for ( i = 1; i arcnum; i+)

23、 for ( j = i + 1; j arcnum; j+) if (edgesi.weight edgesj.weight) swapn(edges, i, j); printf( n); printf( n); printf( n); printf( 權(quán) 從 小 到 大 排 序 之 后 為:n); printf(n); printf( 起點(diǎn) 終點(diǎn) 權(quán)n); for (i = 1; i arcnum; i+) printf( %dn, edgesi.begin, edgesi.end, edgesi.weight); void swapn(edge *edges,int i, int j)

24、 /交換權(quán)值 以及頭和尾 int temp; temp = edgesi.begin; edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end; edgesi.end = edgesj.end; edgesj.end = temp; temp = edgesi.weight; edgesi.weight = edgesj.weight; edgesj.weight = temp; void minispantree(mgraph *g)/生成最小生成樹 int i, j, n, m; int k = 1; int parentm; edge edgesm; for ( i = 1; i vexnum; i+) for (j = i + 1; j vexnum; j+) if (g-arcij.adj = 1) edgesk.begin = i; edgesk.end = j; edgesk.weight = g-arcij.weight; k+; sort(edges, g); for (i = 1; i arcnum; i+) parenti = 0; printf(n);printf( n);printf( n);printf( n); printf( 最 小 生 成