用匈牙利算法求二分圖的最大匹配，匈牙利算法
轉載大神的！！
什麼是二分圖，什麼是二分圖的最大匹配，這些定義我就不講了，網上隨便都找得到。二分圖的最大匹配有兩種求法，第一種是最大流（我在此假設讀者已有網絡流的知識）；第二種就是我現在要講的匈牙利算法。這個算法說白了就是最大流的算法，但是它跟據二分圖匹配這個問題的特點，把最大流算法做了簡化，提高了效率。匈牙利算法其實很簡單，但是網上搜不到什麼說得清楚的文章。所以我決定要寫一下。
最大流算法的核心問題就是找增廣路徑（augment path）。匈牙利算法也不例外，它的基本模式就是：
初始時最大匹配為空
while 找得到增廣路徑
do 把增廣路徑加入到最大匹配中去
可見和最大流算法是一樣的。但是這裡的增廣路徑就有它一定的特殊性，下面我來分析一下。
（注：匈牙利算法雖然根本上是最大流算法，但是它不需要建網絡模型，所以圖中不再需要源點和匯點，僅僅是一個二分圖。每條邊也不需要有方向。）
image圖1
image圖2
圖1是我給出的二分圖中的一個匹配：［1，5］和［2，6］。圖2就是在這個匹配的基礎上找到的一條增廣路徑：3->6->2->5->1->4。我們借由它來描述一下二分圖中的增廣路徑的性質：
(1)有奇數條邊。
(2)起點在二分圖的左半邊，終點在右半邊。
(3)路徑上的點一定是一個在左半邊，一個在右半邊，交替出現。（其實二分圖的性質就決定了這一點，因為二分圖同一邊的點之間沒有邊相連，不要忘記哦。）
(4)整條路徑上沒有重復的點。
(5)起點和終點都是目前還沒有配對的點，而其它所有點都是已經配好對的。（如圖1、圖2所示，［1，5］和［2，6］在圖1中是兩對已經配好對的點；而起點3和終點4目前還沒有與其它點配對。）
(6)路徑上的所有第奇數條邊都不在原匹配中，所有第偶數條邊都出現在原匹配中。（如圖1、圖2所示，原有的匹配是［1，5］和［2，6］，這兩條配匹的邊在圖2給出的增廣路徑中分邊是第2和第4條邊。而增廣路徑的第1、3、5條邊都沒有出現在圖1給出的匹配中。）
(7)最後，也是最重要的一條，把增廣路徑上的所有第奇數條邊加入到原匹配中去，並把增廣路徑中的所有第偶數條邊從原匹配中刪除（這個操作稱為增廣路徑的取反），則新的匹配數就比原匹配數增加了1個。（如圖2所示，新的匹配就是所有藍色的邊，而所有紅色的邊則從原匹配中刪除。則新的匹配數為3。）
不難想通，在最初始時，還沒有任何匹配時，圖1中的兩條灰色的邊本身也是增廣路徑。因此在這張二分圖中尋找最大配匹的過程可能如下：
(1)找到增廣路徑1->5，把它取反，則匹配數增加到1。
(2)找到增廣路徑2->6，把它取反，則匹配數增加到2。
(3)找到增廣路徑3->6->2->5->1->4，把它取反，則匹配數增加到3。
(4)再也找不到增廣路徑，結束。
當然，這只是一種可能的流程。也可能有別的找增廣路徑的順序，或者找到不同的增廣路徑，最終的匹配方案也可能不一樣。但是最大匹配數一定都是相同的。
對於增廣路徑還可以用一個遞歸的方法來描述。這個描述不一定最准確，但是它揭示了尋找增廣路徑的一般方法：
“從點A出發的增廣路徑”一定首先連向一個在原匹配中沒有與點A配對的點B。如果點B在原匹配中沒有與任何點配對，則它就是這條增廣路徑的終點；反之，如果點B已與點C配對，那麼這條增廣路徑就是從A到B，再從B到C，再加上“從點C出發的增廣路徑”。並且，這條從C出發的增廣路徑中不能與前半部分的增廣路徑有重復的點。
比如圖2中，我們要尋找一條從3出發的增廣路徑，要做以下3步：
(1)首先從3出發，它能連到的點只有6，而6在圖1中已經與2配對，所以目前的增廣路徑就是3->6->2再加上從2出發的增廣路徑。
(2)從2出發，它能連到的不與前半部分路徑重復的點只有5，而且5確實在原匹配中沒有與2配對。所以從2連到5。但5在圖1中已經與1配對，所以目前的增廣路徑為3->6->2->5->1再加上從1出發的增廣路徑。
(3)從1出發，能連到的不與自已配對並且不與前半部分路徑重復的點只有4。因為4在圖1中沒有與任何點配對，所以它就是終點。所以最終的增廣路徑是3->6->2->5->1->4。
但是嚴格地說，以上過程中從2出發的增廣路徑（2->5->1->4）和從1出發的增廣路徑（1->4）並不是真正的增廣路徑。因為它們不符合前面講過的增廣路徑的第5條性質，它們的起點都是已經配過對的點。我們在這裡稱它們為“增廣路徑”只是為了方便說明整個搜尋的過程。而這兩條路徑本身只能算是兩個不為外界所知的子過程的返回結果。
顯然，從上面的例子可以看出，搜尋增廣路徑的方法就是DFS，可以寫成一個遞歸函數。當然，用BFS也完全可以實現。
至此，理論基礎部份講完了。但是要完成匈牙利算法，還需要一個重要的定理：
如果從一個點A出發，沒有找到增廣路徑，那麼無論再從別的點出發找到多少增廣路徑來改變現在的匹配，從A出發都永遠找不到增廣路徑。
要用文字來證明這個定理很繁，話很難說，要麼我還得多畫一張圖，我在此就省了。其實你自己畫幾個圖，試圖舉兩個反例，這個定理不難想通的。（給個提示。如果你試圖舉個反例來說明在找到了別的增廣路徑並改變了現有的匹配後，從A出發就能找到增廣路徑。那麼，在這種情況下，肯定在找到別的增廣路徑之前，就能從A出發找到增廣路徑。這就與假設矛盾了。）
有了這個定理，匈牙利算法就成形了。如下：
初始時最大匹配為空
for 二分圖左半邊的每個點i
do 從點i出發尋找增廣路徑。如果找到，則把它取反（即增加了總了匹配數）。
如果二分圖的左半邊一共有n個點，那麼最多找n條增廣路徑。如果圖中共有m條邊，那麼每找一條增廣路徑（DFS或BFS）時最多把所有邊遍歷一遍，所花時間也就是m。所以總的時間大概就是O（n * m）。
在UVA上，二分圖匹配的題目有670和10080，祝好運。
以下是我的標程。是用BFS搜索增廣路徑的。雖然DFS可能寫起來比較簡單，但是我不想讓它遞歸很多層。
歡迎使用我的標程。
![]()
/////////////////////////////////////////////////////////////////////
//Bipartite graphic and maximum matching with Hungarian algorithm.
/////////////////////////////////////////////////////////////////////
#include <list>
#include <cstring>
using namespace std;
const int MAX_LEFT = 500;
const int MAX_RIGHT = 500;
class Bipartite {
private:
struct Edge {
int to;
Edge* next;
Edge(int _to) {
to = _to;
}
};
Edge* m_adjList[MAX_LEFT];
int m_lCnt;
int m_rCnt;
int m_lMatchR[MAX_RIGHT];
int m_rMatchL[MAX_LEFT];
int m_preL[MAX_LEFT];
bool m_visitR[MAX_RIGHT];
//This matrix is just used to prevent adding two repeated edges.
bool m_matrix[MAX_LEFT][MAX_RIGHT];
void clear() {
for (int i = 0; i < m_lCnt; i++) {
Edge* e = m_adjList[i];
while (e != NULL) {
Edge* pre = e;
e = e->next;
delete pre;
}
m_adjList[i] = NULL;
}
memset(m_matrix, 0, sizeof(m_matrix));
}
void findAugment(int start) {
for (int i = 0; i < m_lCnt; i++) {
m_preL[i] = -1;
}
memset(m_visitR, 0, sizeof(bool) * m_rCnt);
list<int> que;
que.push_back(start);
bool found = false;
while (!que.empty() && !found) {
int from = que.front();
que.pop_front();
Edge* edge = m_adjList[from];
while (edge != NULL && !found) {
int to = edge->to;
if (!m_visitR[to]) {
m_visitR[to] = true;
if (m_rMatchL[to] == -1) {
found = true;
reverse(from, to);
}
else {
que.push_back(m_rMatchL[to]);
m_preL[m_rMatchL[to]] = from;
}
}
edge = edge->next;
}
}
}
void reverse(int left, int right) {
m_rMatchL[right] = left;
while(m_preL[left] != -1) {
int nextR = m_lMatchR[left];
m_rMatchL[nextR] = m_preL[left];
m_lMatchR[left] = right;
left = m_preL[left];
right = nextR;
}
m_lMatchR[left] = right;
}
public:
Bipartite() {
memset(m_adjList, 0, sizeof(m_adjList));
m_lCnt = 0;
m_rCnt = 0;
}
~Bipartite() {
clear();
}
//Add an edge between vertex "left" and "right" while "left" and "right" are
//the indices of two vertices in the left/right parts of the graph. Indices
//in the left and right parts are separated and they both begin from 0.
void addEdge(int left, int right) {
if (!m_matrix[left][right]) {
m_matrix[left][right] = true;
Edge* newEdge = new Edge(right);
newEdge->next = m_adjList[left];
m_adjList[left] = newEdge;
}
}
//Before invoking this function, "maxMatch()" must be invoked. This function
//returns the index of the matching vertex of "left" while "left" is the
//index of a vertex in the left part of the graphic.
int getLMatchR(int left) const {
return m_lMatchR[left];
}
//See "getLMatchR()", and this function is opposite to it.
int getRMatchL(int right) const {
return m_rMatchL[right];
}
void init(int leftCnt, int rightCnt) {
clear();
m_lCnt = leftCnt;
m_rCnt = rightCnt;
for (int i = 0; i < m_lCnt; i++) {
m_lMatchR[i] = -1;
}
for (int i = 0; i < m_rCnt; i++) {
m_rMatchL[i] = -1;
}
}
int maxMatch() {
for (int i = 0; i < m_lCnt; i++) {
findAugment(i);
}
int result = 0;
for (int i = 0; i < m_lCnt; i++) {
if (m_lMatchR[i] != -1) {
result++;
}
}
return result;
}
};
//Test suites.
#include <iostream>
int main() {
Bipartite match;
match.init(300, 400);
int a[] = {0, 0, 1, 1, 2, 2, 2};
int b[] = {1, 2, 1, 3, 0, 1, 2};
for (int i = 0; i < 7; i++) {
match.addEdge(a[i], b[i]);
}
int maxMatch = match.maxMatch();
cout << maxMatch << " ";
for (int i = 0; i < 3; i++) {
cout << match.getLMatchR(i) << " ";
}
for (int i = 0; i < 4; i++) {
cout << match.getRMatchL(i) << " ";
}
cout << endl;//Correct: 3 2 3 1 -1 2 0 1
return 0;
}
View Code
補充定義和定理：
最大匹配數：最大匹配的匹配邊的數目
最小點覆蓋數：選取最少的點，使任意一條邊至少有一個端點被選擇
最大獨立數：選取最多的點，使任意所選兩點均不相連
最小路徑覆蓋數：對於一個 DAG（有向無環圖），選取最少條路徑，使得每個頂點屬於且僅屬於一條路徑。路徑長可以為 0（即單個點）。
定理1：最大匹配數 = 最小點覆蓋數（這是 Konig 定理）
定理2：最大匹配數 = 最大獨立數
定理3：最小路徑覆蓋數 = 頂點數 - 最大匹配數
