（通俗易懂小白入門）二分圖最大匹配——匈牙利算法

• 2019 年 10 月 3 日
• 筆記

二分圖 

先介紹一下什麼是二分圖，二分圖也叫二部圖，設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，並且圖中的每條邊（i，j）所關聯的兩個頂點i和j分別屬於這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖，如下圖所有的頂點可以分成A，B兩個集合，而A集合與B集合中的點與自己的陣營的點是沒有連線的（A集合的點只與B集合的點有邊相連），則稱這個為一個二分圖

而二分圖的最大匹配的含義，就是說在這A，B兩個集合中不斷選擇兩個存在連線（只有存在連線才能連起來，而且每個點只能匹配一次）的兩個點相連，求最多可以有多少條連線即這個二分圖的最大匹配數，對於上面這張圖我們用紅線來演示一下，第一次選擇A1和B1相連，第二次選擇A2和B2相連，第三次發現與A3相連的B1與B2都已經被選擇了，那麼我們需要嘗試給匹配過的點換一個點，看看能不能騰出一個位置給A3，我們先嘗試給A1換一個點，A1還可以與B2相連，但是B2同樣被A2佔用，則我們考慮給A2也換一個點，這樣A1就能換上A2原本的占的B2，而就能將B1騰出來給A3了（這很像是一個遞歸的過程，遞歸騰位置），黃線代表除去的原來的匹配方式，而對於A4我們無論如何都無法修改之前的匹配方式而使得總匹配數量增加，所以這個二分圖的最大匹配就是3

而對於一個點來說，判斷從它出發能否在另一個集合中找到一個頂點使得整張圖的總匹配數增加的過程實際上可以理解為一個找尋增廣路的過程（增廣路不是網絡流的概念嗎？！別著急，聽我簡單給你解釋一下）對於上圖的第二張圖，我們要開始給A3找匹配點的時候，發現B1，B2都被佔用，則開始尋找所謂的增廣路，能找到一條增廣路就能使總匹配數+1，而找增廣路的要旨就是：從A集合中的一個點出發，我們能不斷在兩個集合中找到一個未匹配過的頂點，前提是且他們之間有連線，且滿足連線的過程是，這條邊未匹配過，匹配過，未匹配過，匹配過，未匹配過…（總之邊的數量是奇數，且兩頭都是未匹配過）,如下圖的模擬：從A3出發，A3->B1->A1->B2->A2->B3，邊的顏色為藍（未匹配），紅（匹配），藍（未匹配），紅（匹配），藍（未匹配），滿足上面說的找增廣路的要求（而最後的B3->A4雖然也有一條藍色連線但是此時需要紅色的才能繼續連下去故不選擇），一旦我們找到了增廣路，我們只要將紅藍顏色的連線反轉，就能得到一種總匹配數+1的匹配方式，也就是下面的第二張圖的匹配方式（黃色線就是未匹配的意思，這是它是拆出來的，之前為紅色）

 那麼對於A4這個點來說，我們因為B3已經被佔用了，則我們依舊嘗試取找尋增廣路，從A4->B3->A2->B2->A1->B1->A3，到此為止無法繼續走下去，而邊的顏色為藍（未匹配），紅（匹配），藍（未匹配），紅（匹配），藍（未匹配），紅（匹配），總數為偶數，不滿足開頭結尾為未匹配邊，則無法找到增廣路，此時所有A集合中的頂點用完，二分圖的最大匹配數為3

當然上述用增廣路的概念來解釋這個原理是輔助我們理解這個二分圖的，而關於匈牙利算法的使用，它的計算過程是每一次從A集合中取一個點，將其於B集合中有連線的點依次對照，如果可以相連則將這兩個點連起來，遍歷下一個A集合的點，如果有連線卻已經被A集合中上面的點佔去了，則嘗試給佔去這個Bj的點的Ai換一個有連線未被佔用的點，如果又被佔了則再考慮把佔用的換一個，是一個遞歸的過程（一開始的三張圖我們已經推過一邊了，重點就是讓別人給自己騰位置）

關於具體的講解代碼我們通過一題二分圖最大匹配的模板題 HDU2063來解析

題目描述

RPG girls今天和大家一起去遊樂場玩，終於可以坐上夢寐以求的過山車了。可是，過山車的每一排只有兩個座位，而且還有條不成文的規矩，就是每個女生必須找個個男生做partner和她同坐。但是，每個女孩都有各自的想法，舉個例子把，Rabbit只願意和XHD或PQK做partner，Grass只願意和linle或LL做partner，PrincessSnow願意和水域浪子或偽酷兒做partner。考慮到經費問題，boss劉決定只讓找到partner的人去坐過山車，其他的人，嘿嘿，就站在下面看着吧。聰明的Acmer，你可以幫忙算算最多有多少對組合可以坐上過山車嗎？

輸入

輸入數據的第一行是三個整數K , M , N，分別表示可能的組合數目，女生的人數，男生的人數。0<K<=1000
1<=N 和M<=500.接下來的K行，每行有兩個數，分別表示女生Ai願意和男生Bj做partner。最後一個0結束輸入。

輸出

對於每組數據，輸出一個整數，表示可以坐上過山車的最多組合數。

樣例輸入

6 3 3 1 1 1 2 1 3 2 1 2 3 3 1 0

樣例輸出

3

代碼：

 1 #include<stdio.h>   2 #include<string.h>   3 #include<iostream>   4 using namespace std;   5   6 const int N = 505;   7 int mat[N][N];   8 int boy[N];                    //記錄男孩i被女孩選擇的女孩編號，未被選則0   9 int vis[N];                    //很巧妙的使用，每次記錄男孩i是否被佔用了  10 int k, m, n;  11  12 bool dfs(int x){  13     for(int i = 1; i <= n; i++){        //遍歷所有的男生編號   14         if(mat[x][i] == 1 && vis[i] == 0){    //如果有連線且boy[i]沒有被本次查找遍歷過   15             vis[i] = 1;                        //假設i號boy被遍歷到了   16             if(boy[i] == 0 || dfs(boy[i])){    //如果boy[i]沒有被佔用或者能把佔用boy[i]的人換一個連線，短路原則如果沒有被佔用則不會執行後面的部分   17                 boy[i] = x;                    //這一步的作用是執意要將boy[i]匹配給x(儘可能給騰位置出來，因為她可能佔了別的女生相匹配的男生)          18                 return true;  19             }  20         }  21     }  22     return false;  23 }  24  25 int main(){  26     while(scanf("%d", &k) != EOF){  27         if(k == 0) break;  28         scanf("%d%d", &m, &n);  29         memset(mat, 0, sizeof(mat));  30         memset(boy, 0, sizeof(boy));            //boy[]數組存放的是已經匹配好的方案，如果是0則未匹配   31         for(int i = 1; i <= k; i++){  32             int x, y;  33             scanf("%d%d", &x, &y);  34             mat[x][y] = 1;  35         }  36         int ans = 0;  37         for(int i = 1; i <= m; i++){  38             memset(vis, 0, sizeof(vis));        //vis每一次都將所有的男生編號都標記為沒遍歷過，注意區分vis[]和boy[]數組功能的區別   39             if(dfs(i)) ans++;                    //如果能直接相連或別人騰出位置總數+1   40         }  41         printf("%dn", ans);  42     }  43     return 0;  44 }  45