圖論及其應(yīng)用論文

1、圖論及其應(yīng)用論文姓名：xxx學(xué)號(hào)：xxx專業(yè)：xxx圖論在高?；ヂ?lián)校內(nèi)網(wǎng)建設(shè)的應(yīng)用摘要圖論和我們的生活其實(shí)是息息相關(guān)的，我們?cè)谏钪刑幪幙梢?jiàn)圖論的實(shí)際應(yīng)用。特別的，圖論對(duì)我們通信專業(yè)以后的工作也有著極大的幫助。在以后的工作中也會(huì)時(shí)時(shí)用到圖論的相關(guān)知識(shí)。本論文的主旨是利用相關(guān)的圖論知識(shí)來(lái)解決重慶幾所高校建立互聯(lián)校內(nèi)網(wǎng)的問(wèn)題。主要是為了能使各重慶高校的學(xué)生能夠免費(fèi)共享高校的學(xué)習(xí)資源。從而促進(jìn)各高校學(xué)生的共同發(fā)展。本文中，解決重慶幾所高校建立互聯(lián)校內(nèi)網(wǎng)主要應(yīng)用的是求圖的最小生成樹(shù)的方法。而求圖的最小生成樹(shù)有兩種算法，一種是Prim（普里姆）算法，另一種是Kruskal（克魯斯卡爾）算法。本文通過(guò)將高

2、校轉(zhuǎn)換成連通圖，再將連通圖轉(zhuǎn)換成鄰接矩陣。在C+上，通過(guò)輸入結(jié)點(diǎn)和權(quán)值，用普里姆算法獲得權(quán)值最小邊來(lái)得到最小生成樹(shù)，從而在保證各個(gè)地點(diǎn)之間能連通的情況下節(jié)省所需費(fèi)用。關(guān)鍵字：最小生成樹(shù)、PRIM算法、鄰接矩陣、高?；ヂ?lián)校內(nèi)網(wǎng)建設(shè)1. 連通圖（1）概述在圖論中，連通圖基于連通的概念。在一個(gè)無(wú)向圖 G 中，若從頂點(diǎn)vi到頂點(diǎn)vj有路徑相連(當(dāng)然從vj到vi也一定有路徑)，則稱vi和vj是連通的。如果 G 是有向圖，那么連接vi和vj的路徑中所有的邊都必須同向。如果圖中任意兩點(diǎn)都是連通的，那么圖被稱作連通圖。圖的連通性是圖的基本性質(zhì)。（2）嚴(yán)格定義對(duì)一個(gè)圖 G=(V,E) 中的兩點(diǎn) x 和 y ，若

3、存在交替的頂點(diǎn)和邊的序列=(x=v0-e1-v1-e2-.-ek-(vk+1)=y) (在有向圖中要求有向邊vi( vi+1)屬于E )，則兩點(diǎn) x 和 y 是連通的。是一條x到y(tǒng)的連通路徑，x和y分別是起點(diǎn)和終點(diǎn)。當(dāng) x = y 時(shí)， 被稱為回路。如果通路 中的邊兩兩不同，則 是一條簡(jiǎn)單通路，否則為一條復(fù)雜通路。如果圖 G 中每?jī)牲c(diǎn)間皆連通，則 G 是連通圖。（3)相關(guān)概念連通分量：無(wú)向圖 G的一個(gè)極大連通子圖稱為 G的一個(gè)連通分量（或連通分支）。連通圖只有一個(gè)連通分量，即其自身；非連通的無(wú)向圖有多個(gè)連通分量。強(qiáng)連通圖：有向圖 G=(V,E) 中，若對(duì)于V中任意兩個(gè)不同的頂點(diǎn) x和 y，都存

4、在從x到 y以及從 y到 x的路徑，則稱 G是強(qiáng)連通圖。相應(yīng)地有強(qiáng)連通分量的概念。強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即是其自身；非強(qiáng)連通的有向圖有多個(gè)強(qiáng)連分量。弱連通圖：將有向圖的所有的有向邊替換為無(wú)向邊，所得到的圖稱為原圖的基圖。如果一個(gè)有向圖的基圖是連通圖，則有向圖是弱連通圖。初級(jí)通路：通路中所有的頂點(diǎn)互不相同。初級(jí)通路必為簡(jiǎn)單通路，但反之不真。(4)性質(zhì)一個(gè)無(wú)向圖 G=(V,E) 是連通的，那么邊的數(shù)目大于等于頂點(diǎn)的數(shù)目減一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向圖，那么它是強(qiáng)連通圖的必要條件是邊的數(shù)目大于等于頂點(diǎn)的數(shù)目：|E|>=|V|，而反之不成立。沒(méi)

5、有回路的無(wú)向圖是連通的當(dāng)且僅當(dāng)它是樹(shù)，即等價(jià)于：|E|=|V|-1。2. 最小生成樹(shù)（1）樹(shù)樹(shù)包含n（n>=0）個(gè)節(jié)點(diǎn)。當(dāng)n=0時(shí)表示為空樹(shù)。其定義如下：T=(D,R)其中，D為樹(shù)中節(jié)點(diǎn)的有限集合，關(guān)系R滿足一下條件：有且僅有一個(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)。除根結(jié)點(diǎn)k0之外，D中的每個(gè)結(jié)點(diǎn)僅有一個(gè)前趨結(jié)點(diǎn)，但可以有過(guò)個(gè)后繼結(jié)點(diǎn)。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)。（2）鄰接矩陣圖的矩陣表示，本文中只用到了鄰接矩陣，故在這只提出鄰接矩陣的定義，及其圖在鄰接矩陣中的表示。設(shè)圖 A = (

6、V, E)是一個(gè)有 n 個(gè)頂點(diǎn)的圖, 圖的鄰接矩陣是一個(gè)二維數(shù)組 A.edgenn，用來(lái)存放頂點(diǎn)的信息和邊或弧的信息。是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是一個(gè)圖，其中V=v1,v2,vn。G的鄰接矩陣是一個(gè)具有下列性質(zhì)的n階方陣：無(wú)向圖的鄰接矩陣是對(duì)稱的;有向圖的鄰接矩陣可能是不對(duì)稱的。無(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)連通。（3）最小生成樹(shù)在一給定的無(wú)向圖G=(V, E)中(u,v) 代表連接頂點(diǎn)u與頂點(diǎn)v的邊(即),而 w(u,v)代表此邊的權(quán)重,若存在T為E的子集（即)且為無(wú)循環(huán)圖，使得的w(T)

7、最小則此T為G的最小生成樹(shù)。3.prim算法思想：首先，選擇帶最小的邊，把它放進(jìn)生成樹(shù)里，相繼添加帶權(quán)最小的邊，這些邊與已在樹(shù)立的頂點(diǎn)相關(guān)聯(lián)，并且不與已在數(shù)理的邊形成圈，當(dāng)已經(jīng)添加了n-1條邊為止步驟：假設(shè)V是圖中頂點(diǎn)的集合，E是圖中邊的集合，TE為最小生成樹(shù)中的邊的集合，則prim算法通過(guò)以下步驟可以得到最小生成樹(shù)：（1）初始化：U=u 0,TE=f。此步驟設(shè)立一個(gè)只有結(jié)點(diǎn)u 0的結(jié)點(diǎn)集U和一個(gè)空的邊集TE作為最小生成樹(shù)的初始形態(tài)，在隨后的算法執(zhí)行中，這個(gè)形態(tài)會(huì)不斷的發(fā)生變化，直到得到最小生成樹(shù)為止。（2）在所有uU,vVU的邊（u,v）E中，找一條權(quán)最小的邊（u0,v0），將此邊加進(jìn)集合T

8、E中，并將此邊的非U中頂點(diǎn)加入U(xiǎn)中。此步驟的功能是在邊集E中找一條邊，要求這條邊滿足以下條件：首先邊的兩個(gè)頂點(diǎn)要分別在頂點(diǎn)集合U和VU中，其次邊的權(quán)要最小。找到這條邊以后，把這條邊放到邊集TE中，并把這條邊上不在U中的那個(gè)頂點(diǎn)加入到U中。這一步驟在算法中應(yīng)執(zhí)行多次，每執(zhí)行一次，集合TE和U都將發(fā)生變化，分別增加一條邊和一個(gè)頂點(diǎn)，因此，TE和U是兩個(gè)動(dòng)態(tài)的集合，這一點(diǎn)在理解算法時(shí)要密切注意。（3）如果U=V，則算法結(jié)束；否則重復(fù)步驟2。可以把本步驟看成循環(huán)終止條件。我們可以算出當(dāng)U=V時(shí)，步驟2共執(zhí)行了n1次（設(shè)n為圖中頂點(diǎn)的數(shù)目），TE中也增加了n1條邊，這n1條邊就是需要求出的最小生成樹(shù)的邊

9、。4.實(shí)際問(wèn)題及其解決現(xiàn)有：重慶大學(xué)，西南大學(xué)，西南政法大學(xué)，重慶師范大學(xué)，重慶郵電大學(xué)5所高校，要求把他們的校內(nèi)網(wǎng)進(jìn)行互聯(lián)，以組建一個(gè)更大的校園網(wǎng)絡(luò)。在發(fā)費(fèi)最少的情況下進(jìn)行光纜的鋪設(shè)。根據(jù)實(shí)際測(cè)量地圖的得到的各學(xué)校之間的直線距離圖：由于每公里光纜造價(jià)相同，故可以用實(shí)際距離代替造價(jià)作為權(quán)重。實(shí)際情況縮略圖：設(shè)：重慶郵電大學(xué)V1重慶大學(xué)V2重慶師范大學(xué)V3西南大學(xué)V4西南政法大學(xué)V5輸入程序運(yùn)行得到結(jié)果：解決問(wèn)題得到結(jié)果：5.總結(jié)通過(guò)對(duì)prim算法編寫(xiě)的程序我們可以輕易地得到在發(fā)費(fèi)最少的情況下進(jìn)行光纜的鋪設(shè)的路徑。這大大的節(jié)約了成本和時(shí)間，是對(duì)實(shí)際問(wèn)題的一次生動(dòng)嘗試。同時(shí)這個(gè)程序也可以進(jìn)行相應(yīng)的

10、改善和推廣，以利于我們的工作實(shí)踐。參考文獻(xiàn)【1】圖論及其算法，殷劍宏等，中國(guó)科學(xué)技術(shù)大學(xué)出版社?！?】C語(yǔ)言程序設(shè)計(jì)(第三版)，譚浩強(qiáng)，清華大學(xué)出版社。【3】數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)，嚴(yán)蔚敏 吳偉民，清華大學(xué)出版社。程序#include "stdio.h"#define maxnum 10#define maxvalue 88typedef struct /定義存放各節(jié)點(diǎn)間邊的權(quán)值的二位數(shù)組為新的數(shù)據(jù)類(lèi)型可稱為圖int vmaxvaluemaxvalue; mgraph; /該數(shù)據(jù)類(lèi)型用標(biāo)識(shí)符mgraph表示mgraph input(int n) /數(shù)據(jù)輸入函數(shù)用于輸入各節(jié)點(diǎn)間

11、邊的權(quán)值mgraph x; /定義x為mgraph類(lèi)型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)值便于接下的過(guò)濾操作if(i=j) /各節(jié)點(diǎn)到自身的權(quán)重賦為0x.vij=0; else if(i<j) /賦值其他各點(diǎn)到比其大的下標(biāo)的節(jié)點(diǎn)printf(&

12、quot;請(qǐng)輸入節(jié)點(diǎn)%d到節(jié)點(diǎn)%d的權(quán):",i,j);scanf("%d",&temp); /將輸入臨時(shí)存放在tempwhile(temp=0|temp<-1) /過(guò)濾輸入數(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=maxvalue;else /i&

13、gt;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); f

14、or(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 /定義型類(lèi)型數(shù)據(jù)closedge用于臨時(shí)存放下標(biāo)和最小邊int adjvex;int lowcost;closedgemaxnum; for(i=1;i<=n;i+) /初始化輔助數(shù)組if(i!=k) closedgei.adjvex=k;

15、closedgei.lowcost=g.vki;closedgek.lowcost=0; /將節(jié)點(diǎn)加入生成樹(shù)中for(i=1;i<n;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.lowcost<min) /當(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",closedgep.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)int main() /主函數(shù)int n,start; /定義整型n,start表示節(jié)點(diǎn)數(shù)和開(kāi)始節(jié)點(diǎn)printf