本文關(guān)鍵詞：匈牙利算法，由筆耕文化傳播整理發(fā)布。

【基本概念】：

二分圖：

二分圖又稱(chēng)作二部圖，是圖論中的一種特殊模型。 設(shè)G=(V,E)是一個(gè)無(wú)向圖，如果頂點(diǎn)V可分割為兩個(gè)互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關(guān)聯(lián)的兩個(gè)頂點(diǎn)i和j分別屬于這兩個(gè)不同的頂點(diǎn)集(i in A,j in B)，則稱(chēng)圖G為一個(gè)二分圖。 

最大匹配：

給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱(chēng)M是一個(gè)匹配.　　選擇這樣的邊數(shù)最大的子集稱(chēng)為圖的最大匹配問(wèn)題，如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱(chēng)此匹配為完全匹配，也稱(chēng)作完備匹配.  

最小覆蓋：

最小路徑覆蓋： 

用盡量少的不相交簡(jiǎn)單路徑覆蓋有向無(wú)環(huán)圖Ｇ的所有結(jié)點(diǎn)。解決此類(lèi)問(wèn)題可以建立一個(gè)二分圖模型。把所有頂點(diǎn)i拆成兩個(gè)：Ｘ結(jié)點(diǎn)集中的i和Y結(jié)點(diǎn)集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設(shè)二分圖最大匹配為m,則結(jié)果就是n-m。 

增廣路（增廣軌）：

若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬于M的邊和不屬于M的邊(即已匹配和待匹配的邊)在P上交替出現(xiàn)，則稱(chēng)P為相對(duì)于M的一條增廣路徑（舉例來(lái)說(shuō)，有A、B集合，增廣路由A中一個(gè)點(diǎn)通向B中一個(gè)點(diǎn)，再由B中這個(gè)點(diǎn)通向A中一個(gè)點(diǎn)……交替進(jìn)行）。 

增廣路徑的性質(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 整條路徑上沒(méi)有重復(fù)的點(diǎn)。

5 起點(diǎn)和終點(diǎn)都是目前還沒(méi)有配對(duì)的點(diǎn)，而其它所有點(diǎn)都是已經(jīng)配好對(duì)的。

6 路徑上的所有第奇數(shù)條邊都不在原匹配中，所有第偶數(shù)條邊都出現(xiàn)在原匹配中。

7 最后，也是最重要的一條，把增廣路徑上的所有第奇數(shù)條邊加入到原匹配中去，并把增廣路徑中的所有第偶數(shù)條邊從原匹配中刪除（這個(gè)操作稱(chēng)為增廣路徑的取反），則新的匹配數(shù)就比原匹配數(shù)增加了1個(gè)。

了解了增廣路的定義以及性質(zhì)之后，我們仔細(xì)理解第7條性質(zhì)。因?yàn)樵鰪V路徑的長(zhǎng)度為奇數(shù)，我們不妨設(shè)為2*K+1，又因?yàn)榈谝粭l是非匹配邊，且匹配邊與非匹配邊交替出現(xiàn)，所以非匹配邊有K+1條，匹配邊有K條。此時(shí)，我們做取反操作，則匹配邊的個(gè)數(shù)會(huì)在原來(lái)的基礎(chǔ)上+1。求最大匹配的“匈牙利算法”即是此思想：無(wú)論從哪個(gè)匹配開(kāi)始，每一次操作都讓匹配數(shù)+1，不斷擴(kuò)充，直到找不到增廣路徑，此時(shí)便得到最大匹配。

匈牙利算法：

算法的核心就是根據(jù)一個(gè)初始匹配不停的找增廣路，直到?jīng)]有增廣路為止。

匈牙利算法的本質(zhì)實(shí)際上和基于增廣路特性的最大流算法還是相似的，只需要注意兩點(diǎn)：

（一）每個(gè)X節(jié)點(diǎn)都最多做一次增廣路的起點(diǎn)；

（二）如果一個(gè)Y節(jié)點(diǎn)已經(jīng)匹配了，那么增廣路到這兒的時(shí)候唯一的路徑是走到Y(jié)節(jié)點(diǎn)的匹配點(diǎn)（可以回憶最大流算法中的后向邊，，這個(gè)時(shí)候后向邊是可以增流的）。

找增廣路的時(shí)候既可以采用dfs也可以采用bfs，兩者都可以保證O(nm)的復(fù)雜度，因?yàn)槊空乙粭l增廣路的復(fù)雜度是O(m)，而最多增廣n次，dfs在實(shí)際實(shí)現(xiàn)中更加簡(jiǎn)短。

匈牙利算法的基本模式：

1、 初始時(shí)最大匹配為空

2、 while （找得到增廣路徑）

3、 do  把增廣路徑加入到最大匹配中。

如果二分圖的左半邊一共有n個(gè)點(diǎn)，最多找n條增廣路徑，如果圖中有m條邊，每一條增廣路徑把所有邊遍歷一遍，所以時(shí)間復(fù)雜度為O（n*m）;

算法思想： 

算法的思路是不停的找增廣軌, 并增加匹配的個(gè)數(shù),增廣軌顧名思義是指一條可以使匹配數(shù)變多的路徑,在匹配問(wèn)題中,增廣軌的表現(xiàn)形式是一條"交錯(cuò)軌",也就 是說(shuō)這條由圖的邊組成的路徑, 它的第一條邊是目前還沒(méi)有參與匹配的,第二條邊參與了匹配,第三條邊沒(méi)有..最后一條邊沒(méi)有參與匹配,并且始點(diǎn)和終點(diǎn)還沒(méi) 有被選擇過(guò).這樣交錯(cuò)進(jìn)行,顯然 他有奇數(shù)條邊.那么對(duì)于這樣一條路徑,我們可以將第一條邊改為已匹配,第二條邊改為未匹配...以此類(lèi)推.也就是將所有 的邊進(jìn)行"反色",容易發(fā)現(xiàn)這樣修 改以后,匹配仍然是合法的,但是匹配數(shù)增加了一對(duì).另外,單獨(dú)的一條連接兩個(gè)未匹配點(diǎn)的邊顯然也是交錯(cuò)軌.可以證明, 當(dāng)不能再找到增廣軌時(shí),就得到了一個(gè) 最大匹配.這也就是匈牙利算法的思路.、

二分圖匹配中較為重要的三個(gè)公式：

二分圖最小頂點(diǎn)覆蓋 = 二分圖最大匹配；

DAG圖的最小路徑覆蓋 = 節(jié)點(diǎn)數(shù)（n）- 最大匹配數(shù)；

二分圖最大獨(dú)立集 = 節(jié)點(diǎn)數(shù)（n）- 最大匹配數(shù)；

模版：

#include 

  本文關(guān)鍵詞：匈牙利算法，由筆耕文化傳播整理發(fā)布。