二分圖匹配與最短路徑問題

1、 什么是二分圖？設(shè)G=(V,E)是一個(gè)無向圖。如頂點(diǎn)集V可分割為兩個(gè)互不相交的子集，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬兩個(gè)不同的子集。則稱圖G為二分圖。也就是說在二分圖中，頂點(diǎn)可以分為兩個(gè)集合X和Y，每一條邊的兩個(gè)頂點(diǎn)都分別位于X和Y集合中。如下圖所示：二分圖的基本性質(zhì) 頂點(diǎn)可以分成A、B兩個(gè)集合，每條邊的兩個(gè)頂點(diǎn)分別位于A、B集合中的圖被稱為二分圖。 二分圖中不含奇環(huán)。二分圖的判定方法：用DFS對二分圖進(jìn)行黑白染色。如果某個(gè)點(diǎn)染成黑色，那么與這個(gè)點(diǎn)相連的所有點(diǎn)都必須染成白色，反之同理，如果染色過程中不出現(xiàn)矛盾，那么這就是一個(gè)二分圖。怎樣判定一個(gè)圖是不是二分圖？程序主要部分：int color

2、maxn;/判定節(jié)點(diǎn)u所在的連通分量是否為二分圖bool bipartite(int u) for(int i = 0; i Gu.size(); i+) int v = Gui;/枚舉每條邊(u, v) if(colorv = coloru) return false;/結(jié)點(diǎn)v已著色，且和結(jié)點(diǎn)u的顏色沖突 if(!colorv) colorv = 3 coloru;/給結(jié)點(diǎn)v著與結(jié)點(diǎn)u相反的顏色 if(!bipartite(v) return false; return true;圖的連通性問題無向圖的連通分量（1）連通圖 在對無向圖進(jìn)行遍歷時(shí)，對于連通圖，僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)

3、先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有結(jié)點(diǎn)。（2）非連通圖 在對無向圖進(jìn)行遍歷時(shí)，對于非連通圖，需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為其各個(gè)連通分量中的頂點(diǎn)集。 有向圖的連通性 設(shè)D=為有向圖， 對于任意的u, vV，如果存在從u到v的通路，則稱u可達(dá)v，記為uv ，并規(guī)定任何頂點(diǎn)到自身總是可達(dá)的。 若D中任意兩結(jié)點(diǎn)相互可達(dá)，則稱D是強(qiáng)連通的。SCC的概念有向圖中, u可達(dá)v不一定意味著v可達(dá)u. 相互可達(dá)則屬于同一個(gè)強(qiáng)連通分量(Strongly Connected Component, SCC)有向圖和它的轉(zhuǎn)置的有向圖和它的轉(zhuǎn)置的強(qiáng)連通分

4、量相同強(qiáng)連通分量相同所有SCC構(gòu)成一個(gè)DAG(有向無環(huán)圖) 求強(qiáng)連通分量使用 Kosaraju算法 一、Kosaraju算法步驟： Step1、對有向圖G做dfs（深度優(yōu)先遍歷），記錄每個(gè)結(jié)點(diǎn)結(jié)束訪問的時(shí)間(即節(jié)點(diǎn)出棧順序，后出棧的點(diǎn)第二次先掃描) Step2、將圖G逆置，即將G中所有弧反向。 Step3、按Step1中記錄的結(jié)點(diǎn)結(jié)束訪問時(shí)間從大到小對逆置后的圖做dfs Step4、得到的遍歷森林中每棵樹對應(yīng)一個(gè)強(qiáng)連通分量。二、Kosaraju算法求解過程實(shí)例下面結(jié)合實(shí)例說明Kosaraju算法的基本策略。圖1給出了一個(gè)有向圖G。ACBDEFGH圖1 有向圖GStep1：假設(shè)從DFS在遍歷時(shí)按

5、照字母順序進(jìn)行，根據(jù)Kosaraju算法，在步驟1中我們得到的遍歷順序可以表達(dá)為A,C,B,D,D,B,C,AE,F,G,H,H,G,F,E 越后出棧的點(diǎn)先訪問 第一步所得到的順序即為：EFGHACBDStep2：根據(jù)算法第2步，將圖G逆置，得到對應(yīng)的反向圖G如圖2所示。AC圖2 逆置圖GGHBDEFACBDEFGH圖1 有向圖G Step3：根據(jù)步驟1得到的遍歷序列，按照結(jié)點(diǎn)結(jié)束訪問時(shí)間遞減排序后的結(jié)果 EFGHACBD 下面，按照該結(jié)點(diǎn)序列順序?qū)δ嬷脠DG所深度優(yōu)先遍歷，得到的深度優(yōu)先遍歷森林如圖3所示。森林中共有4棵樹，其中(a)和(d)只有一個(gè)結(jié)點(diǎn)，這里認(rèn)為單結(jié)點(diǎn)也是一個(gè)強(qiáng)聯(lián)通分量（在實(shí)

6、際應(yīng)用中可以根據(jù)實(shí)際需要將這種情況過濾掉）。AC圖2 逆置圖GGHBDEF圖3 逆置圖G的DFS生成森林GEFHBACD (a) (b) (c) (d) kasaraju 算法代碼 #includeconst int MAXN = 100 + 10, INF = 1000000000;int visMAXN, orderMAXN, idMAXN; /是否遍歷、第二次遍歷的順序、個(gè)點(diǎn)所屬的強(qiáng)連通分量int n,m,number; /點(diǎn)數(shù)、邊數(shù)、計(jì)數(shù)器int mapmaxmax; /圖int net = 0;void init() /初始化 int i, j; scanf(%d%d, &n

7、, &m); for(i = 1; i = n; i+)for(j = 1; j = n; j+) mapij = INF; for(i=1;i=n;i+) mapii=0;void read() /讀取數(shù)據(jù) int i, a, b; number = n; for(i = 1; i = m; i+) scanf(%d%d, &a, &b); mapab = 1; void dfs1(int v) /第一次遍歷確定點(diǎn)的順序 int i; visv=1; for(i = 1; i = n; i+)if(mapviINF & visi!=1) dfs1(i);ord

8、ernumber = v;/出棧的時(shí)候記錄順序于ORDER數(shù)組number-;void dfs2(int v) int i; visv = 1; idv = number;/V點(diǎn)所屬的連通分量 for(i =1; i = n; i+) if(mapivinf & visi!=1) dfs2(i);void kosaraju() int i, j; for(i = 1; i = n; i+)/第一次DFS確定第二次DFS順序 if(!visi) dfs1(i); number = 0; for(i = 1; i = n; i+) visi = 0; for(i = 1; i = n; i

9、+) if(visorderi!=1) number+;/連通分量標(biāo)記 dfs2(orderi);ACBDEFGH圖1 有向圖Gint main() int i, j; init(); read(); kosaraju(); for(i = 1; i ,i); for(j=1;jl uW u v( )( , ) 則令l v( )=l uW u v( )( , ),z v( )= u先寫出帶權(quán)鄰接矩陣： 03064093021509701608120W因 G 是無向圖，故 W是對稱陣 TO MATLAB(road1)u1u2u3u4u5u6u7u8218152939763416第0步u2u3u4

10、u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第1步u3u2u3u4u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第2步u310(u1,u3)u2u2u3u4u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第3步u310(u1,u3)u23(u1,u2)u5u2u3u4u5u6u7u82181529397634162(u1)8(u1)1(u1)u1第4步u310(u1,u3)u23(u1,u2)u66(u1,u2, u5)12(u1,u2,u5)u5u2u3u4u5u6u7u8218152939

11、7634162(u1)8(u1)1(u1)u1第5步u310(u1,u3)u23(u1,u2)u66(u1,u2, u5)12(u1,u2,u5)u57(u1,u2,u5,u6)u4u2u3u4u5u6u7u82181529397634162(u1)1(u1)u1第6步u310(u1,u3)u23(u1,u2)u66(u1,u2, u5)12(u1,u2,u5)u57(u1,u2,u5,u6)u49(u1,u2,u5,u6,u4)u7u8u3u4u6u7u1u3u2u6u5u4u7u81243553317284例2 求出點(diǎn)1到其余各頂點(diǎn)的最短有向路的長度？例例3 狼、羊、白菜問題狼、羊、白菜問

12、題狼、羊、白菜過河問題狼、羊、白菜過河問題 獵人要把一只狼、一頭羊和一籃白菜從河的左岸帶到右岸，但他的渡船太小，一次只能帶一樣。因?yàn)槔且匝?，羊?huì)吃白菜，所以狼和羊，羊和白菜不能在無人監(jiān)視的情況下相處。問獵人怎樣才能達(dá)到目的？ 人、狼、羊、菜四種的任意組合共有16種。其中狼羊菜、狼羊、羊菜三種不允許出現(xiàn)，所以人、人狼、人菜也不允許出現(xiàn)。因此，允許出現(xiàn)的情況共有以下10種情況：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空。把這10種狀態(tài)視為10個(gè)點(diǎn)，若一種狀態(tài)通過一次擺渡后可變?yōu)榱硪环N狀態(tài)，則在兩種狀態(tài)（點(diǎn)）之間畫一直線 ，得示意圖如下：7424613503 將各頂點(diǎn)到“人狼羊菜

13、”的距離標(biāo)在圖中各頂點(diǎn)處，可知有兩種最迅速最安全的渡河方案： （1）人狼羊菜狼菜人狼菜狼 人狼羊羊 人羊空； （2）人狼羊菜狼菜人狼菜菜 人羊菜羊 人羊空；每種方案都要七次。 這種“用頂點(diǎn)代表狀態(tài)，邊代表狀態(tài)間的轉(zhuǎn)移”的狀態(tài)轉(zhuǎn)移圖模型頗具代表性任何具有有限個(gè)狀態(tài)的多步?jīng)Q策問題都可以類似地建立圖的模型，利用圖論工具來解決 這樣擺渡問題就轉(zhuǎn)化成在圖中找出以“人狼羊菜”為起點(diǎn)，以“空”為終點(diǎn)的簡單路。int gMAXNMAXN, n;void Dijkstra(int s, int t) int i, distMAXN, visMAXN; memset(vis, false, sizeof(vis)

14、; for(i = 1; i = n; i+) disti = INF; dists = 0; while(true) int u = -1, mind = INF;for(i = 1; i = n; i+) if(!visi & distimind) u = i;mind = disti; if(u = -1) break;visu = true;for(i = 1; i distu+gui)disti = distu+gui; return distt;Dijkstra算法的主要部分：二、任意兩點(diǎn)間的最短路問題二、任意兩點(diǎn)間的最短路問題算法原理算法原理 求距離矩陣的方法求距離矩陣的

15、方法把帶權(quán)鄰接矩陣 W 作為距離矩陣的初值，即 D(0)=)()0(ijd=W（）D(1)= )() 1 (ijd，其中)0(1)0() 1 (,miniijijddd)0(1jd)1(ijd是從 vi到 vj的只允許以 v1作為中間點(diǎn)的路徑中最短路的長度（2）D(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是從 vi到 vj的只允許以 v1 、 v2作為中間點(diǎn)的路徑中最短路的長度（）D()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是從 vi到 vj的只允許以 v1、v2、v作為中間點(diǎn)

16、的路徑中最短路的長度即是從 vi到 vj中間可插入任何頂點(diǎn)的路徑中最短路的長，因此D()即是距離矩陣算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R ij算法原理算法原理 查找最短路路徑的方法查找最短路路徑的方法若1)(prij，則點(diǎn) p1是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn).然后用同樣的方法再分頭查找若：（） 向點(diǎn) i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向點(diǎn) j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：jqqqpppimk,21, 12算法步驟算法

17、步驟D(i,j)：i 到 j 的距離R(i,j)：i 到 j 之間的插入點(diǎn)輸入: 帶權(quán)鄰接矩陣 w(i,j)例例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑v1v2v4v3v5937422第0步( 0 )( 0 )09312345902712345, 2024123453201234574012345DR(1)(1)09312345902712345, 2024123453201234574012345DR121211第2步( 2 )( 2 )0931234590212712315, 202412345312201134574012345DR111116161919222222(3 )(3 )15

18、3463346331566091131224902123, 112024223453201344035333DR第3步( 4 )( 4 )031402462333, 7594447 2024234534206133436460453343495DR第4步(5 )( 4 )(5 )( 4 ), DDRR TO MATLAB(road2(floyd)由 v4向 v1追朔：141r所以從 v5到 v1的最短路徑為：1435.const int INF = 1000000000, MAXN = 1010;int gMAXNMAXN, n;void Floyd() int i, j, k, distMA

19、XNMAXN; for(i = 1; i = n; i+)for(j = 1; j = n; j+) distij = INF; for(k = 1; k = n; k+)for(i = 1; i = n; i+) for(j = 1; j distik + distkj) distij = distik + distkj;Floyd算法的主要部分：例例1 1 某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時(shí)間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是時(shí)間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購置設(shè)備，每年需支付購置費(fèi)用；若繼續(xù)使用舊否更新。若購置設(shè)備，每年需支付購置費(fèi)用；若繼續(xù)使用舊設(shè)備，需要支付維修與運(yùn)行費(fèi)用，而且隨著設(shè)備的老化會(huì)逐設(shè)備，需要支付維修與運(yùn)行費(fèi)用，而且隨著設(shè)備的老化會(huì)逐年增加。計(jì)劃期（五年）內(nèi)中每年的購置費(fèi)、維