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

【基本概念】：

二分圖：

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

最大匹配：

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

最小覆蓋：

最小路徑覆蓋： 

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

增廣路（增廣軌）：

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

增廣路徑的性質(zhì)：

1 有奇數(shù)條邊。

2 起點在二分圖的左半邊，終點在右半邊。

3 路徑上的點一定是一個在左半邊，一個在右半邊，交替出現(xiàn)。（其實二分圖的性質(zhì)就決定了這一點，因為二分圖同一邊的點之間沒有邊相連，不要忘記哦。）

4 整條路徑上沒有重復(fù)的點。

5 起點和終點都是目前還沒有配對的點，而其它所有點都是已經(jīng)配好對的。

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

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

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

匈牙利算法：

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

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

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

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

找增廣路的時候既可以采用dfs也可以采用bfs，兩者都可以保證O(nm)的復(fù)雜度，因為每找一條增廣路的復(fù)雜度是O(m)，而最多增廣n次，dfs在實際實現(xiàn)中更加簡短。

匈牙利算法的基本模式：

1、 初始時最大匹配為空

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

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

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

算法思想： 

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

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

二分圖最小頂點覆蓋 = 二分圖最大匹配；

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

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

模版：

#include 

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