以下內(nèi)容基本轉(zhuǎn)載自Renfei Song's Blog。

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

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

匹配：在圖論中，一個(gè)「匹配」（matching）是一個(gè)邊的集合，其中任意兩條邊都沒有公共頂點(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è)圖都存在完美匹配。

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

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

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

增廣路：從一個(gè)未匹配點(diǎn)出發(fā)，走交替路，如果途經(jīng)另一個(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ù)目比原來多了 1 條。

我們可以通過不停地找增廣路來增加匹配中的匹配邊和匹配點(diǎn)。找不到增廣路時(shí)，達(dá)到最大匹配（這是增廣路定理）。匈牙利算法正是這么做的。

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

//二分圖匹配（匈牙利算法的DFS實(shí)現(xiàn)）//初始化：g[][]是兩邊頂點(diǎn)的劃分情況，linker[]是該頂點(diǎn)所匹配的結(jié)點(diǎn)//建立g[i][j]表示i->j的有向邊就可以了，是左邊向右邊的匹配//g沒有邊相連則初始化為0//uN是匹配左邊的頂點(diǎn)數(shù)，vN是匹配右邊的頂點(diǎn)數(shù)//調(diào)用：res=hungary();輸出最大匹配數(shù)//優(yōu)點(diǎn)：適用于稠密圖，DFS找增廣路，實(shí)現(xiàn)簡(jiǎn)潔易于理解//時(shí)間復(fù)雜度:O(VE)const int MAXN=510;int uN,vN;//左邊頂點(diǎn)數(shù),右邊頂點(diǎn)數(shù)。int g[MAXN][MAXN];int linker[MAXN];bool used[MAXN];bool dfs(int u)//從左邊開始找增廣路{    int v;    for(v=0;v<vN;v++)//這個(gè)頂點(diǎn)編號(hào)從0開始，若要從1開始需要修改      if(g[u][v]&&!used[v])      {          used[v]=true;          if(linker[v]==-1||dfs(linker[v]))          {//找增廣路，反向              linker[v]=u;              return true;          }      }    return false;//這個(gè)不要忘了，經(jīng)常忘記這句}int hungary(){    int res=0;    int u;    memset(linker,-1,sizeof(linker));    for(u=0;u<uN;u++)    {        memset(used,0,sizeof(used));        if(dfs(u)) res++;    }    return res;}