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

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

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

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

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

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

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

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

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

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

10、連通，相反說明該圖是連通圖。具體實現(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) ;遍歷結束后可以通過統(tǒng)計 visited 數(shù)組中的值為 1 的元素的個數(shù) v 來確定訪問過的結點個數(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） 對權值進行由大到小排序由于整個算法的時間復雜度主要取決于排序算法的效率高低，因此在這里我們采用的是快速排序算法qsort (edge&mst, int i, int j )，排序的時間復雜度可以做到o (eloge)。具體算法實現(xiàn)就不再贅述。4） 簡易算法的主體部分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）實現(xiàn)步驟：從節(jié)點a開始，依次添加節(jié)點c，f，d，b，e，并依次添加

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

14、edef struct/定義圖 vertex vexsmax_vertex_num; /頂點集 adjmatrix arcs; /邊 int vexnum,arcnum;/點個數(shù)，邊個數(shù)mgraph;int locatevex(mgraph g,vertex u)/若g中存在頂點u,則返回該點在圖中位置;否則返回其他信息; 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、向圖頂點數(shù)和邊數(shù): n); scanf(%d %d,&g.vexnum,&g.arcnum); printf(輸入各頂點的值：n, g.vexnum); for(i=0;ig.vexnum;+i) /構造頂點集 scanf(%s,&g.vexsi); for(i=0;ig.vexnum;+i) /初始化鄰接方陣 for(j=0;jg.vexnum;+j) g.arcsij=infinity; printf(輸入一條邊依附的頂點及權值： n,g.arcnum);/輸入一條邊依附的頂點及權值 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; /置于對稱弧 int minimum(close c,mgraph g)/求出下一個節(jié)點 第k個頂點 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;/一個結構 boo

17、l isbreak=false; k=locatevex(g,u);/u在圖中位置 返回g.vexsi中下標 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個頂點并入u集flagcount=k;count+; for(j=0;jg.vexnum;+j) if(g.arcskjclosedgej.lowcost)/新頂點并入u后重新選擇最小邊 strcpy(closedgej.adjvex,g.vexsk); closedgej.lowcost=g.arcskj; if(isbreak) printf(此圖不連通，

19、無最小支撐樹 ！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）實現(xiàn)步驟：依次添加邊（a,c）, （d,f）, （b,e）, （c,f）, （b,c），并依次添加對應節(jié)點，各個步驟結果如下圖：（2） 算法實現(xiàn)：#include#include#define m 20#define max 20typedef struc

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

21、swapn(edge *, int, int); /交換兩條邊的權值和它們的起點和終點 void creatgraph(mgraph *g) /構件圖g int i, j,n, m; printf(請輸入圖的頂點數(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+) /輸入邊和權值 printf(n請輸入邊的起始點和終點:); scan

22、f(%d %d,&n,&m); while(n g-vexnum | m g-vexnum) printf( n);printf( n); printf(輸入的數(shù)字不符合要求 請重新輸入:); scanf(%d%d,&n,&m); g-arcnm.adj = g-arcmn.adj = 1; getchar(); printf(n請輸入%d與%d之間的權值: , n, m); scanf(%d,&g-arcnm.weight); /輸入權值 void sort(edge edges,mgraph *g) /對權值進行排序 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( 權 從 小 到 大 排 序 之 后 為:n); printf(n); printf( 起點 終點 權n); for (i = 1; i arcnum; i+) printf( %dn, edgesi.begin, edgesi.end, edgesi.weight); void swapn(edge *edges,int i, int j)

24、 /交換權值 以及頭和尾 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( 最 小 生 成