圖論在實(shí)際生活中的應(yīng)用

1、 摘 要尋找最短的路徑到達(dá)想要去的地方在這個(gè)快節(jié)奏的時(shí)代已經(jīng)變得越來越重要，它對于節(jié)約人們的時(shí)間成本具有重要意義。當(dāng)前城市的規(guī)模越來越大，交通道路狀況也越來越復(fù)雜，從一個(gè)地方到另一個(gè)地方可能有很多種路徑，如何從眾多的路徑中選擇距離最短或者所需時(shí)間最短的路徑便成了人們關(guān)注的熱點(diǎn)。能夠選擇出一條最符合條件的路徑會給我們的日常生活帶來極大地方便。本文就通過找重慶郵電大學(xué)幾個(gè)代表性地點(diǎn)之間尋找最短距離路徑為例，介紹經(jīng)典的最短路徑算法floyd算法及其算法的實(shí)現(xiàn)。關(guān)鍵字： 最優(yōu)路徑，floyd算法，尋路 一、圖論的基本知識圖論起源于舉世聞名的柯尼斯堡七橋問題。在柯尼斯堡的普萊格爾河上面有七座橋?qū)⒑又械膷u

2、及島與河岸是連接起來的,有一個(gè)問題是要從這四塊陸地中任何一塊開始，通過每一座橋而且正好只能一次，再回到起點(diǎn)。然而許多人經(jīng)過無數(shù)次的嘗試都沒有成功。在1736年歐拉神奇般的解決了這個(gè)問題，他用抽像分析法將這個(gè)問題化為第一個(gè)圖論問題：即用點(diǎn)來代替每一塊陸地，將每一座橋用聯(lián)接相應(yīng)的兩個(gè)點(diǎn)的一條線來代替，所以相當(dāng)于得到一個(gè)“圖”（如下圖）。cabd(b) 柯尼斯堡七橋圖 橋轉(zhuǎn)換成圖 歐拉證明了這個(gè)問題是沒有解的，并且推廣了這個(gè)問題，給出了對于一個(gè)給定的圖可以某種方式走遍的判定法則。這項(xiàng)工作使得歐拉成為圖論及拓?fù)鋵W(xué)的創(chuàng)始人。 圖論其實(shí)也是一門應(yīng)用數(shù)學(xué)，它的概念和結(jié)果來源非常廣泛，既有來自生產(chǎn)實(shí)踐的問題，

3、也有來自理論研究的問題。它具有以下特點(diǎn)：蘊(yùn)含了豐富的思想、漂亮的圖形以及巧妙的證明；涉及的問題很多而且廣泛，問題外表簡單樸素，本質(zhì)上卻十分復(fù)雜深刻；解決問題的方法是千變?nèi)f化，非常靈活，常常是一種問題就有一種解法。圖論研究的內(nèi)容非常廣泛，如圖的連通性、遍歷性、圖的計(jì)數(shù)、圖的著色、圖的極值問題、圖的可平面性等。歷史上參與研究圖論問題的人既有許多天才的數(shù)學(xué)家，也有不少的業(yè)余愛好者。 那么什么是圖論中的圖呢？在日常生活、生產(chǎn)活動以及科學(xué)研究中，人們常用點(diǎn)表示事物，用點(diǎn)與點(diǎn)之間是否有連線表示事物之間是否是有某種關(guān)系，這樣構(gòu)成的圖形就是圖論中的圖。其實(shí)，集合論中的二元關(guān)系的關(guān)系圖都是圖論中的圖，在這些圖中

4、，人們只關(guān)心點(diǎn)與點(diǎn)之間是否有連線，而不關(guān)心點(diǎn)的位置，以及連線的曲直。這就是圖論中的圖與幾何中的圖形的本質(zhì)區(qū)別。 因此在現(xiàn)實(shí)世界中，事物的許多狀態(tài)可以由圖形來描述，使其簡單直觀，便于理解，幫助思維，易于記憶，同時(shí)還可以根據(jù)圖的特點(diǎn)，從不同角度來擴(kuò)展討論范圍。 1.1、圖論概述圖論graph theory是數(shù)學(xué)的一個(gè)分支，也是一門新興學(xué)科，發(fā)展迅速而又應(yīng)用廣泛。它已廣泛地應(yīng)用于物理、化學(xué)、運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)管理、社會科學(xué)等幾乎所有的學(xué)科領(lǐng)域。另一方面，隨著這些學(xué)科的發(fā)展，特別是計(jì)算機(jī)科學(xué)的快速發(fā)展，又大大的促進(jìn)了圖論的發(fā)展。圖論中的研究對象是由若干給定的點(diǎn)及連接兩點(diǎn)的

5、線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。 1.2 圖論中的最短路問題路的定義 設(shè)為無向標(biāo)定圖，中頂點(diǎn)與邊的交替序列稱為到的通路，其中，為的端點(diǎn)，分別稱為始點(diǎn)與終點(diǎn)，中的邊的條數(shù)稱為它的長度，若又有，則稱為回路。若的所有邊各異，則稱為簡單通路。若又有，則稱為簡單回路，若所有的頂點(diǎn)（除與可能相同外）各異，所有的邊也各異，則稱為初級通路或路徑，若又有，則為初級回路或圈，將長度為奇數(shù)的圈成為奇圈，長度為偶數(shù)的圈為偶圈。我們要考慮的問題是對任意給定的一個(gè)賦權(quán)圖,及中兩個(gè)指點(diǎn)的頂點(diǎn)與，求出其最短路徑。易見。只要考慮簡單連通

6、圖的情形就夠了。這里我們假設(shè)每邊的權(quán)都是大于0的實(shí)數(shù)。因?yàn)楫?dāng)一條邊的權(quán)為0時(shí)。我們可以把和合并成一個(gè)頂點(diǎn)。又，我們約定邊當(dāng)且僅當(dāng)。 1.3 floyd算法 floyd算法的基本思想： 可以將問題分解，先找出最短的距離，然后在考慮如何找出對應(yīng)的行進(jìn)路線。如何找出最短路徑呢，這里還是用到動態(tài)規(guī)劃的知識，對于任何一個(gè)地點(diǎn)而言，i到j(luò)的最短距離不外乎存在經(jīng)過i與j之間的k和不經(jīng)過k兩種可能，所以可以令k=1，2，3，.，n(n是地點(diǎn)的數(shù)目)，在檢查d(ij)與d(ik)+d(kj)的值；在此d(ik)與d(kj)分別是目前為止所知道的i到k與k到j(luò)的最短距離，因此d(ik)+d(kj)就是i到j(luò)經(jīng)過k

7、的最短距離。所以，若有d(ij)d(ik)+d(kj)，就表示從i出發(fā)經(jīng)過k再到j(luò)的距離要比原來的i到j(luò)距離短，自然把i到j(luò)的d(ij)重寫為d(ik)+d(kj)，每當(dāng)一個(gè)k查完了，d(ij)就是目前的i到j(luò)的最短距離。重復(fù)這一過程，最后當(dāng)查完所有的k時(shí)，d(ij)里面存放的就是i到j(luò)之間的最短距離了。 floyd算法的基本步驟： 定義nn的方陣序列d-1, d0 , dn1,初始化： d-1c d-1ij邊的長度，表示初始的從i到j(luò)的最短路徑長度，即它是從i到j(luò)的中間不經(jīng)過其他中間點(diǎn)的最短路徑。迭代：設(shè)dk-1已求出，如何得到dk（0kn-1） dk-1ij表示從i到j(luò)的中間點(diǎn)不大于k-1

8、的最短路徑p：ij， 考慮將頂點(diǎn)k加入路徑p得到頂點(diǎn)序列q：ikj， 若q不是路徑，則當(dāng)前的最短路徑仍是上一步結(jié)果：dkij= dk1ij； 否則若q的長度小于p的長度，則用q取代p作為從i到j(luò)的最短路徑。 因?yàn)閝的兩條子路徑ik和kj皆是中間點(diǎn)不大于k1的最短路徑，所以從i到j(luò)中間點(diǎn)不大于k的最短路徑長度為：dkijmin dk-1ij, dk-1ik +dk-1kj 2、 利用圖論知識尋找指定兩點(diǎn)最短路徑2.1 把實(shí)際問題轉(zhuǎn)化成圖論問題 圖1 重慶郵電大學(xué)地圖上圖為郵電大學(xué)的地圖，我們在地圖中選取重郵的八個(gè)地方看成是八個(gè)點(diǎn)（1、新世紀(jì)超市 2、三教學(xué)樓 3、數(shù)字圖書館 4、二教學(xué)樓 5、信

9、科大樓 6、太極操場 7、老圖書館 8、31棟宿舍），用線段把每一個(gè)點(diǎn)與其相鄰的點(diǎn)連接起來，從而形成一個(gè)無向圖。再根據(jù)實(shí)際情況：不同地點(diǎn)的距離問題；路的暢通與否等給相應(yīng)的邊賦上權(quán)值，最后得出一個(gè)賦權(quán)圖，如圖2：圖2 賦權(quán)圖2.2 floyd算法用c+實(shí)現(xiàn)#include#include#includeusing namespace std;#define max_vex_num 10vector allpath; /向量，用來存放所有的頂點(diǎn)a到頂點(diǎn)i的路徑vector all; /向量，用來存放對應(yīng)路徑的長度struct mgraph char vexsmax_vex_num; int arc

10、smax_vex_nummax_vex_num;int vexnum,arcnum;mgraph g; int locatevex(mgraph g,char v)/圖的基本操作，尋找v的位置int i=0;while(ig.vexnum & v!=g.vexsi)i+;if(ig.vexnum)return i;elsereturn -1;int createudg(mgraph &g) /數(shù)組鄰接矩陣表示法構(gòu)造無向圖char v1,v2;int weight;cout請輸入圖的頂點(diǎn)數(shù)和邊的條數(shù)g.vexnumg.arcnum;cout請輸入頂點(diǎn)的名稱(0-9)endl;for(int i=

11、0;ig.vexsi; for(int q=0;qg.vexnum;q+) for(int p=0;pg.vexnum;p+) g.arcsqp=0; for(int k=0;kg.arcnum;k+)/構(gòu)造鄰接矩陣 cout輸入邊的頂點(diǎn)和權(quán)值：(格式為：起點(diǎn) 終點(diǎn) 權(quán)值)v1v2weight; int a=locatevex(g,v1); int b=locatevex(g,v2); g.arcsab=weight; g.arcsba=g.arcsab; cout該圖的鄰接矩陣表示為：n;for(int n=0;ng.vexnum;n+)/輸出頂點(diǎn) coutg.vexsn ;cout(矩陣頂

12、點(diǎn)名稱); coutendl; coutendl; for(int x=0;xg.vexnum;x+)/輸出鄰接矩陣 for(int y=0;yg.vexnum;y+) coutg.arcsxy ; coutendl; coutendl; cout+vexs;allpath.push_back(path); all.push_back(long); cout路徑:path 長度:long+vexs; int i=locatevex(g,vexs); visitedi=true; for(int j=0;jg.vexnum;j+) if(!visitedj)&(g.arcsij!=0) minw

13、ay(g,visited,g.vexsj,long+g.arcsij,vb,path); visitedi=false; void countminway(mgraph g) /該函數(shù)調(diào)用遞歸部分實(shí)現(xiàn)遞歸char va,vb;string path; coutva; coutvb;coutendl; int i=locatevex(g,va);bool visited100;for(int j=0;jg.vexnum;j+)visitedj=false; visitedi=true; int long=0; path+=va;for( j=0;jg.vexnum;j+)if(g.arcsij!

14、=0)long=g.arcsij;minway(g,visited,g.vexsj,long,vb,path); coutendl;void minway()/輸出最短路徑int min=10000;for(int i=0;iallpath.size();i+)if(allimin)min=alli;for(int j=0;jallpath.size();j+)if(allj=min)cout最短路徑: allpathj 長度:alljendl;coutendl;void main()createudg(g); /建圖countminway(g); /找出所有路徑minway(); /輸出最短

15、路徑 程序描述：通過輸入頂點(diǎn)的個(gè)數(shù)、邊的條數(shù)和名稱以及兩點(diǎn)之間的權(quán)值得到一個(gè)帶權(quán)值的矩陣。再輸入你所處的位置和你要到的位置，程序?qū)⑼ㄟ^floyd算法給出可以到達(dá)的路徑，并給出最優(yōu)的路徑（即權(quán)值最小的路徑）。 輸入圖的頂點(diǎn)個(gè)數(shù)和邊的條數(shù)，并輸入頂點(diǎn)的名稱如圖3所示。 圖3 數(shù)據(jù)輸入圖 輸入邊的權(quán)值，輸入格式為邊的起點(diǎn)名稱 終點(diǎn)名稱 和權(quán)值，如圖4所示。圖4 權(quán)值的輸入 程序自動生成并輸出圖的鄰接矩陣如圖5所示。圖5 圖的鄰接矩陣 輸入所在的位置和想要去的位置，程序給出可以到達(dá)的所以路徑及其權(quán)值，并給出最短的路徑及其權(quán)值如圖6所示。圖6 輸出結(jié)果總結(jié) 圖論其實(shí)是一門應(yīng)用數(shù)學(xué)，它的概念和結(jié)果來源非常廣泛，既有來自生產(chǎn)實(shí)踐的問題，也有來自理論研究的問題。它具有以下特點(diǎn)：蘊(yùn)含了豐富的思想、漂亮的圖形和巧妙的證明；涉及的問題多且廣泛，問題外表簡單樸素，本質(zhì)上卻十分復(fù)雜深刻；解決問題的方法千變?nèi)f化。非常靈活，常常是一種問題一種解法。圖論研究的內(nèi)容非常廣泛，如圖的連通性、遍歷性、圖的計(jì)數(shù)、圖的著色、圖的極值問題、圖的可平面性等。在實(shí)際生活中，圖論是有很大的利用價(jià)