二分圖：簡(jiǎn)單來(lái)說(shuō)，如果圖中點(diǎn)可以被分為兩組，并且使得所有邊都跨越組的邊界，則這就是一個(gè)二分圖。準(zhǔn)確地說(shuō)：把一個(gè)圖的頂點(diǎn)劃分為兩個(gè)不相交集 U 和 V ，使得每一條邊都分別連接 U、V 中的頂點(diǎn)。如果存在這樣的劃分，則此圖為一個(gè)二分圖。二分圖的一個(gè)等價(jià)定義是：不含有「含奇數(shù)條邊的環(huán)」的圖。圖1 是一個(gè)二分圖。為了清晰，我們以后都把它畫成圖2的形式。

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

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

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

完美匹配：如果一個(gè)圖的某個(gè)匹配中，所有的頂點(diǎn)都是匹配點(diǎn)，那么它就是一個(gè)完美匹配。圖4是一個(gè)完美匹配。顯然，完美匹配一定是最大匹配（完美匹配的任何一個(gè)點(diǎn)都已經(jīng)匹配，添加一條新的匹配邊一定會(huì)與已有的匹配邊沖突）。但并非每個(gè)圖都存在完美匹配。

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

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

交替路：從一個(gè)未匹配點(diǎn)出發(fā)，依次經(jīng)過(guò)非匹配邊、匹配邊、非匹配邊…形成的路徑叫交替路。

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

增廣路有一個(gè)重要特點(diǎn)：非匹配邊比匹配邊多一條。因此，研究增廣路的意義是改進(jìn)匹配。只要把增廣路中的匹配邊和非匹配邊的身份交換即可。由于中間的匹配節(jié)點(diǎn)不存在其他相連的匹配邊，所以這樣做不會(huì)破壞匹配的性質(zhì)。交換后，圖中的匹配邊數(shù)目比原來(lái)多了1條。

我們可以通過(guò)不停地找增廣路來(lái)增加匹配中的匹配邊和匹配點(diǎn)。找不到增廣路時(shí)，達(dá)到最大匹配（這是增廣路定理）。匈牙利算法正是這么做的。在給出匈牙利算法DFS和BFS版本的代碼之前，先講一下匈牙利樹(shù)。

匈牙利樹(shù)一般由BFS構(gòu)造（類似于BFS樹(shù)）。從一個(gè)未匹配點(diǎn)出發(fā)運(yùn)行BFS（唯一的限制是，必須走交替路），直到不能再擴(kuò)展為止。例如，由圖7，可以得到如圖8的一棵BFS樹(shù)：

這棵樹(shù)存在一個(gè)葉子節(jié)點(diǎn)為非匹配點(diǎn)（7號(hào)），但是匈牙利樹(shù)要求所有葉子節(jié)點(diǎn)均為匹配點(diǎn)，因此這不是一棵匈牙利樹(shù)。如果原圖中根本不含7號(hào)節(jié)點(diǎn)，那么從2號(hào)節(jié)點(diǎn)出發(fā)就會(huì)得到一棵匈牙利樹(shù)。這種情況如圖9所示（順便說(shuō)一句，圖8中根節(jié)點(diǎn)2到非匹配葉子節(jié)點(diǎn)7顯然是一條增廣路，沿這條增廣路擴(kuò)充后將得到一個(gè)完美匹配）。

下面給出匈牙利算法的DFS和BFS版本的代碼：

// 頂點(diǎn)、邊的編號(hào)均從 0 開(kāi)始
// 鄰接表儲(chǔ)存

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] 存儲(chǔ)頂點(diǎn) i 出發(fā)的邊的編號(hào) */
vector<Edge> edges;
typedef vector<int>::iterator iterator_t;
int num_nodes;
int num_left;
int num_right;
int num_edges;
int matching[__maxNodes]; /* 存儲(chǔ)求解結(jié)果 */
int check[__maxNodes];

bool dfs(int u)
{
    for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 對(duì) u 的每個(gè)鄰接點(diǎn)
        int v = edges[*i].to;
        if (!check[v]) {     // 要求不在交替路中
            check[v] = true; // 放入交替路
            if (matching[v] == -1 || dfs(matching[v])) {
                // 如果是未蓋點(diǎn)，說(shuō)明交替路為增廣路，則交換路徑，并返回成功
                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 為路徑起點(diǎn)
            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) { // 此點(diǎn)為匹配點(diǎn)
                            prev[matching[v]] = u;
                        } else { // 找到未匹配點(diǎn)，交替路變?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;
}

匈牙利算法的要點(diǎn)如下

（1）從左邊第1個(gè)頂點(diǎn)開(kāi)始，挑選未匹配點(diǎn)進(jìn)行搜索，尋找增廣路。

a. 如果經(jīng)過(guò)一個(gè)未匹配點(diǎn)，說(shuō)明尋找成功。更新路徑信息，匹配邊數(shù)+1，停止搜索。

b. 如果一直沒(méi)有找到增廣路，則不再?gòu)倪@個(gè)點(diǎn)開(kāi)始搜索。事實(shí)上，此時(shí)搜索后會(huì)形成一棵匈牙利樹(shù)。我們可以永久性地把它從圖中刪去，而不影響結(jié)果。

（2）由于找到增廣路之后需要沿著路徑更新匹配，所以我們需要一個(gè)結(jié)構(gòu)來(lái)記錄路徑上的點(diǎn)。DFS版本通過(guò)函數(shù)調(diào)用隱式地使用一個(gè)棧，而BFS版本使用 prev 數(shù)組。

性能比較

兩個(gè)版本的時(shí)間復(fù)雜度均為O(V?E)。DFS 的優(yōu)點(diǎn)是思路清晰、代碼量少，但是性能不如 BFS。我測(cè)試了兩種算法的性能。對(duì)于稀疏圖，BFS 版本明顯快于 DFS 版本；而對(duì)于稠密圖兩者則不相上下。在完全隨機(jī)數(shù)據(jù) 9000 個(gè)頂點(diǎn) 4,0000 條邊時(shí)前者領(lǐng)先后者大約 97.6%，9000 個(gè)頂點(diǎn) 100,0000 條邊時(shí)前者領(lǐng)先后者 8.6%, 而達(dá)到 500,0000 條邊時(shí) BFS 僅領(lǐng)先 0.85%。

補(bǔ)充定義和定理：

最大匹配數(shù)：最大匹配的匹配邊的數(shù)目

最小點(diǎn)覆蓋數(shù)：選取最少的點(diǎn)，使任意一條邊至少有一個(gè)端點(diǎn)被選擇

最大獨(dú)立數(shù)：選取最多的點(diǎn)，使任意所選兩點(diǎn)均不相連

最小路徑覆蓋數(shù)：對(duì)于一個(gè) DAG（有向無(wú)環(huán)圖），選取最少條路徑，使得每個(gè)頂點(diǎn)屬于且僅屬于一條路徑。路徑長(zhǎng)可以為 0（即單個(gè)點(diǎn)）。

定理1：最大匹配數(shù) = 最小點(diǎn)覆蓋數(shù)（這是 Konig 定理）

定理2：最大匹配數(shù) = 最大獨(dú)立數(shù)

定理3：最小路徑覆蓋數(shù) = 頂點(diǎn)數(shù) - 最大匹配數(shù)