這篇文章講無權二分圖（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用於求解匹配的匈牙利演算法（Hungarian Algorithm）；不講帶權二分圖的最佳匹配。

本文摘取自網路，為本人學習相關知識的參考文章，邏輯非常清楚，適合新手學習相關知識，推薦給大家。下文附了原文鏈接及相應代碼，有興趣的可以去原文閱讀。

二分圖：簡單來說，如果圖中點可以被分為兩組，並且使得所有邊都跨越組的邊界，則這就是一個二分圖。準確地說：把一個圖的頂點劃分為兩個不相交集 U 和 V ，使得每一條邊都分別連接U 、 V 中的頂點。如果存在這樣的劃分，則此圖為一個二分圖。二分圖的一個等價定義是：不含有「含奇數條邊的環」的圖。圖 1 是一個二分圖。為了清晰，我們以後都把它畫成圖 2 的形式。

匹配：在圖論中，一個「匹配」（matching）是一個邊的集合，其中任意兩條邊都沒有公共頂點。例如，圖 3、圖 4 中紅色的邊就是圖 2 的匹配。

我們定義匹配點、匹配邊、未匹配點、非匹配邊，它們的含義非常顯然。例如圖 3 中 1、4、5、7 為匹配點，其他頂點為未匹配點；1-5、4-7為匹配邊，其他邊為非匹配邊。

最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。圖 4 是一個最大匹配，它包含 4 條匹配邊。

完美匹配：如果一個圖的某個匹配中，所有的頂點都是匹配點，那麼它就是一個完美匹配。圖 4 是一個完美匹配。顯然，完美匹配一定是最大匹配（完美匹配的任何一個點都已經匹配，添加一條新的匹配邊一定會與已有的匹配邊衝突）。但並非每個圖都存在完美匹配。

舉例來說：如下圖所示，如果在某一對男孩和女孩之間存在相連的邊，就意味著他們彼此喜歡。是否可能讓所有男孩和女孩兩兩配對，使得每對兒都互相喜歡呢？圖論中，這就是完美匹配問題。如果換一個說法：最多有多少互相喜歡的男孩/女孩可以配對兒？這就是最大匹配問題。

基本概念講完了。求解最大匹配問題的一個演算法是匈牙利演算法，下面講的概念都為這個演算法服務。

交替路：從一個未匹配點出發，依次經過非匹配邊、匹配邊、非匹配邊…形成的路徑叫交替路。

增廣路：從一個未匹配點出發，走交替路，如果途徑另一個未匹配點（出發的點不算），則這條交替路稱為增廣路（agumenting path）。例如，圖 5 中的一條增廣路如圖 6 所示（圖中的匹配點均用紅色標出）：

增廣路有一個重要特點：非匹配邊比匹配邊多一條。因此，研究增廣路的意義是改進匹配。只要把增廣路中的匹配邊和非匹配邊的身份交換即可。由於中間的匹配節點不存在其他相連的匹配邊，所以這樣做不會破壞匹配的性質。交換後，圖中的匹配邊數目比原來多了 1 條。

我們可以通過不停地找增廣路來增加匹配中的匹配邊和匹配點。找不到增廣路時，達到最大匹配（這是增廣路定理）。匈牙利演算法正是這麼做的。在給出匈牙利演算法 DFS 和 BFS 版本的代碼之前，先講一下匈牙利樹。

匈牙利樹一般由 BFS 構造（類似於 BFS 樹）。從一個未匹配點出發運行 BFS（唯一的限制是，必須走交替路），直到不能再擴展為止。例如，由圖 7，可以得到如圖 8 的一棵 BFS 樹：

這棵樹存在一個葉子節點為非匹配點（7 號），但是匈牙利樹要求所有葉子節點均為匹配點，因此這不是一棵匈牙利樹。如果原圖中根本不含 7 號節點，那麼從 2 號節點出發就會得到一棵匈牙利樹。這種情況如圖 9 所示（順便說一句，圖 8 中根節點 2 到非匹配葉子節點 7 顯然是一條增廣路，沿這條增廣路擴充後將得到一個完美匹配）。

匈牙利演算法的要點如下

1. 從左邊第 1 個頂點開始，挑選未匹配點進行搜索，尋找增廣路。
   1. 如果經過一個未匹配點，說明尋找成功。更新路徑信息，匹配邊數 +1，停止搜索。
   2. 如果一直沒有找到增廣路，則不再從這個點開始搜索。事實上，此時搜索後會形成一棵匈牙利樹。我們可以永久性地把它從圖中刪去，而不影響結果。
2. 由於找到增廣路之後需要沿著路徑更新匹配，所以我們需要一個結構來記錄路徑上的點。DFS 版本通過函數調用隱式地使用一個棧，而 BFS 版本使用 prev 數組。

性能比較

兩個版本的時間複雜度均為 O(V?E) 。DFS 的優點是思路清晰、代碼量少，但是性能不如 BFS。我測試了兩種演算法的性能。對於稀疏圖，BFS 版本明顯快於 DFS 版本；而對於稠密圖兩者則不相上下。在完全隨機數據 9000 個頂點 4,0000 條邊時前者領先後者大約 97.6%，9000 個頂點 100,0000 條邊時前者領先後者 8.6%, 而達到 500,0000 條邊時 BFS 僅領先 0.85%。

補充定義和定理：

最大匹配數：最大匹配的匹配邊的數目

最大獨立數：選取最多的點，使任意所選兩點均不相連

定理1：最大匹配數 = 最小點覆蓋數（這是 Konig 定理）

原文鏈接以及匈牙利演算法的 DFS 和 BFS 版本的代碼