二分图的最大匹配

摘自爱国师哥博客https://www.cnblogs.com/aiguona/p/7665946.html

代码部分摘自《图论算法》

一、概念：

二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 $U$

匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。例如，图 3、图 4 中红色的边就是图 2 的匹配。

Bipartite Graph(1) Bipartite Graph(2) Matching Maximum Matching

在图 3 中 1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。图 4 是一个最大匹配，它包含 4 条匹配边。

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。图 4 是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。但并非每个图都存在完美匹配。

二、算法：

求解最大匹配问题的一个算法是匈牙利算法。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，图 5 中的一条增广路如图 6 所示（图中的匹配点均用红色标出）：

增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。

只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。

我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（这是增广路定理）。

给一个例子
1、起始没有匹配

2、选中第一个x点找第一跟连线

3、选中第二个点找第二跟连线

4、发现x3的第一条边x3y1已经被人占了，找出x3出发的的交错路径x3-y1-x1-y4，把交错路中已在匹配上的边x1y1从匹配中去掉，剩余的边x3y1 x1y4加到匹配中去

5、同理加入x4,x5。

匈牙利算法可以深度有限或者广度优先，刚才的示例是深度优先，即x3找y1,y1已经有匹配，则找交错路。若是广度优先，应为：x3找y1,y1有匹配，x3找y2。

匈牙利算法的要点如下

从左边第 1 个顶点开始，挑选未匹配点进行搜索，寻找增广路。

如果经过一个未匹配点，说明寻找成功。更新路径信息，匹配边数 +1，停止搜索。

如果一直没有找到增广路，则不再从这个点开始搜索。事实上，此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去，而不影响结果。

由于找到增广路之后需要沿着路径更新匹配，所以我们需要一个结构来记录路径上的点。DFS 版本通过函数调用隐式地使用一个栈，而 BFS 版本使用 prev 数组。

补充定义和定理：

(1)二分图的最小顶点覆盖

最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。

Knoig定理：二分图的最小顶点覆盖数等于二分图的最大匹配数。

(2)DAG图的最小路径覆盖

用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。

结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）

(3)二分图的最大独立集

最大独立集问题：在Ｎ个点的图G中选出m个点，使这m个点两两之间没有边．求m最大值

结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）

代码：

1.DFS增广

采用DFS思想搜索可增广路并求出最大匹配的代码如下：

 1 #define MAXN 10
 2 int nx,ny;///x,y集合中点的个数
 3 int maps[MAXN][MAXN];///邻接矩阵
 4 int cx[MAXN],cy[MAXN];///cx[i]表示最终求得的最大匹配中与xi匹配的Y节点
 5 int vis[MAXN];///顶点访问状态数组，1访问过，0未访问过
 6 int path(int u)
 7 {
 8     int v;
 9     for(v=0; v<ny; v++)
10     {
11         if(maps[u][v]&&!vis[v])///u与v邻接并且未被访问过
12         {
13             vis[v]=1;///访问v
14             ///v没有匹配或者v已经匹配了，但从cy[v]出发可以找到一条增光路
15             if(!cy[v]||path(cy[v]))///如果前一个条件成立则不会调用递归
16             {
17                 cx[u]=v;///把v匹配给u
18                 cy[v]=u;///把u匹配个v
19                 return 1;
20             }
21         }
22     }
23     return 0;///不存在从u出发的增广路
24 }
25 int MaxMatch()
26 {
27     int res=0;///所求得的最大匹配
28     int i;
29     memset(cx,0,sizeof(cx));
30     memset(cy,0,sizeof(cy));///初始化为0
31     for(i=0; i<=nx; i++)
32     {
33         memset(vis,0,sizeof(vis));
34         if(path(i))///从未盖点出发寻找增广路
35         {
36             res++;
37         }
38     }
39     return res;
40 }

DFS增广特点：

（1）优点：实现简洁，容易理解。

（2）适用：稠密图，由于边很多，DFS找增广路很快。

（3) 复杂度：O（n^3）。

2.BFS增广

采用BFS思想搜索可增广路并求出最大匹配的代码如下：

 1 #define MAXN 10
 2 int nx,ny;///x,y集合中点的个数
 3 int maps[MAXN][MAXN];///邻接矩阵
 4 int cx[MAXN],cy[MAXN];///cx[i]表示最终求得的最大匹配中与xi匹配的Y节点
 5 int pred[MAXN];///用来记录交错轨，同时也用来记录Y集合中的顶点是佛遍历过
 6 int queue[MAXN];///数组模拟的队列
 7 int MaxMath()
 8 {
 9     int i,j,y;
10     int cur,tail;///表示队列头和尾位置的下标
11     int res=0;///所求得的最大匹配数
12     memset(cx,0,sizeof(cx));
13     memset(cy,0,sizeof(cy));
14     for(i=0;i<nx;i++)
15     {
16         if(!cx[i])
17         {
18             continue;
19         }
20         ///对X集合中每一个未盖点i进行一次BFS找交错轨
21         for(j=0;j<ny;j++)
22         {
23             pred[j]=-2;///-2为初始值
24         }
25         cur=tail=0;
26         for(j=0;j<ny;j++)///把i的邻接点入队列
27         {
28             if(maps[i][j])
29             {
30                 pred[j]=-1;///-1表示遍历到了，是邻接顶点
31                 queue[tail++]=j;
32             }
33         }
34         while(cur<tail)
35         {
36             y=queue[cur];
37             if(!cy[y])///找到了一个未被匹配的点，则找到了一条增广路
38             {
39                 break;
40             }
41             cur++;
42             ///y已经匹配给了cy[y]了,从cy[y]出发，将它的邻接顶点入队列
43             for(j=0;j<ny;j++)
44             {
45                 if(pred[j]==-2&&maps[cy[y]][j])
46                 {
47                     pred[j]=y;
48                     queue[tail++]=j;
49                 }
50             }
51         }
52         if(cur==tail)///没有找到交错轨
53         {
54             continue;
55         }
56         while(pred[y]>-1)///更改交错轨上的匹配状态
57         {
58             cx[cy[pred[y]]]=y;
59             cy[y]=cy[pred[y]];
60             y=pred[y];
61         }
62         cy[y]=i;
63         cx[i]=y;
64         res++;///匹配数+1
65     }
66     return res;
67 }

再给出一个直接调用队列的代码：

 1 int nx,ny;///x,y集合中点的个数
 2 int maps[MAXN][MAXN];///邻接矩阵
 3 int cx[MAXN],cy[MAXN];///cx[i]表示最终求得的最大匹配中与xi匹配的Y节点
 4 int pre[MAXN];///x每一个点的上一个节点
 5 int vis[MAXN];///标志一个点在找增广路的同时是否被访问过
 6 int MaxMatch()
 7 {
 8     int i,j,y;
 9     int res=0;///所求得的最大匹配数
10     memset(cx,0,sizeof(cx));
11     memset(cy,0,sizeof(cy));
12     memset(vis,0,sizeof(vis));
13     for(i=1; i<=nx; i++)
14     {
15         if(!cx[i])
16         {
17             queue<int>q;
18             q.push(i);
19             pre[i]=-1;
20             int flag=0;///标志是否找到了增广路
21             while(!q.empty()&&!flag)
22             {
23                 int u=q.front();
24                 q.pop();
25                 for(int v=1; v<=ny&&!flag; v++)
26                 {
27                     if(maps[u][v]&&vis[v]!=i)
28                     {
29                         vis[v]=i;
30                         q.push(cy[v]);///将于y匹配的x点放入队列
31                         if(cy[v]!=0)///没有增广路
32                         {
33                             pre[cy[v]]=u;///记录x点的顺序
34                         }
35                         else///找到增广路
36                         {
37                             flag=1;
38                             int d=u,e=v;
39                             while(d!=-1)///将原来匹配的边去掉加入原来不在匹配中的边
40                             {
41                                 int t=cx[d];
42                                 cx[d]=e;
43                                 cy[e]=d;
44                                 d=pre[d];
45                                 e=t;
46                             }
47                         }
48                     }
49                 }
50             }
51             if(cx[i]!=0)///新增一个匹配的边
52             {
53                 res++;
54             }
55         }
56     }
57     return res;
58 }

BFS增广特点：

（1）适用：稀松二部图，边少，增广路短。

（2）时间复杂度:O(n^3)。