二分圖最大匹配.doc

《二分圖最大匹配.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、二分圖的最大匹配就是要在二分圖的邊集E中找到一個子集S，使S中的任兩條邊沒有公共頂點，且｜S｜達(dá)到最大。二分圖有很多實際應(yīng)用，如工作分配問題。同時二分圖最大匹配問題又可以轉(zhuǎn)化成“最小頂點覆蓋”、“最小路徑覆蓋”、“最大獨立集“等問題，因此顯得非常重要。下面就介紹二分圖最大匹配算法。二分圖最大匹配可以轉(zhuǎn)換成最大流問題來解。假設(shè)二分圖的兩個頂點集分別為X，Y，那么我們在圖中添加一個源s，和一個匯t。同時，在s與X的每個頂點間加一條有向邊(s,vx)，在Y的每個頂點與t間加一條有向邊(vy,t)。X與Y的每條邊也變?yōu)閄－>Y的有向邊。圖

2、中每條邊的容量為1。則最大匹配問題就轉(zhuǎn)換為求轉(zhuǎn)換后的圖G'的最大流的問題。利用Ford－Fulkerson方法求最大流，時間復(fù)雜度為O（VE），V為頂點數(shù)，E為邊數(shù)。具體證明參考《算法導(dǎo)論》。經(jīng)典的求二分圖最大匹配的算法是Edmond于1965年提出的匈牙利算法。算法的核心思想是由一個初始匹配不斷找增廣路，直到找不到增廣路為止。這里的增廣路和網(wǎng)絡(luò)流中的增廣路有些不同。這里的增廣路是這樣的一條路：設(shè)已有的匹配為M，它的第一條邊不在M中，最后一條邊也不在M中，中間為在M中的邊與不在M中的邊交錯出現(xiàn)。顯然，這條路起點在X中，終點在Y中，

3、且不在M中的邊比在M中的邊多1。所以我們?nèi)魧υ鰪V路中的邊進(jìn)行取反，即原來不是匹配邊的邊變?yōu)槠ヅ溥叄瓉硎瞧ヅ溥叺倪呑優(yōu)椴皇瞧ヅ溥叺倪?，則我們能獲得一個更大的匹配。所以這么一直找下去，直到找不到增廣路為止，我們最后得到的匹配M就是要求的最大匹配。匈牙利算法中，初始匹配我們可以設(shè)為空，然后用DFS或者BFS找增廣路。找一條增廣路的復(fù)雜度為O（E），最多找V條增廣路，故算法時間復(fù)雜度為O（VE）。下面給出匈牙利算法的兩種實現(xiàn)：1.DFS找增廣路#include#includeusingnamespa

4、cestd;constintMAXN=100;intuN,vN;//u,ｖ數(shù)目boolg[MAXN][MAXN];//g[i][j]表示xi與yj相連intxM[MAXN],yM[MAXN];//輸出量boolchk[MAXN];//輔助量檢查某輪y[v]是否被checkboolSearchPath(intu){intv;for(v=0;v

5、

6、SearchPath(yM[v])){yM[v]=u;xM[u]=v;return

7、true;}}}returnfalse;}intMaxMatch(){intu;intret=0;memset(xM,-1,sizeof(xM));memset(yM,-1,sizeof(yM));for(u=0;u#include

8、ring>usingnamespacestd;#defineMAXN128intg[MAXN][MAXN],Mx[MAXN],My[MAXN],Nx,Ny;intchk[MAXN],Q[MAXN],prev[MAXN];intMaxMatch(void){intres=0;intqs,qe;memset(Mx,-1,sizeof(Mx));memset(My,-1,sizeof(My));memset(chk,-1,sizeof(chk));for(inti=0;i

9、qe++]=i;prev[i]=-1;boolflag=0;while(qs=0)prev[My[v]]=u;else{flag=1;intd=u,e=v;while(d!=-1){intt=Mx[d];Mx[d]=e;My[e]=d;d=prev[d];e=t;}}}}qs++;}if(Mx[i]!=-1)res++;}

10、}returnres;}優(yōu)點：適用于稀疏二分圖，邊較少，增廣路較短。還有一種叫做Hopcroft－Carp的算法，時間復(fù)雜度為O（V^0.5E）。該算法的主要思想是在找增廣路的時候同時找多條不相交的增廣路，形成極大增廣路集，然后對極大增廣路集進(jìn)行增