https://www.renfei.org/blog/bipartite-matching.html
這篇文章講無權(quán)二分圖（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用于求解匹配的匈牙利算法（Hungarian Algorithm）；不講帶權(quán)二分圖的最佳匹配。
二分圖：簡單來說，如果圖中點可以被分為兩組，并且使得所有邊都跨越組的邊界，則這就是一個二分圖。準(zhǔn)確地說：把一個圖的頂點劃分為兩個不相交集?UU?和VV?，使得每一條邊都分別連接UU、VV中的頂點。如果存在這樣的劃分，則此圖為一個二分圖。二分圖的一個等價定義是：不含有「含奇數(shù)條邊的環(huán)」的圖。圖 1 是一個二分圖。為了清晰，我們以后都把它畫成圖 2 的形式。
匹配：在圖論中，一個「匹配」（matching）是一個邊的集合，其中任意兩條邊都沒有公共頂點。例如，圖 3、圖 4 中紅色的邊就是圖 2 的匹配。
我們定義匹配點、匹配邊、未匹配點、非匹配邊，它們的含義非常顯然。例如圖 3 中 1、4、5、7 為匹配點，其他頂點為未匹配點；1-5、4-7為匹配邊，其他邊為非匹配邊。
最大匹配：一個圖所有匹配中，所含匹配邊數(shù)最多的匹配，稱為這個圖的最大匹配。圖 4 是一個最大匹配，它包含 4 條匹配邊。
完美匹配：如果一個圖的某個匹配中，所有的頂點都是匹配點，那么它就是一個完美匹配。圖 4 是一個完美匹配。顯然，完美匹配一定是最大匹配（完美匹配的任何一個點都已經(jīng)匹配，添加一條新的匹配邊一定會與已有的匹配邊沖突）。但并非每個圖都存在完美匹配。
舉例來說：如下圖所示，如果在某一對男孩和女孩之間存在相連的邊，就意味著他們彼此喜歡。是否可能讓所有男孩和女孩兩兩配對，使得每對兒都互相喜歡呢？圖論中，這就是完美匹配問題。如果換一個說法：最多有多少互相喜歡的男孩/女孩可以配對兒？這就是最大匹配問題。
基本概念講完了。求解最大匹配問題的一個算法是匈牙利算法，下面講的概念都為這個算法服務(wù)。
交替路：從一個未匹配點出發(fā)，依次經(jīng)過非匹配邊、匹配邊、非匹配邊…形成的路徑叫交替路。
增廣路：從一個未匹配點出發(fā)，走交替路，如果途徑另一個未匹配點（出發(fā)的點不算），則這條交替路稱為增廣路（agumenting path）。例如，圖 5 中的一條增廣路如圖 6 所示（圖中的匹配點均用紅色標(biāo)出）：
增廣路有一個重要特點：非匹配邊比匹配邊多一條。因此，研究增廣路的意義是改進(jìn)匹配。只要把增廣路中的匹配邊和非匹配邊的身份交換即可。由于中間的匹配節(jié)點不存在其他相連的匹配邊，所以這樣做不會破壞匹配的性質(zhì)。交換后，圖中的匹配邊數(shù)目比原來多了 1 條。
我們可以通過不停地找增廣路來增加匹配中的匹配邊和匹配點。找不到增廣路時，達(dá)到最大匹配（這是增廣路定理）。匈牙利算法正是這么做的。在給出匈牙利算法 DFS 和 BFS 版本的代碼之前，先講一下匈牙利樹。
匈牙利樹一般由 BFS 構(gòu)造（類似于 BFS 樹）。從一個未匹配點出發(fā)運行 BFS（唯一的限制是，必須走交替路），直到不能再擴(kuò)展為止。例如，由圖 7，可以得到如圖 8 的一棵 BFS 樹：
這棵樹存在一個葉子節(jié)點為非匹配點（7 號），但是匈牙利樹要求所有葉子節(jié)點均為匹配點，因此這不是一棵匈牙利樹。如果原圖中根本不含 7 號節(jié)點，那么從 2 號節(jié)點出發(fā)就會得到一棵匈牙利樹。這種情況如圖 9 所示（順便說一句，圖 8 中根節(jié)點 2 到非匹配葉子節(jié)點 7 顯然是一條增廣路，沿這條增廣路擴(kuò)充后將得到一個完美匹配）。
下面給出匈牙利算法的 DFS 和 BFS 版本的代碼：
// 頂點、邊的編號均從 0 開始
// 鄰接表儲存
struct Edge
{
? ? int from;
? ? int to;
? ? int weight;
? ? Edge(int f, int t, int w):from(f), to(t), weight(w) {}
};
vector<int> G[__maxNodes]; /* G[i] 存儲頂點 i 出發(fā)的邊的編號 */
vector<Edge> edges;
typedef vector<int>::iterator iterator_t;
int num_nodes;
int num_left;
int num_right;
int num_edges;
int matching[__maxNodes]; /* 存儲求解結(jié)果 */
int check[__maxNodes];
bool dfs(int u)
{
? ? for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 對 u 的每個鄰接點
? ? ? ? int v = edges[*i].to;
? ? ? ? if (!check[v]) {? ? // 要求不在交替路中
? ? ? ? ? ? check[v] = true; // 放入交替路
? ? ? ? ? ? if (matching[v] == -1 || dfs(matching[v])) {
? ? ? ? ? ? ? ? // 如果是未蓋點，說明交替路為增廣路，則交換路徑，并返回成功
? ? ? ? ? ? ? ? matching[v] = u;
? ? ? ? ? ? ? ? matching[u] = v;
? ? ? ? ? ? ? ? return true;
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return false; // 不存在增廣路，返回失敗
}
int hungarian()
{
? ? int ans = 0;
? ? memset(matching, -1, sizeof(matching));
? ? for (int u=0; u < num_left; ++u) {
? ? ? ? if (matching[u] == -1) {
? ? ? ? ? ? memset(check, 0, sizeof(check));
? ? ? ? ? ? if (dfs(u))
? ? ? ? ? ? ? ? ++ans;
? ? ? ? }
? ? }
? ? return ans;
}
queue<int> Q;
int prev[__maxNodes];
int Hungarian()
{
? ? int ans = 0;
? ? memset(matching, -1, sizeof(matching));
? ? memset(check, -1, sizeof(check));
? ? for (int i=0; i<num_left; ++i) {
? ? ? ? if (matching[i] == -1) {
? ? ? ? ? ? while (!Q.empty()) Q.pop();
? ? ? ? ? ? Q.push(i);
? ? ? ? ? ? prev[i] = -1; // 設(shè) i 為路徑起點
? ? ? ? ? ? bool flag = false; // 尚未找到增廣路
? ? ? ? ? ? while (!Q.empty() && !flag) {
? ? ? ? ? ? ? ? int u = Q.front();
? ? ? ? ? ? ? ? for (iterator_t ix = G[u].begin(); ix != G[u].end() && !flag; ++ix) {
? ? ? ? ? ? ? ? ? ? int v = edges[*ix].to;
? ? ? ? ? ? ? ? ? ? if (check[v] != i) {
? ? ? ? ? ? ? ? ? ? ? ? check[v] = i;
? ? ? ? ? ? ? ? ? ? ? ? Q.push(matching[v]);
? ? ? ? ? ? ? ? ? ? ? ? if (matching[v] >= 0) { // 此點為匹配點
? ? ? ? ? ? ? ? ? ? ? ? ? ? prev[matching[v]] = u;
? ? ? ? ? ? ? ? ? ? ? ? } else { // 找到未匹配點，交替路變?yōu)樵鰪V路
? ? ? ? ? ? ? ? ? ? ? ? ? ? flag = true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? int d=u, e=v;
? ? ? ? ? ? ? ? ? ? ? ? ? ? while (d != -1) {
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? int t = matching[d];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? matching[d] = e;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? matching[e] = d;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? d = prev[d];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? e = t;
? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? Q.pop();
? ? ? ? ? ? }
? ? ? ? ? ? if (matching[i] != -1) ++ans;
? ? ? ? }
? ? }
? ? return ans;
}
匈牙利算法的要點如下
從左邊第 1 個頂點開始，挑選未匹配點進(jìn)行搜索，尋找增廣路。
如果經(jīng)過一個未匹配點，說明尋找成功。更新路徑信息，匹配邊數(shù) +1，停止搜索。
如果一直沒有找到增廣路，則不再從這個點開始搜索。事實上，此時搜索后會形成一棵匈牙利樹。我們可以永久性地把它從圖中刪去，而不影響結(jié)果。
由于找到增廣路之后需要沿著路徑更新匹配，所以我們需要一個結(jié)構(gòu)來記錄路徑上的點。DFS 版本通過函數(shù)調(diào)用隱式地使用一個棧，而 BFS 版本使用?prev?數(shù)組。
性能比較
兩個版本的時間復(fù)雜度均為O(V?E)O(V?E)。DFS 的優(yōu)點是思路清晰、代碼量少，但是性能不如 BFS。我測試了兩種算法的性能。對于稀疏圖，BFS 版本明顯快于 DFS 版本；而對于稠密圖兩者則不相上下。在完全隨機數(shù)據(jù) 9000 個頂點 4,0000 條邊時前者領(lǐng)先后者大約 97.6%，9000 個頂點 100,0000 條邊時前者領(lǐng)先后者 8.6%, 而達(dá)到 500,0000 條邊時 BFS 僅領(lǐng)先 0.85%。
補充定義和定理：
最大匹配數(shù)：最大匹配的匹配邊的數(shù)目
最小點覆蓋數(shù)：選取最少的點，使任意一條邊至少有一個端點被選擇
最大獨立數(shù)：選取最多的點，使任意所選兩點均不相連
最小路徑覆蓋數(shù)：對于一個 DAG（有向無環(huán)圖），選取最少條路徑，使得每個頂點屬于且僅屬于一條路徑。路徑長可以為 0（即單個點）。
定理1：最大匹配數(shù) = 最小點覆蓋數(shù)（這是 Konig 定理）
定理2：最大匹配數(shù) = 最大獨立數(shù)
定理3：最小路徑覆蓋數(shù) = 頂點數(shù) - 最大匹配數(shù)
