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

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

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

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

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

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

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

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

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

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

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

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

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

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

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