




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 互聯(lián)網(wǎng)+農(nóng)業(yè)金融服務(wù)模式及其風(fēng)險(xiǎn)管理
- 高職院校田徑運(yùn)動(dòng)訓(xùn)練計(jì)劃與實(shí)施的協(xié)調(diào)機(jī)制
- 多國(guó)法律與標(biāo)準(zhǔn)對(duì)跨境數(shù)據(jù)治理的協(xié)調(diào)
- 河南省周口市扶溝縣2025屆八年級(jí)數(shù)學(xué)第一學(xué)期期末質(zhì)量跟蹤監(jiān)視試題含解析
- 2025至2030全球及中國(guó)白金戒指行業(yè)項(xiàng)目調(diào)研及市場(chǎng)前景預(yù)測(cè)評(píng)估報(bào)告
- 礦產(chǎn)資源采石場(chǎng)股份買(mǎi)賣(mài)協(xié)議
- 航空航天產(chǎn)業(yè)財(cái)稅代理與研發(fā)費(fèi)用加計(jì)扣除合同
- 老年人的健康飲食與烹飪技巧
- 液態(tài)金屬電極行業(yè)投資機(jī)會(huì)與風(fēng)險(xiǎn)評(píng)估
- 高新技術(shù)在特定區(qū)域的產(chǎn)業(yè)化發(fā)展指導(dǎo)研究
- 福建省機(jī)關(guān)工作人員年度考核登記表
- JBT 7808-2010 無(wú)損檢測(cè)儀器 工業(yè)X射線探傷機(jī)主參數(shù)系列
- DB44-T 2474-2024 自然教育標(biāo)識(shí)設(shè)置指引
- 研學(xué)基地合作協(xié)議
- 駕駛員行為規(guī)范管理制度
- (高清版)JTG D81-2017 公路交通安全設(shè)施設(shè)計(jì)規(guī)范
- 《鍋爐水介質(zhì)檢驗(yàn)導(dǎo)則標(biāo)準(zhǔn)-征求意見(jiàn)稿》
- 2023年陽(yáng)江市陽(yáng)東區(qū)教育局招聘事業(yè)編制教師考試真題
- 利用隱私保護(hù)技術(shù)實(shí)現(xiàn)網(wǎng)絡(luò)爬蟲(chóng)安全抓取
- 成本會(huì)計(jì)崗位競(jìng)聘稿
- 2024年新版消防設(shè)施操作員初級(jí)考試題庫(kù)(含答案)
評(píng)論
0/150
提交評(píng)論