二分圖匹配(匈牙利算法)

1、Pku (2239 2727 1274=1149 2584 2536 2446簡(jiǎn)單)1449 1325 3189 3041設(shè)G=(V,R)是一個(gè)無(wú)向圖。如頂點(diǎn)集V可分割為兩個(gè)互不相交的子集，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬兩個(gè)不同的子集。則稱圖G為二分圖。1 給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集E中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配。2選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問(wèn)題3 如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。最大匹配在實(shí)際中有廣泛的用處，求最大匹配的一種顯而易見(jiàn)的算法是：先找出全部匹

2、配，然后保留匹配數(shù)最多的。但是這個(gè)算法的復(fù)雜度為邊數(shù)的指數(shù)級(jí)函數(shù)。因此，需要尋求一種更加高效的算法。匈牙利算法是求解最大匹配的有效算法，該算法用到了增廣路的定義(也稱增廣軌或交錯(cuò)軌)：若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬M(fèi)的邊和不屬M(fèi)的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱P為相對(duì)于M的一條增廣路徑。由增廣路徑的定義可以推出下述三個(gè)結(jié)論：1. P的路徑長(zhǎng)度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M。2.P經(jīng)過(guò)取反操作（即非M中的邊變?yōu)镸中的邊，原來(lái)M中的邊去掉）可以得到一個(gè)更大的匹配M。3. M為G的最大匹配當(dāng)且僅當(dāng)不存在相對(duì)于M的增廣路徑。從而可以得到求解最大匹配的匈牙利

3、算法： (1)置M為空(2)找出一條增廣路徑P，通過(guò)取反操作獲得更大的匹配M代替M(3)重復(fù)(2)操作直到找不出增廣路徑為止根據(jù)該算法，我選用dfs (深度優(yōu)先搜索)實(shí)現(xiàn)。程序清單如下：int matchi /存儲(chǔ)集合m中的節(jié)點(diǎn)i在集合n中的匹配節(jié)點(diǎn),初值為-1。int n,m,match100;                      /二分圖的兩個(gè)集合分別含有n和m個(gè)元素

4、。bool visit100,map100100;               /map存儲(chǔ)鄰接矩陣。bool dfs(int k)int t;for(int i = 0; i < m; i+)     if(mapki && !visiti)      visiti = true;      t

5、 = matchi;      matchi = k;                            /路徑取反操作。      if(t = -1 | dfs(t) /尋找是否為增廣路徑   

6、;    return true;      matchi = t;     return false;int main()/.     int    s = 0;     memset(match,-1,sizeof(match);     for(i = 0; i < n; i+)   &

7、#160;  /以二分集中的較小集為n進(jìn)行匹配較優(yōu)      memset(visit,0,sizeof(visit);      if(dfs(i)          s+;          /s為匹配數(shù)     /.return 0;什么是二分圖，什么是二分圖的最

8、大匹配，這些定義我就不講 了，網(wǎng)上隨便都找得到。二分圖的最大匹配有兩種求法，第一種是最大流（我在此假設(shè)讀者已有網(wǎng)絡(luò)流的知識(shí)）；第二種就是我現(xiàn)在要講的匈牙利算法。這個(gè)算法說(shuō) 白了就是最大流的算法，但是它跟據(jù)二分圖匹配這個(gè)問(wèn)題的特點(diǎn)，把最大流算法做了簡(jiǎn)化，提高了效率。匈牙利算法其實(shí)很簡(jiǎn)單，但是網(wǎng)上搜不到什么說(shuō)得清楚的文 章。所以我決定要寫(xiě)一下。最大流算法的核心問(wèn)題就是找增廣路徑（augment path）。匈牙利算法也不例外，它的基本模式就是：初始時(shí)最大匹配為空while 找得到增廣路徑    do 把增廣路徑加入到最大匹配中去可見(jiàn)和最大流算法是一樣的。但是這里的增廣

9、路徑就有它一定的特殊性，下面我來(lái)分析一下。（注：匈牙利算法雖然根本上是最大流算法，但是它不需要建網(wǎng)絡(luò)模型，所以圖中不再需要源點(diǎn)和匯點(diǎn)，僅僅是一個(gè)二分圖。每條邊也不需要有方向。）圖1 圖2圖1是我給出的二分圖中的一個(gè)匹配：1，5和2，6。圖2就是在這個(gè)匹配的基礎(chǔ)上找到的一條增廣路徑：3->6->2->5->1->4。我們借由它來(lái)描述一下二分圖中的增廣路徑的性質(zhì)：(1)有奇數(shù)條邊。(2)起點(diǎn)在二分圖的左半邊，終點(diǎn)在右半邊。(3)路徑上的點(diǎn)一定是一個(gè)在左半邊，一個(gè)在右半邊，交替出現(xiàn)。（其實(shí)二分圖的性質(zhì)就決定了這一點(diǎn)，因?yàn)槎謭D同一邊的點(diǎn)之間沒(méi)有邊相連，不要忘記哦。）(4

10、)整條路徑上沒(méi)有重復(fù)的點(diǎn)。(5)起點(diǎn)和終點(diǎn)都是目前還沒(méi)有配對(duì)的點(diǎn)，而其它所有點(diǎn)都是已經(jīng)配好對(duì)的。（如圖1、圖2所示，1，5和2，6在圖1中是兩對(duì)已經(jīng)配好對(duì)的點(diǎn)；而起點(diǎn)3和終點(diǎn)4目前還沒(méi)有與其它點(diǎn)配對(duì)。）(6)路徑上的所有第奇數(shù)條邊都不在原匹配中，所有第偶數(shù)條邊都出現(xiàn)在原匹配中。（如圖1、圖2所示，原有的匹配是1，5和2，6，這兩條配匹的邊在圖2給出的增廣路徑中分邊是第2和第4條邊。而增廣路徑的第1、3、5條邊都沒(méi)有出現(xiàn)在圖1給出的匹配中。）(7)最后，也是最重要的一條，把增廣路徑上的所有第奇數(shù)條邊加入到原匹配中去，并把增廣路徑中的所有第偶數(shù)條邊從原匹配中刪除（這個(gè)操作稱為增廣路徑的取反），則新

11、的匹配數(shù)就比原匹配數(shù)增加了1個(gè)。（如圖2所示，新的匹配就是所有藍(lán)色的邊，而所有紅色的邊則從原匹配中刪除。則新的匹配數(shù)為3。）不難想通，在最初始時(shí)，還沒(méi)有任何匹配時(shí)，圖1中的兩條灰色的邊本身也是增廣路徑。因此在這張二分圖中尋找最大配匹的過(guò)程可能如下：(1)找到增廣路徑1->5，把它取反，則匹配數(shù)增加到1。(2)找到增廣路徑2->6，把它取反，則匹配數(shù)增加到2。(3)找到增廣路徑3->6->2->5->1->4，把它取反，則匹配數(shù)增加到3。(4)再也找不到增廣路徑，結(jié)束。當(dāng)然，這只是一種可能的流程。也可能有別的找增廣路徑的順序，或者找到不同的增廣路徑，最終

12、的匹配方案也可能不一樣。但是最大匹配數(shù)一定都是相同的。對(duì)于增廣路徑還可以用一個(gè)遞歸的方法來(lái)描述。這個(gè)描述不一定最準(zhǔn)確，但是它揭示了尋找增廣路徑的一般方法：“從點(diǎn)A出發(fā)的增廣路徑”一定首先連向一個(gè)在原匹配中沒(méi)有與點(diǎn)A配對(duì)的點(diǎn)B。如果點(diǎn)B在原匹配中沒(méi)有與任何點(diǎn)配對(duì)，則它就是這條增廣路徑的終點(diǎn)；反之，如 果點(diǎn)B已與點(diǎn)C配對(duì)，那么這條增廣路徑就是從A到B，再?gòu)腂到C，再加上“從點(diǎn)C出發(fā)的增廣路徑”。并且，這條從C出發(fā)的增廣路徑中不能與前半部分的增廣 路徑有重復(fù)的點(diǎn)。比如圖2中，我們要尋找一條從3出發(fā)的增廣路徑，要做以下3步：(1)首先從3出發(fā)，它能連到的點(diǎn)只有6，而6在圖1中已經(jīng)與2配對(duì)，所以目前的增

13、廣路徑就是3->6->2再加上從2出發(fā)的增廣路徑。(2)從2出發(fā)，它能連到的不與前半部分路徑重復(fù)的點(diǎn)只有5，而且5確實(shí)在原匹配中沒(méi)有與2配對(duì)。所以從2連到5。但5在圖1中已經(jīng)與1配對(duì)，所以目前的增廣路徑為3->6->2->5->1再加上從1出發(fā)的增廣路徑。(3)從1出發(fā)，能連到的不與自已配對(duì)并且不與前半部分路徑重復(fù)的點(diǎn)只有4。因?yàn)?在圖1中沒(méi)有與任何點(diǎn)配對(duì)，所以它就是終點(diǎn)。所以最終的增廣路徑是3->6->2->5->1->4。但是嚴(yán)格地說(shuō)，以上過(guò)程中從2出發(fā)的增廣路徑（2->5->1->4）和從1出發(fā)的增廣路徑

14、（1->4）并不是真正的增廣路徑。 因?yàn)樗鼈儾环锨懊嬷v過(guò)的增廣路徑的第5條性質(zhì)，它們的起點(diǎn)都是已經(jīng)配過(guò)對(duì)的點(diǎn)。我們?cè)谶@里稱它們?yōu)椤霸鰪V路徑”只是為了方便說(shuō)明整個(gè)搜尋的過(guò)程。而這兩 條路徑本身只能算是兩個(gè)不為外界所知的子過(guò)程的返回結(jié)果。顯然，從上面的例子可以看出，搜尋增廣路徑的方法就是DFS，可以寫(xiě)成一個(gè)遞歸函數(shù)。當(dāng)然，用BFS也完全可以實(shí)現(xiàn)。至此，理論基礎(chǔ)部份講完了。但是要完成匈牙利算法，還需要一個(gè)重要的定理：如果從一個(gè)點(diǎn)A出發(fā)，沒(méi)有找到增廣路徑，那么無(wú)論再?gòu)膭e的點(diǎn)出發(fā)找到多少增廣路徑來(lái)改變現(xiàn)在的匹配，從A出發(fā)都永遠(yuǎn)找不到增廣路徑。要用文字來(lái)證明這個(gè)定理很繁，話很難說(shuō)，要么我還得多畫(huà)一張圖，我在此就省了。其實(shí)你自己畫(huà)幾個(gè) 圖，試圖舉兩個(gè)反例，這個(gè)定理不難想通的。（給個(gè)提示。如果你試圖舉個(gè)反例來(lái)說(shuō)明在找到了別的增廣路徑并改變了現(xiàn)有的匹配后，從A出發(fā)就能找到增廣路徑。 那么，在這種情況下，肯定在找到別的增