十二單元圖論

1、第十二單元圖與圖論算法導(dǎo)入：七橋問題【Seven Bridges Problem 】在哥尼斯堡的一個(gè)公園里，有七座橋?qū)⑵绽赘駹柡又袃蓚€(gè)島及島與河岸連接起來(如圖)。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點(diǎn)？1736年歐拉向圣彼得堡科學(xué)院遞交了哥尼斯堡的七座橋的論文，他用抽像分析法將這個(gè)問題化為第一個(gè)圖論問題：即把每一塊陸地用一個(gè)點(diǎn)來代替，將每一座橋用聯(lián)接相應(yīng)的兩個(gè)點(diǎn)的一條線來代替，從而相當(dāng)于得到一個(gè)“圖”。在解答問題的同時(shí)，開創(chuàng)了數(shù)學(xué)的一個(gè)新的分支-圖論與幾何拓?fù)?。圖論本身是應(yīng)用數(shù)學(xué)的一部分。12.1圖的基本概念（1）圖的定義圖是由一個(gè)頂點(diǎn)的集合V和一個(gè)頂點(diǎn)間關(guān)系的集

2、合E組成，記為 G=（V，E） V：頂點(diǎn)的有限非空集合。125341253412534圖1.2圖1.3圖1.1 E：頂點(diǎn)間關(guān)系的有限集合（邊集）。 存在一個(gè)結(jié)點(diǎn)v，可能含有多個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。（2）無向圖和有向圖無向圖（如圖1.2）：在圖G=（V，E）中，如果對(duì)于任意的頂點(diǎn)a，bV，當(dāng)(a,b)E時(shí)，必有（b,a）E（即關(guān)系R對(duì)稱），此圖稱為無向圖。無向圖中用不帶箭頭的邊表示頂點(diǎn)的關(guān)系V=1, 2, 3, 4, 5 E=(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)有向圖 (如圖1.3)： 如果對(duì)于任意的頂點(diǎn)a,bV,當(dāng)(a,b)E時(shí) ,(b,a)E未必

3、成立，則稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的結(jié)點(diǎn)。V=1, 2, 3, 4,5 E=<1,2>,<1,4>,<2,3>,<2,5>,<3,1>,<5,3>,<5,4>（3）頂點(diǎn)的度、入度和出度在無向圖中：頂點(diǎn)v的度是指與頂點(diǎn)v相連的邊的數(shù)目D(v)。D(2)=3結(jié)論：圖中所有頂點(diǎn)的度=邊數(shù)的兩倍在有向圖中：入度以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和 . ID(3)=2 出度以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和 . OD(3)=1度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。度：等于該頂點(diǎn)的入度與出度之和。

4、 D(5)=ID(5)+OD(5)=1+2=3 無向圖： 無向完全圖:（4）路徑、簡(jiǎn)單路徑、回路在圖G=（V，E）中，如果對(duì)于結(jié)點(diǎn)a，b，存在滿足下述條件的結(jié)點(diǎn)序列x1xk(k>1) x1=a，xk=b (xi，xi+1)E i=1k-11253412534圖1.4圖1.5則稱結(jié)點(diǎn)序列x1=a，x2，xk=b為結(jié)點(diǎn)a到結(jié)點(diǎn)b的一條路徑，而路徑上邊的數(shù)目（k-1）稱為該路徑的長(zhǎng)度。圖1.4: 1.(1,2,3,5) 長(zhǎng)度=3 2.(1,2,3,5,2) 長(zhǎng)度=4 3.(1,2,5,4,1) 長(zhǎng)度=4圖1.5: (1,2,5,4) 長(zhǎng)度=31.如果一條路徑上的結(jié)點(diǎn)除起點(diǎn)x1 和終點(diǎn)xk可以相

5、同外，其它結(jié)點(diǎn)均不相同，則稱此路徑為一條簡(jiǎn)單路徑。12534678圖1.6 2.x1=xk的簡(jiǎn)單路徑稱為回路（也稱為環(huán)）（5）連通、連通圖、連通分量(無向圖) 連通：“連成一片”。連通圖：“能連成一片的圖”。連通：如果存在一條從頂點(diǎn)u到v有路徑，則稱u和v是連通的。連通圖：圖中任意的兩個(gè)頂點(diǎn)u和v都是連通的，稱為連通圖（如圖1.4）。否則稱為非連通圖（如圖1.6）。125342342132連通分量：無向圖中的極大連通子圖。圖1.6中有3個(gè)連通分量：1 2 4 5 3 6 7 8（6）帶權(quán)圖一般的圖邊上沒有數(shù)字，邊僅表示兩個(gè)頂點(diǎn)的相連接關(guān)系（ 圖1.4,1.5,1.6 ）圖1.7圖中的邊可以加上

6、表示某種含義的數(shù)值，數(shù)值稱為邊的權(quán)，此圖稱為帶權(quán)圖。也稱為網(wǎng)。(如圖1.7)12.2圖的存儲(chǔ)結(jié)構(gòu)我們可以認(rèn)為圖的結(jié)構(gòu)為：G=( V,E ) V是頂點(diǎn)：數(shù)組或記錄。E是邊：鄰接矩陣/鄰接表圖的存儲(chǔ)結(jié)構(gòu)類型：1.鄰接矩陣2.鄰接表3.邊集數(shù)組4.前向星（可以被鄰接表代替）（1）鄰接矩陣(空間復(fù)雜度O(n*n)鄰接矩陣是表示結(jié)點(diǎn)間相鄰關(guān)系的矩陣。若G=（V，E）是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖，則G的鄰接矩陣是如下定義的二維數(shù)組 a1.n1.n。（注意：n盡量稍微大點(diǎn)）優(yōu)點(diǎn)：代碼書寫簡(jiǎn)單,便于操作 缺點(diǎn)：內(nèi)存空間占用太大, 找鄰接點(diǎn)慢1 (或權(quán)值)：無向圖：有邊( i , j )和邊( j , i ) 有向圖

7、：有邊< i , j >aij=0: i 到 j 無邊格式：12534125342342132125341 23451 2 3 4 50 1 1 1 01 0 1 0 11 1 0 0 11 0 0 0 10 1 1 1 00 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 01 2 3 4 51 23450 1 0 1 00 0 1 0 11 0 0 0 00 0 0 0 00 0 1 1 01 2 3 4 51 2345對(duì)角線為0：自身不相連。無向圖：是對(duì)稱矩陣。有向圖一般不是。第i行非0 的個(gè)數(shù)是結(jié)點(diǎn)i的度具體到題目時(shí)，數(shù)據(jù)的給出格式多種多

8、樣：1、直接給出鄰接矩陣，直接讀即可。如：輸入文件內(nèi)容：scanf%(“%d”,&n);for (int i=1;i<=n;i+) for(int j=1;j<=n;j+) scanf(“%d”,&aij); 50 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 0scanf(“%d%d”,&&)for ( int i=1;i<=n;i+) for (int j=1;j<=n;j+)int x,y,v;scanf(“%d%d%d”,&x,&y,&z);axy=z;/ayx=z;(

9、雙向圖時(shí)) 2、給出邊的頂點(diǎn)。如輸入文件：兩個(gè)頂點(diǎn)及權(quán)值5 71 2 21 3 21 4 32 3 12 5 33 5 24 5 4scanf(“%d” ,&n);for (int i=1;i<=n;i+) sacnf(“%d”,&k); for (int j=1;j<=k;j+) scanf(“%d”,&x); aix:=1;axi:=1; 3、給出每個(gè)頂點(diǎn)的鄰接點(diǎn)如62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 5（2）鄰接表(空間復(fù)雜度O(|E|)1.無權(quán)圖:設(shè)置結(jié)點(diǎn)指針結(jié)點(diǎn)鄰接點(diǎn)指針2.有權(quán)圖：3. 用數(shù)組模擬有權(quán)

10、圖: 對(duì)于從x為起點(diǎn)的邊，在鄰接表里裝入所對(duì)應(yīng)的y值，以及權(quán)值v,以及以x點(diǎn)為起點(diǎn)的前一個(gè)所對(duì)應(yīng)的y值的編號(hào)，link數(shù)組里裝入以i號(hào)點(diǎn)為起點(diǎn)的邊中所對(duì)應(yīng)的最后一個(gè)y值。靜態(tài)存儲(chǔ)鄰接表 聲明:struct edge int y,v,next; /y表示這條邊的終點(diǎn)編號(hào)，v是權(quán)值；/next表示同起點(diǎn)下條邊的編號(hào)是多少emaxm+100; /邊表。int linkmaxn+100; /起點(diǎn)表 linki表示由i出去的第一條邊的下標(biāo)是多少int len=0; /len表示有l(wèi)en條邊讀入：void insert(int xx,int yy,int vv) /ss為起點(diǎn),ee為終點(diǎn)，vv為權(quán)值。 e

11、+len.next=ass; ass=len; elen.y=vv; elen.v=vv;void init()scanf("%d%d",&n,&m);memset(e,0,sizeof(e);memset(link,0,sizeof(link);for (int i=1;i<=n;i+)int xx,yy,vv;scanf("%d%d%d",&xx,&yy,&vv);insert(xx,yy,vv);insert(yy,xx,vv); /這里插入的是無向圖，所以兩條邊都要插入注：在使用鄰接表時(shí)有個(gè)很強(qiáng)大的f

12、or (int i=linkk;i;i=ei.next)，在后面的題目中會(huì)出現(xiàn)，值得好好領(lǐng)悟鄰接矩陣：代碼書寫簡(jiǎn)單，找鄰接點(diǎn)慢 采用二維數(shù)組的靜態(tài)存儲(chǔ)結(jié)構(gòu)一般點(diǎn)數(shù)|v|小于 等于5000的時(shí)候，用鄰接矩陣。鄰接表：代碼書寫較復(fù)雜，找鄰接點(diǎn)快，適用于稀疏圖 采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)（指針或用數(shù)組模擬）一般點(diǎn)數(shù)|v|大于等于5000，并且邊得個(gè)數(shù)不是很多的時(shí)候，用鄰接表，并且現(xiàn)在一般都是用數(shù)組來模擬。數(shù)組模擬鏈表的速度會(huì)快一點(diǎn)，并且能避免一些錯(cuò)誤。（3）鄰接矩陣和鄰接表的優(yōu)缺點(diǎn)：對(duì)于在圖論里數(shù)據(jù)出現(xiàn)的重邊問題，鄰接矩陣必須判斷，鄰接表則可以直接處理。（4）邊表（適用于稀疏圖）聲明：Struct edge

13、int x,y /起點(diǎn)和終點(diǎn) int v /權(quán)值 emaxm+100;邊表就是單純的記錄所有邊的信息。12.3圖的遍歷給出一個(gè)圖G，從某一個(gè)初始點(diǎn)出發(fā)，按照一定的搜索方法對(duì)圖中的每一個(gè)結(jié)點(diǎn)訪問僅且訪問一次的過程。訪問結(jié)點(diǎn)：處理結(jié)點(diǎn)的過程。如輸出、查找結(jié)點(diǎn)的信息。按照搜索方法的不同，通常有兩種遍歷方法：1、深度優(yōu)先搜索dfs 2、廣度優(yōu)先搜索bfs（1）深度優(yōu)先搜索DFS遍歷算法（遞歸過程）：  1)從某一初始出發(fā)點(diǎn)i開始訪問,輸出該點(diǎn)編號(hào),并對(duì)該點(diǎn)作被訪問標(biāo)志(以免被重復(fù)訪問) 2)再從i的其中一個(gè)未被訪問的鄰接點(diǎn)j作為初始點(diǎn)出發(fā)繼續(xù)深搜。當(dāng)i的所有鄰接點(diǎn)都被訪問完，則退回

14、到i的父結(jié)點(diǎn)的另一個(gè)鄰接點(diǎn)k再繼續(xù)深搜。直到全部結(jié)點(diǎn)訪問完畢代碼實(shí)現(xiàn):（建圖參看上面代碼）bool fmaxn+10;/ 標(biāo)記是否被訪問過。 /True: 已訪問；flase：沒訪問。初始值：false 鄰接矩陣的dfs：void dfs(int k)for (int i=1;i<=n;i+)if (aki)&&(!fi)fi=1;dfs(i);鄰接表的dfs :void dfs(int k)for (int i=linkk;i;i=ai.next)if(!hai.y) fai.y=1;dfs(ai.y);主程序int main() memset(f,0,sizeof(f

15、); for (int i=1;i<=n;i+) if (!fi) dfs(i);求無向的連通分量sumn=0;for (int i=1;i<=n;i+)if (! fi) sumn+; dfs(i); printf(“%dn”,sumn);練習(xí)：P1205田野上的環(huán) dfs+ 鄰接矩陣（2）廣度優(yōu)先搜索(寬度優(yōu)先搜索）BFS按層次遍歷：從圖中某結(jié)點(diǎn)i出發(fā)，在訪問了i之后依次訪問i的各個(gè)未曾訪問的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問的結(jié)點(diǎn)都被訪問到。代碼實(shí)現(xiàn)：鄰接矩陣中的dfs：void bfs(int i); memset(q,0,si

16、zeof(q); int head=0,tail=1; q1=i; fi=true; while (head<tail) k=q+head; cout>>k; for (int j=1;j<=n,j+) if (akj && !fj) q+tail=j; fj=true; 鄰接表中的bfs：void bfs(int k)int head=0;int tail=1;q1=k;while(head<tail)for (int i=linkq+head;i;i=ai.next)if(!fai.y)fai.y=1;q+tail=ai.y;（3）圖的遍歷的簡(jiǎn)

17、單應(yīng)用【問題描述】犯罪團(tuán)伙警察抓到了n個(gè)罪犯，警察根據(jù)經(jīng)驗(yàn)知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個(gè)團(tuán)伙，但通過警察的審訊，知道其中的一些罪犯之間相互認(rèn)識(shí)，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識(shí)，有可能一個(gè)犯罪團(tuán)伙只有一個(gè)人。請(qǐng)你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號(hào)從1至n?！痉治觥堪裯個(gè)人看成圖的n個(gè)頂點(diǎn)；相互認(rèn)識(shí)的連一無向條邊。相互認(rèn)識(shí)的所有人構(gòu)成一個(gè)極大連通子圖。問題轉(zhuǎn)化為：求無向圖的連通分量（有多少個(gè)極大連通子圖）相關(guān)題目：P1206 犯罪團(tuán)伙 鄰接矩陣+dfsP1207 犯罪團(tuán)伙（大數(shù)據(jù)版） 鄰接表+dfsP1208 犯罪團(tuán)伙（超大數(shù)據(jù)版） 鄰接表+bfs

18、（4）歐拉路和歐拉回路對(duì)于最初提到的七橋問題，大數(shù)學(xué)家歐拉把它轉(zhuǎn)化成一個(gè)幾何問題：一筆畫問題，也就是我們所說的歐拉路。歐拉路或歐拉回路問題，即有一條路徑（或回路）由所有邊構(gòu)成，且每邊只用一次。所以我們要首先判斷圖中是否有歐拉路。對(duì)于一個(gè)無向圖，如果它每個(gè)點(diǎn)的度都是偶數(shù)，那么它存在一條歐拉回路；如果有且僅有2個(gè)點(diǎn)的度為奇數(shù)，那么它存在一條歐拉路；如果超過2個(gè)點(diǎn)的度為奇數(shù)，那么它就不存在歐拉路了。 有關(guān)歐拉回路的詳細(xì)講解可以借鑒07年集訓(xùn)隊(duì)仇榮琦的論文，在ftp服務(wù)器里有資料?！締栴}描述】騎馬修柵欄 Fj的農(nóng)場(chǎng)有N個(gè)柵欄，并且所有柵欄都是聯(lián)通的，問，有沒有一種走法，讓所有的柵欄都走一遍?！痉治觥考?/p>

19、遍歷所有的邊，并且不會(huì)重復(fù)。由于題目中說數(shù)據(jù)保證至少有1個(gè)解，所以一定存在歐拉路了。但是我們還要選一個(gè)點(diǎn)作為起點(diǎn)。如果沒有點(diǎn)的度為奇數(shù)，那么任何一個(gè)點(diǎn)都能做起點(diǎn)。如果有2個(gè)奇點(diǎn)，那么就只能也這兩個(gè)點(diǎn)之一為起點(diǎn)，另一個(gè)為終點(diǎn)。但是我們要注意，題目要求我們輸出的是進(jìn)行進(jìn)制轉(zhuǎn)換之后最小的（也就是輸出第一個(gè)數(shù)較小的，如果還有多組解，輸出第二個(gè)數(shù)較小的，等等），所以我們要以最小的點(diǎn)做起點(diǎn)。相關(guān)題目：P1210 騎馬修柵欄 輸出歐拉路。P1209 幾何圖形還原 鄰接矩陣+ 帶回溯的dfsP1211 街道賽跑（5）圖的傳遞閉包圖的傳遞閉包即是判斷無向圖的連通性。G的傳遞閉包： G*=（V，E*）E*=（i，

20、j）：圖G中存在一條i到j(luò)的路徑表示：如圖示：鄰接矩陣表示為： 【思考】連通性判斷對(duì)于任意圖，如何判斷是否存在從i到j(luò)的路徑【分析】判斷結(jié)點(diǎn) i 到 j是否有路徑時(shí)，需要注意：1、結(jié)點(diǎn) i 到 j 有邊則有路徑。2、i 到 j 之間沒有邊：如果存在另外的一個(gè)結(jié)點(diǎn)k，滿足：i到k有路徑，k到j(luò)有路徑，則i到j(luò)有路徑。否則i到j(luò)沒有路徑。canij=true:i到j(luò)有邊； canij= false:無邊。則：canij=canij | ( canik && cankj)算法描述：for (int i=1;i<=n;i+) cani,i:=true; for (int k=1;

21、k<=n;k+)for (int i=1;i<=n;i+) for (int j=1;j<=n;j+) canij |= (canik && cankj);練習(xí)：P1212 Geodetic集合P1234 校園網(wǎng)絡(luò)12.4圖的最短路徑【問題描述】已知各個(gè)城市之間的道路情況如下：現(xiàn)在，我們想從城市A到達(dá)城市E。怎樣走才能使得路徑最短，最短路徑的長(zhǎng)度是多少？最短路徑(ShortestPath)-屬性三角形性質(zhì)：設(shè)源點(diǎn)s到點(diǎn)x、y的最短路徑長(zhǎng)度為disx、disy。x與y之間的距離是lenxy，則有下面的“三角形定理”： disx + lenxy >= dis

22、y 松馳：若在處理過程中，有兩點(diǎn)x、y出現(xiàn)不符合“三角形定理”，則可改進(jìn)一下松馳： if ( disx+lenxy < disy ) disy = disx+lenxy;（1）每對(duì)頂點(diǎn)（任意兩點(diǎn)）之間的最短路徑-floyed( 弗洛伊德算法 )目標(biāo)：把圖中 任意 點(diǎn)i與j之間的最短距離都求出來 di,j。原理：根據(jù)圖的傳遞閉包思想：if (dik+dkj<dij )dij=dik+dkj時(shí)間復(fù)雜度：O(n*n*n)算法： for (int k=1;k<=n;k+)（注意k循環(huán)在最外層） for (int i=1;i<=n;i+) for (int j=1;j<=n

23、;j+) if (disik+diskj<disij ) disij=disik+diskj；初始化條件：dii=0 /自己到自己為0；對(duì)角線為0；dij=邊權(quán) /i與j有直接相連的邊dij=+ /i與j無直接相連的邊,一般設(shè)+為：memset 10即可探究： pathij 記錄i到j(luò)的最短路徑中j的前驅(qū)頂點(diǎn)，可用于輸出最小路徑。 如圖例：path14=2path12=3path13=1 初始化：i到j(luò)有邊，則 pathij:=i; pathji :=j 核心: for (int k=1;k<=n;k+) for (int i=1;i<=n;i+) for (int j=1;

24、j<=n;j+) if (dik+dkj<dij ) dij=dik+dkj； pathij=pathkj； 輸出i到j(luò)的路線void dfs(int i,int j)if (i=j) cout<<i<<' 'else if (pathij>0)dfs(i,pathij); cout<<j<<' ' pathi,j 記錄能使i到j(luò)的距離變短的結(jié)點(diǎn)。 初始化：pathij= -1: i與j不通的pathij:=0; 從i到j(luò)的最短路徑是直接到達(dá)的。開始有邊的都直接到達(dá)。pathij>0;從i到

25、j的最短路徑要經(jīng)過點(diǎn)pathi,j. 核心: for (int k=1;k<=n;k+) for (int i=1;i<=n;i+) for (int j=1;j<=n;j+) if (dik+dkj<dij ) dij=dik+dkj； pathij=k;輸出: cout<<i<< <<dfs(i,j)<< <<j;void dfs(int i,int j) if (pathij >0) dfs(i,pathij); cout<<pahtij<<' ' dfs(p

26、athij,j); 【問題描述】最優(yōu)乘車 H城是一個(gè)旅游勝地，每年都有成千上萬的人前來觀光。為方便游客，巴士公司在各個(gè)旅游景點(diǎn)及賓館，飯店等地都設(shè)置了巴士站并開通了一些單程巴士線路。每條單程巴士線路從某個(gè)巴士站出發(fā)，依次途經(jīng)若干個(gè)巴士站，最終到達(dá)終點(diǎn)巴士站。一名旅客最近到H城旅游，他很想去S公園游玩，但如果從他所在的飯店沒有一路巴士可以直接到達(dá)S公園，則他可能要先乘某一路巴士坐幾站，再下來換乘同一站臺(tái)的另一路巴士, 這樣換乘幾次后到達(dá)S公園。 現(xiàn)在用整數(shù)1,2,N 給H城的所有的巴士站編號(hào)，約定這名旅客所在飯店的巴士站編號(hào)為1S公園巴士站的編號(hào)為N。 寫一個(gè)程序，幫助這名旅客尋找一個(gè)最優(yōu)乘車方

27、案,使他在從飯店乘車到S公園的過程中換車的次數(shù)最少?！痉治觥繕?gòu)造權(quán)為1的有向圖有floyed尋找最優(yōu)解最少換車次數(shù)為 :d1,n-1相關(guān)題目：P1212 Geodetic集合 也可以用 floyed P1213 最優(yōu)乘車 P1214 Bessie Come Home（2）一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑（單源最短路徑） - dijkstra（迪杰斯特拉算法）單源點(diǎn)最短路徑(ShortestPath)-定義 最短路徑：對(duì)在權(quán)圖G=(V,E),從一個(gè)源點(diǎn)s到匯點(diǎn)t有很多路徑，其中路徑上權(quán)和最少的路徑，稱從s到t的最短路徑。 簡(jiǎn)單講：找出連接兩個(gè)給定點(diǎn)的最低成本路徑 單源最短路徑問題：求從源點(diǎn)s到其它所

28、有點(diǎn)的最短路徑問題。 令人驚訝的是，“單源單匯”與“單源多匯”兩個(gè)問題的算法復(fù)雜度是一樣的，有向、無向圖也一樣。統(tǒng)稱單源最短路徑問題。Dijkstra算法應(yīng)用的是貪心的理念，這個(gè)算法的思路出發(fā)點(diǎn)是，如果源點(diǎn)到某個(gè)點(diǎn)x的距離是到其他點(diǎn)的距離的最小值，那么到第點(diǎn)x的最短距離目標(biāo): 圖中一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑,不能有負(fù)權(quán) - 單源,非負(fù)原理: 經(jīng)嚴(yán)格證明的貪心時(shí)間復(fù)雜度：O(n2)【問題描述】如圖，求1號(hào)點(diǎn)到各點(diǎn)的最短路徑15341075717344 213【分析】開始點(diǎn)（源點(diǎn)）：startDi:頂點(diǎn)i到start的最短距離。初始：Dstart=0；Di=astart,i （無邊設(shè)為maxin

29、t）用集合1表示已知點(diǎn)，用集合2表示未求點(diǎn)則1中最初只有start這個(gè)點(diǎn)，集合2中有其他n-1個(gè)點(diǎn)1. 在集合2中找一個(gè)到start距離最近的頂點(diǎn)k ，距離=dk2. 把頂點(diǎn)k加到集合1中，同時(shí)修改集合2 中的剩余頂點(diǎn)j的dj是否經(jīng)過k后變短。如果變短修改dj:if (dk+akj<dj) dj=dk+akj3. 重復(fù)1，直至集合2空為止。用表格模擬如下：頂點(diǎn)12345FiTFFFFDi010497Pathi11,21,3-1,5狀態(tài)1：狀態(tài)2:頂點(diǎn)12345FiTFFFTDi01049207Pathi11,21,31,5,41,5狀態(tài)3：頂點(diǎn)12345FiTTFFTDi01027177

30、Pathi11,21,2,31, 2,41,5狀態(tài)4：頂點(diǎn)12345FiTTFTTDi01027177Pathi11,21,2,31, 2,41,5狀態(tài)5:頂點(diǎn)12345FiTTTTTDi01027177Pathi11,21,2,31, 2,41,5dijkstra 算法描述：void dijkstra(int st)for (int i=1;i<=n;i+) disi=asti;memset(vis,0,sizeof(vis);visst=1; disst=0;for (int i=1;i<n;i+) /只需要循環(huán)n-1次int minn=99999999;int k=0;for

31、(int j=1;j<=n;j+)if ( (!visj) && (disj<minn) )minn=disj;k=j;if(k=0)return; /已經(jīng)找不到了。visk=1; /把c加入集合1；for(int j=1;j<=n;j+) /三角形迭代，更新最短距離if(!visj)&&(disk+acj<disj)disj=disk+akj;St：起點(diǎn)；t：終點(diǎn)；pathi：i的前驅(qū)結(jié)點(diǎn)；way：從s到t的結(jié)點(diǎn)路徑思考1：怎樣輸出路徑？思考2：為什么不能有負(fù)權(quán)回路？這里需要不斷迭代地做“松馳”，直到無“松馳”為止。相關(guān)題目：P1217

32、 晚餐 P1220 第二短路 P1507 旅行 P1525 道路（3）最短路徑（求單源點(diǎn)到其它點(diǎn)的最短距離，判斷是否有負(fù)環(huán)）- Bellman-ford算法在之前的學(xué)習(xí)中，我們知道如果邊有負(fù)權(quán)的話，Dijkstra算法是錯(cuò)誤的。那么，我們?nèi)绾闻袛嘭?fù)環(huán)呢？Bellman-ford算法N次迭代就可以判斷圖中是否有“負(fù)環(huán)”它取所有邊有兩種方法：- 掃描每一點(diǎn)的鄰接鏈表- 用有序點(diǎn)對(duì)(x,y)記錄邊時(shí)，可直接取邊。但要請(qǐng)注意對(duì)無向圖，要注意(y,x)也要松馳。對(duì)于求s到某點(diǎn)t的最短距離，可能因?yàn)槠渌胤接小柏?fù)環(huán)”而出現(xiàn)問題，要預(yù)處理。時(shí)間復(fù)雜度：O(N*E)注意：Bellman-ford 用的是邊表算

33、法描述：SP_Bellman(G, s) 1. 初始化每點(diǎn)到s點(diǎn)的最短距離為 2. 取所有邊(x,y)，看x能否對(duì)y松馳。 3. 如果沒有任何松馳，則結(jié)束break。 4. 如果松馳次數(shù)<N，轉(zhuǎn)(2) 5如果第n次還能松弛，圖中有“負(fù)圈”。memset(dis,10,sizeof(dis); / 初始化每點(diǎn)到st距離為極大值disst=0; /將disst設(shè)為0 bool rel=0;for (int i=1;i<=n;i+) /最多迭代nrel=0; /是否有松馳標(biāo)志for (int j=1;j<=sumn;j+) /取圖的每一條邊 if(disaj.x+aj.v<d

34、isaj.y) /判斷是否滿足三角形性質(zhì) disaj.y=aj.v+disaj.x; /松馳disy rel=1; if ( !rel ) return 0; /沒有一次松馳，則結(jié)束return 1; /迭代了n次，有負(fù)圈【問題描述】蟲洞(Wormholes) 在一個(gè)神秘島上，有N(1 <= N <= 500)個(gè)洞口，標(biāo)號(hào)1.N，它們之間有M (1 <= M <= 2500) 條通道相連。神秘的是另外還有W (1 <= W <= 200)條傳說中的時(shí)間蟲洞-當(dāng)?shù)竭_(dá)通道的另一端洞口時(shí)，竟然可以比進(jìn)入的時(shí)間要早！ 你當(dāng)然想進(jìn)行這樣的時(shí)間之旅，希望從一個(gè)洞口s出發(fā)

35、，經(jīng)過幾個(gè)通道，在比出發(fā)早些時(shí)候的時(shí)間回到洞口s。也許還能碰到自己,hehe根據(jù)給定的地圖，請(qǐng)判斷能否實(shí)現(xiàn)這樣的愿望。【分析】首先，把無向邊改成兩個(gè)有向邊，這樣整個(gè)問題成在有向圖中求負(fù)環(huán)問題。 N*(M+W) = 500*（2500+200）< 2,000,000顯然，用Bellman算法不超時(shí)。本題要注意的是，兩點(diǎn)之間可能有多條邊，不能用鄰接矩陣記錄。（4）最短路徑（對(duì)Bellman-ford算法迭代的改進(jìn)）- SPFA算法Bellman-ford算法中，每次都要檢查所有的邊。這個(gè)看起來比較浪費(fèi)，對(duì)于邊(x,y)，如果上一次disx沒有改變，則本次的檢查顯然是多余的。我們每次只要從上次

36、剛被“松馳”過的點(diǎn)x，來看看x能不能松馳其它點(diǎn)即可。SPFA算法中用BFS中的隊(duì)列來存放剛被“松馳”過的點(diǎn)。由于頂點(diǎn)個(gè)數(shù)為|V|，隊(duì)列如果用數(shù)組的話顯然要用“循環(huán)隊(duì)列”使用空間時(shí)間復(fù)雜度：O(K*E)注意: SPFA使用的是鄰接表算法描述：memset(dis,10,sizeof(dis); / 初始化每點(diǎn)到s距離,不在隊(duì)列memset(vis,0,sizeof(vis); /標(biāo)記數(shù)字，表明第i個(gè)點(diǎn)是否被訪問diss=0;viss=1;que1=s; /將diss設(shè)為0, s放入隊(duì)列head=0;tail=1; /隊(duì)列頭尾指針while(head<tail)int tn=q+head;v

37、istn=0; /隊(duì)頭節(jié)點(diǎn)tn出隊(duì) 標(biāo)記其不在隊(duì)列里。int te=linktn; /取該點(diǎn)的第一條邊f(xié)or (int i=te;i;i=ei.next) /枚舉每一條邊int tmp=ei.y; /取另一節(jié)點(diǎn)if (distn+ei.v<distmp) /如果可以松弛distmp=distn+ei.v; /更新if (!vistmp) /若不在隊(duì)列中，進(jìn)隊(duì)q+tail=tmp;vistmp=1;SPFA算法的思考：對(duì)有向圖，s到t的最短路問題仍然有負(fù)環(huán)影響。無向圖呢？怎樣判斷圖上負(fù)環(huán)？SPFA最常用的優(yōu)化是SLF優(yōu)化，即將隊(duì)列用雙端隊(duì)列實(shí)現(xiàn)。如果該點(diǎn)源點(diǎn)S到當(dāng)前節(jié)點(diǎn)I的距離小于隊(duì)列首的

38、節(jié)點(diǎn)距離，那么就把該節(jié)點(diǎn)放入隊(duì)列首，否則放入隊(duì)列尾。SPFA在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過其它的點(diǎn)之后，過了一段時(shí)間可能本身會(huì)再次被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。SPFA在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過其它的點(diǎn)之后，過了一段時(shí)間可能本身會(huì)再次被改進(jìn)，于是再次用來改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。 【問題描述】香甜的黃油（b

39、utter） 農(nóng)夫John發(fā)現(xiàn)做出全威斯康辛州最甜的黃油的方法：糖。把糖放在一片牧場(chǎng)上，他知道N只奶牛會(huì)過來舔它，這樣就能做出能賣好價(jià)錢的超甜黃油。 農(nóng)夫John可以訓(xùn)練這些奶牛，讓它們?cè)诼牭解徛晻r(shí)去一個(gè)特定的牧場(chǎng)。他打算將糖放在那里然后下午發(fā)出鈴聲，以至他可以在晚上擠奶。 農(nóng)夫John知道每只奶牛都在各自喜歡的牧場(chǎng)（一個(gè)牧場(chǎng)不一定只有一頭牛）。給出各頭牛所在的牧場(chǎng)和牧場(chǎng)間的路線，找出使所有牛到達(dá)的路程和最短的牧場(chǎng)（他將把糖放在那）【分析】此題中，若用Floyd算法預(yù)處理，顯然P3=8003>5*108肯定是要超時(shí)的，但是我們注意，本圖中邊比較少，可枚舉每一點(diǎn)為源，再用Dijkstra算

40、法+堆優(yōu)化來處理: P*C*logP =800* 1450*log800<1.2*107 不超時(shí)，但是用到堆優(yōu)化（要考慮用set）而用SPFA算法來做，基本上p*e的時(shí)間復(fù)雜度，不會(huì)超時(shí)，編程難度要比Dijkstra算法+堆優(yōu)化容易的多?！咀疃搪窂娇偨Y(jié)】堆優(yōu)化的Dijkstra不能處理負(fù)邊的情況，而SPFA則可以堆優(yōu)化的Dijkstra時(shí)間復(fù)雜度穩(wěn)定，而SPFA的時(shí)間復(fù)雜度不穩(wěn)定。SPFA的實(shí)現(xiàn)比堆優(yōu)化的Dijkstra簡(jiǎn)單，平均速度也較快。 對(duì)于稠密圖來說，用dijkstra要穩(wěn)定的多，而對(duì)于稀疏圖來說，用spfa是個(gè)不錯(cuò)的選擇，在noip級(jí)別里，spfa的性價(jià)比最高。 Floyd全源

41、，無負(fù)環(huán) O(|V|3) Dijkstra單源，非負(fù) O(|V|2) 對(duì)稠密圖好可用“堆”優(yōu)化 O(|E|*log|V|) 對(duì)稀疏圖較好 Bellman-Ford和SPFA單源 無負(fù)環(huán) O(|V|*|E|)可先用Dijkstra預(yù)處理優(yōu)化SPFA用更新隊(duì)列優(yōu)化,時(shí)間復(fù)雜度平均好，但不確定。相關(guān)題目：P1215 香甜的黃油 SPFAP1216 蟲洞 Bellman-Ford【思考】有多源問題類嗎？如果邊權(quán)只有0,1(或0,1,2,3,4)，能否優(yōu)化算法？12.5圖的最小生成樹最小生成樹(MST)-定義- 生成樹：一個(gè)|V|個(gè)點(diǎn)的圖,取其中|V|-1條邊,并連接所有頂點(diǎn),則組成原圖的一個(gè)生成樹屬性

42、：|v|-1條邊、連通、無環(huán)。- 最小生成樹：加權(quán)圖的最小生成樹是一棵生成樹，其所有邊的權(quán)值之和不會(huì)大于其它任何生成樹。簡(jiǎn)單講：找出連接所有點(diǎn)的最低成本路線如圖,紅邊連接了所有頂點(diǎn),所以構(gòu)成一棵生成樹權(quán)和=1+2+4+4+7+8+9最小生成樹算法原理：- 環(huán)屬性：一棵生成樹上，增加一條邊e，再刪除e所在環(huán)上的最大邊，會(huì)得到另一棵“更好”的生成樹(如果e不是最大邊) - 剪切屬性：在圖中，剪切將頂點(diǎn)劃分成兩個(gè)不相交集合。交叉邊為地些頂點(diǎn)在兩個(gè)不同集合的邊。對(duì)于任何一個(gè)剪切，各條最小的交叉邊都屬于某個(gè)M-ST，且每個(gè)MST中都包含一條最小交叉邊。- 最小邊原則：圖中權(quán)值最小的邊(如果唯一的話)一定

43、在最小生成樹上。- 唯一性：一棵生成樹上，如果各邊的權(quán)都不相同，則最小生成樹是唯一的，反之不然。（1）最小生成樹(MST)- Prim（普里姆）算法算法描述：- 將G剪切成兩個(gè)集合A、B，A中只有一個(gè)點(diǎn)r- 取最小權(quán)的交叉邊(x,y)，xB, yB- 將y加入A- 如果已經(jīng)加了n-1條邊，結(jié)束。否則，轉(zhuǎn)到第三步算法證明：參考算法導(dǎo)論（可用反證法證明其正確性）算法要點(diǎn)：- 每次求最小權(quán)交叉邊時(shí)，如果都重新計(jì)算，則顯然要枚舉(x,y)- xA ,yB。O(n2)時(shí)間復(fù)雜度。 - 其實(shí)每次A中只是增加一個(gè)新頂點(diǎn)v，最多有交叉邊(v,y)，修改量只有與v有邊的頂點(diǎn)，為O(n)。- 只需記錄下B中的每個(gè)

44、元素y與A所有元素中最小權(quán)邊，則求最小值最多為O(n)-有時(shí)可以用“堆”優(yōu)化。（stl的set）算法圖示：對(duì)于圖最小生成樹添加為：時(shí)間復(fù)雜度：O(N*N)算法：/距離初始化memset(dis,10,sizeof(dis); for (int i=1;i<=n;i+) disi=asi; /所有點(diǎn)都不在隊(duì)列內(nèi)，除了smemset(vis,0,sizeof(vis);viss=1;sumn=0;for (int i=2;i<=n;i+) /做N-1次最短路徑 /尋找現(xiàn)在能到達(dá)的邊中最短的那條int minn=a00,c=0; for (int j=1;j<=n;j+) if(!

45、visj)&&(disj<minn) minn=disj; c=j; /c點(diǎn)到達(dá)了，最小生成樹長(zhǎng)度增加 visc=1; sumn+=minn; /基于這個(gè)點(diǎn)做松弛操作 for (int j=1;j<=n;j+) if(acj<disj)&&(!visj) disj=acj;【練習(xí)題】 1221 1222（2）最小生成樹(MST)-Kruskal（克魯斯卡爾）算法算法要點(diǎn)：Kruskal算法的最難點(diǎn)在于怎樣判斷加入邊(x,y)后是否形成了環(huán)。問題可化為：判斷邊(x,y)的兩個(gè)頂點(diǎn)x,y在圖（實(shí)際是森林）mst中最否已經(jīng)連通。如果已經(jīng)連通，加入邊將

46、形成環(huán)；否則，不形成環(huán)。在kruskal算法中，要用到并查集的合并和查找并查集代碼：int getfather (int k) /找到祖先（最高級(jí)祖先）if (fatherk=k) return k;fatherk=getfather(fatherk);return fatherk;void merge(int x,int y) /合并x,yint fx=getfather(x);int fy=getfather(y);fatherfx=fy;bool judge(int x,int y) /判斷是否在一個(gè)并查集中int fx=getfather(x);int fy=getfather(y);

47、return (fx=fy);Kruskal算法for(int i=1;i<=n;i+) /初始每個(gè)點(diǎn)都是一個(gè)集合fatheri=i;sort(e+1,e+m+1,mycmp); /邊按升序排列cal=0;for (int i=1;i<=len;i+)/尋找兩個(gè)結(jié)點(diǎn)的祖先int v=getfather(ei.x);int u=getfather(ei.y);/如果不在一個(gè)并查集中if(v!=u)/合并merge(v,u);if(+cal=n-1) /如果已經(jīng)做了N-1次printf("%dn",ei.v);return ;【最小生成樹總結(jié)】- Prim算法普通的方法 O(|V|2) - Prim算法中用“堆”方法 O(|E|+|V|)*log|V|) -對(duì)稀疏圖較好- Kruskal算法 O(|E|*