二分图的最大匹配—匈牙利算法
【基本概念】：
二分圖：
二分圖又稱作二部圖，是圖論中的一種特殊模型。?設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯的兩個頂點i和j分別屬于這兩個不同的頂點集(i?in?A,j?in?B)，則稱圖G為一個二分圖。?
無向圖G為二分圖的充分必要條件是，G至少有兩個頂點，且其所有回路的長度均為偶數。?
最大匹配：
給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配. 選擇這樣的邊數最大的子集稱為圖的最大匹配問題，如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯，則稱此匹配為完全匹配，也稱作完備匹配.??
最小覆蓋：
最小覆蓋要求用最少的點（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點關聯?？梢宰C明：最少的點（即覆蓋數）＝最大匹配數?
最小路徑覆蓋：?
用盡量少的不相交簡單路徑覆蓋有向無環圖Ｇ的所有結點。解決此類問題可以建立一個二分圖模型。把所有頂點i拆成兩個：Ｘ結點集中的i和Y結點集中的i',如果有邊i->j，則在二分圖中引入邊i->j'，設二分圖最大匹配為m,則結果就是n-m。?
增廣路（增廣軌）：
若P是圖G中一條連通兩個未匹配頂點的路徑，并且屬于M的邊和不屬于M的邊(即已匹配和待匹配的邊)在P上交替出現，則稱P為相對于M的一條增廣路徑（舉例來說，有A、B集合，增廣路由A中一個點通向B中一個點，再由B中這個點通向A中一個點……交替進行）。?
增廣路徑的性質：
1?有奇數條邊。
2?起點在二分圖的左半邊，終點在右半邊。
3?路徑上的點一定是一個在左半邊，一個在右半邊，交替出現。（其實二分圖的性質就決定了這一點，因為二分圖同一邊的點之間沒有邊相連，不要忘記哦。）
4?整條路徑上沒有重復的點。
5?起點和終點都是目前還沒有配對的點，而其它所有點都是已經配好對的。
6?路徑上的所有第奇數條邊都不在原匹配中，所有第偶數條邊都出現在原匹配中。
7?最后，也是最重要的一條，把增廣路徑上的所有第奇數條邊加入到原匹配中去，并把增廣路徑中的所有第偶數條邊從原匹配中刪除（這個操作稱為增廣路徑的取反），則新的匹配數就比原匹配數增加了1個。
了解了增廣路的定義以及性質之后，我們仔細理解第7條性質。因為增廣路徑的長度為奇數，我們不妨設為2*K+1，又因為第一條是非匹配邊，且匹配邊與非匹配邊交替出現，所以非匹配邊有K+1條，匹配邊有K條。此時，我們做取反操作，則匹配邊的個數會在原來的基礎上+1。求最大匹配的“匈牙利算法”即是此思想：無論從哪個匹配開始，每一次操作都讓匹配數+1，不斷擴充，直到找不到增廣路徑，此時便得到最大匹配。
匈牙利算法：
算法的核心就是根據一個初始匹配不停的找增廣路，直到沒有增廣路為止。
匈牙利算法的本質實際上和基于增廣路特性的最大流算法還是相似的，只需要注意兩點：
（一）每個X節點都最多做一次增廣路的起點；
（二）如果一個Y節點已經匹配了，那么增廣路到這兒的時候唯一的路徑是走到Y節點的匹配點（可以回憶最大流算法中的后向邊，這個時候后向邊是可以增流的）。
找增廣路的時候既可以采用dfs也可以采用bfs，兩者都可以保證O(nm)的復雜度，因為每找一條增廣路的復雜度是O(m)，而最多增廣n次，dfs在實際實現中更加簡短。
匈牙利算法的基本模式：
1、?初始時最大匹配為空
2、?while?（找得到增廣路徑）
3、?do??把增廣路徑加入到最大匹配中。
如果二分圖的左半邊一共有n個點，最多找n條增廣路徑，如果圖中有m條邊，每一條增廣路徑把所有邊遍歷一遍，所以時間復雜度為O（n*m）;
算法思想：?
算法的思路是不停的找增廣軌,?并增加匹配的個數,增廣軌顧名思義是指一條可以使匹配數變多的路徑,在匹配問題中,增廣軌的表現形式是一條"交錯軌",也就?是說這條由圖的邊組成的路徑,?它的第一條邊是目前還沒有參與匹配的,第二條邊參與了匹配,第三條邊沒有..最后一條邊沒有參與匹配,并且始點和終點還沒?有被選擇過.這樣交錯進行,顯然?他有奇數條邊.那么對于這樣一條路徑,我們可以將第一條邊改為已匹配,第二條邊改為未匹配...以此類推.也就是將所有?的邊進行"反色",容易發現這樣修?改以后,匹配仍然是合法的,但是匹配數增加了一對.另外,單獨的一條連接兩個未匹配點的邊顯然也是交錯軌.可以證明,?當不能再找到增廣軌時,就得到了一個?最大匹配.這也就是匈牙利算法的思路.、
二分圖匹配中較為重要的三個公式：
二分圖最小頂點覆蓋?=?二分圖最大匹配；
DAG圖的最小路徑覆蓋?=?節點數（n）-?最大匹配數；
二分圖最大獨立集?=?節點數（n）-?最大匹配數；
模版：
#include?<iostream>#include?<cstdio>
#include?<cstring>
using?namespace?std;
const?int?N=1001;
int?n1,n2,k;
//n1,n2為二分圖的頂點集,其中x∈n1,y∈n2
int?map[N][N],vis[N],link[N];
//link記錄n2中的點y在n1中所匹配的x點的編號
int?find(int?x)
{
????int?i;
????for(i=1;i<=n2;i++)
????{
????????if(map[x][i]&&!vis[i])//x->i有邊,且節點i未被搜索
????????{
????????????vis[i]=1;//標記節點已被搜索
????????????//如果i不屬于前一個匹配M或被i匹配到的節點可以尋找到增廣路
????????????if(link[i]==0||find(link[i]))
????????????{
????????????????link[i]=x;//更新
????????????????return?1;//匹配成功
????????????}
????????}????????
????}
????return?0;
}
int?main()
{
????int?i,x,y,s=0;
????scanf("%d%d%d",&n1,&n2,&k);
????for(i=0;i<k;i++)
????{
????????scanf("%d%d",&x,&y);
????????map[x][y]=1;
????}
????for(i=1;i<=n1;i++)
????{
????????memset(vis,0,sizeof(vis));
????????if(find(i))
????????????s++;
????}
????printf("%d\n",s);
????return?0;
}
練習題：
POJ 3041 Asteroids? 鏈接：?http://poj.org/problem?id=3041
題意：在某個n*n的空間內，分布有一些小行星，某人在里面打炮，放一槍后某一行或某一列的行星就都沒了，讓求最少的打炮數。
思路：以行號x作為n1點集，列號y作為n2點集，若某位置有行星，則x->y有邊，建立二分圖。?則問題可轉化為，求最少的點覆蓋所有的邊。
根據公式1：?二分圖最小頂點覆蓋?=?二分圖最大匹配
代碼：
?1?#include?<iostream>?2?#include?<cstdio>
?3?#include?<cstring>
?4?using?namespace?std;
?5?const?int?N=1001;
?6?int?n,k;
?7?int?map[N][N],vis[N],link[N];
?8?int?find(int?x)
?9?{
10?????int?i;
11?????for(i=1;i<=n;i++)
12?????{
13?????????if(map[x][i]&&!vis[i])
14?????????{
15?????????????vis[i]=1;
16?????????????if(link[i]==0||find(link[i]))
17?????????????{
18?????????????????link[i]=x;
19?????????????????return?1;
20?????????????}
21?????????}????????
22?????}
23?????return?0;
24?}
25?int?main()
26?{
27?????int?i,x,y,s=0;
28?????scanf("%d%d",&n,&k);
29?????for(i=0;i<k;i++)
30?????{
31?????????scanf("%d%d",&x,&y);
32?????????map[x][y]=1;
33?????}
34?????for(i=1;i<=n;i++)
35?????{
36?????????memset(vis,0,sizeof(vis));
37?????????if(find(i))
38?????????????s++;
39?????}
40?????printf("%d\n",s);
41?????return?0;
42?}
43
代碼：
?1?#include?<iostream>?2?#include?<cstdio>
?3?#include?<cstring>
?4?using?namespace?std;
?5?const?int?N=510;
?6?int?map[N][N],vis[N],link[N];
?7?int?n,m;
?8?int?find(int?x)
?9?{
10?????int?i;
11?????for(i=1;i<=m;i++)
12?????{
13?????????if(!vis[i]&&map[x][i])
14?????????{
15?????????????vis[i]=1;
16?????????????if(!link[i]||find(link[i]))
17?????????????{
18?????????????????link[i]=x;
19?????????????????return?1;
20?????????????}
21?????????}
22?????}
23?????return?0;
24?}
25?int?main()
26?{
27?????int?i,j,s,t,a;
28?????while(~scanf("%d%d",&n,&m))
29?????{
30?????????memset(map,0,sizeof(map));
31?????????memset(link,0,sizeof(link));
32?????????memset(vis,0,sizeof(vis));
33?????????for(i=1;i<=n;i++)
34?????????{
35?????????????scanf("%d",&t);
36?????????????for(j=1;j<=t;j++)
37?????????????{
38?????????????????scanf("%d",&a);
39?????????????????map[i][a]=1;
40?????????????}
41?????????}
42?????????s=0;
43?????????for(i=1;i<=n;i++)
44?????????{
45?????????????memset(vis,0,sizeof(vis));
46?????????????if(find(i))
47?????????????????s++;
48?????????}
49?????????printf("%d\n",s);
50?????}
51?????return?0;
52?}
53
?
POJ 1469 COURSES?
題解：http://www.cnblogs.com/pony1993/archive/2012/08/13/2636394.html?
?
?
POJ 1325 Machine Schedule(二分圖最小點集覆蓋)?
題解：http://www.cnblogs.com/pony1993/archive/2012/08/13/2636916.html
總結
以上是生活随笔為你收集整理的二分图的最大匹配—匈牙利算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 二分图的最大带权匹配
- 下一篇： C++ STL泛型编程——在ACM中的运