匈牙利算法是由匈牙利數(shù)學(xué)家Edmonds于1965年提出典鸡，因而得名项阴。匈牙利算法是基于Hall定理中充分性證明的思想锌奴，它是部圖匹配最常見的算法兽狭，該算法的核心就是尋找增廣路徑鹿蜀，它是一種用增廣路徑求二分圖最大匹配的算法服球。（來(lái)自百度百科）
淺顯的講，就是尋找二部圖的最大匹配斩熊，先寫出幾個(gè)概念；
二部圖：二分圖又稱作二部圖粉渠，是圖論中的一種特殊模型分冈。 設(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)，則稱圖G為一個(gè)二分圖尤溜。（來(lái)自百度百科）
當(dāng)子圖中沒有任何一個(gè)同時(shí)連接Xi和Yj的同一頂點(diǎn)的時(shí)候我們稱為二部圖的一個(gè)匹配，記為集合M
什么是最大匹配呢 如下圖
當(dāng)匹配集合中的邊數(shù)達(dá)到最大的時(shí)候宫莱，這就是一個(gè)最大匹配丈攒，如上圖；
再提出幾個(gè)個(gè)概念
未覆蓋點(diǎn)：就是在集合M中沒有邊連接到的點(diǎn)稱為未覆蓋點(diǎn)授霸。
完美匹配：當(dāng)M是二部圖的最大匹配且沒有未覆蓋點(diǎn)的時(shí)候肥印，則這個(gè)集合M就是二部圖的完美匹配。上圖中的匹配就是完美匹配绝葡，在符合最大匹配的同時(shí)深碱，M集合中的邊覆蓋了二部圖的所有點(diǎn)。
最后一個(gè)最關(guān)鍵的概念：增廣路徑 藏畅；
匈牙利算法的核心就是不停的尋找增廣路徑來(lái)擴(kuò)充匹配集合M敷硅，什么是增廣路經(jīng)呢功咒？（來(lái)自百度百科）
1－P的路徑長(zhǎng)度必定為奇數(shù)。
2－起點(diǎn)在左绞蹦，終點(diǎn)在右力奋。
3－路徑中的點(diǎn)左右交替出現(xiàn)。
4－只有起點(diǎn)和終點(diǎn)是未覆蓋點(diǎn)幽七，其他點(diǎn)都配對(duì)景殷。
5 -對(duì)增廣路徑編號(hào)，所有奇數(shù)的邊都不在M中澡屡，偶數(shù)邊在M中猿挚。
6 -對(duì)增廣路徑取反得到的匹配比原來(lái)匹配多一個(gè)。
我們給出實(shí)例來(lái)理解驶鹉。
我們尋找如上圖的最大匹配;首先M集合為空（即沒有邊在里面）绩蜻，然后開始從X1尋找增廣路，遵循2的原則我們只能在Yi中找室埋，找到Y(jié)1办绝，（X1，Y1 ）這條路徑姚淆，滿足1-5的條件,取反孕蝉，將（X1，Y1 ）這條路徑加入到M中腌逢。
接著降淮，我們找到X2點(diǎn)，遵循原則上忍，找到Y(jié)1骤肛，Y1不是未覆蓋點(diǎn)，這個(gè)時(shí)候我們有兩種選擇窍蓝，一個(gè)是深度搜索腋颠，一個(gè)是廣度搜索，我們采用深度優(yōu)先吓笙，雖然Y1不是未覆蓋點(diǎn)淑玫，（X2,Y1）不是增廣路面睛，但是Y1連著X1，X1又和Y3相連土涝，我們考慮（ X2,Y1,X1,Y3 ）這條路徑幌墓，奇數(shù)冀泻？左右交替弹渔？起終點(diǎn)未覆蓋溯祸？奇路徑不屬于M偶路徑屬于？滿足所有增廣路條件博杖，所以這是一條增廣路徑氨鹏，然后取反压状，得到如下圖。
現(xiàn)在M集合中的路徑有兩條了镣丑，由于我們找到了增廣路徑莺匠，使得M中的邊數(shù)量增加十兢。所以增廣路徑是匈牙利算法的核心旱物，每找到一條增廣路徑，意味這M集合中邊的數(shù)量就會(huì)增加1单匣，當(dāng)找不到增廣路徑的時(shí)候宝穗，這個(gè)時(shí)候M中邊的數(shù)量就是我們二部圖的最大匹配數(shù)量。我們是怎樣找到這條路徑的呢鸡号，從X2開始尋找须鼎，我們先找到Y(jié)1堪藐，Y1不是未覆蓋點(diǎn)礁竞，我們考慮Y1的原有匹配點(diǎn)X1模捂，從X1開始尋找增廣路蜘矢，找到了Y3，當(dāng)X1有增廣路的時(shí)候岖食，那么加上(X1,Y1)(X2,Y1)這兩條路經(jīng)舞吭，依然滿足增廣路條件。所以基于我們上面的理解可以給出尋找增廣路的偽代碼
while(找到Xi的關(guān)聯(lián)頂點(diǎn)Yj){
if(頂點(diǎn)Yj不在增廣路徑上){
將Yj加入增廣路
if(Yj是未覆蓋點(diǎn)或者Yj的原匹配點(diǎn)Xk能找到增廣路徑){ //擴(kuò)充集合M
將Yj的匹配點(diǎn)改為Xi;
返回true
}
}
返回false
}
從X2開始尋找是基于深度優(yōu)先的蔑穴，如果是基于廣度優(yōu)先呢存和？那么X2就會(huì)找到Y(jié)2衷旅。
給出C語(yǔ)言代碼
typedef struct tagMaxMatch{
int edge[COUNT][COUNT];
bool on_path[COUNT];
int path[COUNT];
int max_match;
}GRAPH_MATCH;
void outputRes(int *path){
for (int i = 0 ; i<COUNT; i++) {
printf("%d****%d\n",i,*(path+i)); //Yj在前 Xi在后
}
}
void clearOnPathSign(GRAPH_MATCH *match){
for (int j = 0 ; j < COUNT ; j++) {
match->on_path[j] = false;
}
}
//dfs算法
bool FindAugPath(GRAPH_MATCH *match , int xi){
for (int yj = 0 ; yj < COUNT; yj++) {
if ( match->edge[xi][yj] == 1 && !match->on_path[yj]) { //如果yi和xi相連且yi沒有在已經(jīng)存在的增廣路經(jīng)上
match->on_path[yj] = true;
if (match->path[yj] == -1 || FindAugPath(match,match->path[yj])) { // 如果是yi是一個(gè)未覆蓋點(diǎn)或者和yi相連的xk點(diǎn)能找到增廣路經(jīng)柿顶，
match->path[yj] = xi; //yj點(diǎn)加入路徑;
return true;
}
}
}
return false;
}
void Hungary_match(GRAPH_MATCH *match){
for (int xi = 0; xi<COUNT ; xi++) {
FindAugPath(match, xi);
clearOnPathSign(match);
}
outputRes(match->path);
}
int main() {
GRAPH_MATCH *graph = (GRAPH_MATCH *)malloc(sizeof(GRAPH_MATCH));
for (int i = 0 ; i < COUNT ; i++) {
for (int j = 0 ; j < COUNT ; j++) {
graph->edge[i][j] = 0;
}
}
graph->edge[0][1] = 1;
graph->edge[0][0] = 1;
graph->edge[1][1] = 1;
graph->edge[1][2] = 1;
graph->edge[2][1] = 1;
graph->edge[2][0] = 1;
graph->edge[3][2] = 1;
for (int j = 0 ; j < COUNT ; j++) {
graph->path[j] = -1;
graph->on_path[j] = false;
}
Hungary_match(graph);
}
