爱华网一、二分图匹配
图匹配里面最特殊的一种就是二分图匹配，当然，也是算法最简单的一种。
所谓二分图，用最通俗的说法，就是图的顶点恰好可以分成两个集合，同一个集合内的顶点间不允许有边，处在不同集合的顶点允许有边相连。
而二分图匹配，指的是，从整个二分图中选出若干条边，图中的任意一个顶点（对于一个顶点，可能有许多条以该顶点为端点的边，每一条边都为该顶点的连边）至多有一条连边被选取。而边的选取过程，实质上是给顶点进行配对（选取一条边，边的两个端点即完成了配对），因此我们称这个过程为二分图匹配。
说到这里，我们肯定会有一个疑问，如何配对才能得到更多的边？我们称这个求边数最大的问题为最大二分图匹配问题。
1、匈牙利算法
对于最大二分图匹配问题，最基础，代码量最小的算法是匈牙利算法。
在学习匈牙利算法之前，我们先来思考一下一种情况：假如一个二分图当前已经进行了匹配（不是最大匹配），在该二分图中，仍然存在两个未进行匹配但是存在连通路径（路径可以由一条或多条边组成）的点，且在该连通路径上，已经选取的的边与未选取的边交替出现，我们把这种特殊情况下的特殊的连通路径称为增广轨。
对于任意一条增广轨，如果我们把路径上已经选取的边变成未选取，那么很容易发现，之前无法选取的边现在恰好全部可以选取了，而且，更重要的是，增广轨上，路径的头和尾的边均是未选取状态！因此，经过选取与未选取的完全取反（之前已经选取的边全部变成未选取，之前未选取的全部变成选取）以后，该增广轨上匹配数增加了1！！
进行一下推广后，我们便找到了一种计算最大二分图匹配的算法：不断寻找增广轨，并使匹配数增加，直到再也找不到增广轨后，所得的匹配数便是最大二分图匹配。这种算法便是匈牙利算法。
匈牙利算法的正确性：匈牙利算法实质是上一种贪心算法，而对于贪心算法，唯一的问题便是后效性。假如存在Xi和Yj的匹配，后效性即是指Xi和Yj进行匹配以后，由于Yj无法再进行匹配而导致最终的匹配数减少。
思考一下我们便知道，这种后效性并不存在：即使Yj无法再进行匹配，但是由于之前Xi和Yj进行了匹配，总的匹配数并不会减少。
具体做法为：
（1）、对于一个顶点，先判断这个点是否已经匹配，假如没有匹配，则以这个点出发判断是否有增广轨，有的话使匹配数加1。
intret=0;
_clr(xM,-1);
for(inti=0;i<uN;i++)
{
_clr(chk[i])
if(SeachPatch(i))
ret++;
}
returnret;
（2）、判断增广轨的同时，对所有边进行取反操作。
boolSeachPatch(intu)
{
for(inti=0;i<vN,i++)
if(g[u][i]&&!chk[i])
{
chk[i]=1;![图匹配算法[转] opencv 图像匹配算法](http://img.aihuau.com/images/01111101/01035455t01e3d479220c29ddfd.jpg)
if(xM[i]==-1||SeachPatch(xM[i]))
{
xM[i]=u;
return1;
}
}
return0;
}
这个搜索过程的核心是深度优先搜索，以一个未匹配点出发，沿着连通路径一直搜索，直到找到第二个未匹配点为止，而在搜索回溯的过程中，变更点的匹配（即xM的值，xM的值直接确定着该点的匹配对象）在回溯过程中，我们把xM的值进行处理，达到边的取反效果，假如xM[n]=n+1,则我们令xM[n-1]=n，xM[n+1]=n+2。
值得注意的是，我们这种做法并不能直接清空xM[n]的值，只不过由于这个深度优先搜索使用的是间隔搜索法（从函数中可以看出，在连通路径中，u,i,xM[i]是连续的三个点，而进行了搜索递归操作的只是u和xM[i]两个间隔的点），在搜到n-1的时候，会直接跳到n+1继续进行搜索，xM[n]的值被忽略了。这就导致在二分图匹配结束后，我们并不能直接根据xM[n]的值来直接判断每个点的匹配对象。
（3）、当再也找不到增广轨的时候，完成该顶点的操作。
（4）、对于每个顶点，不断重复（1）、（2）、（3）的操作。当所有顶点都遍历一遍以后，最大二分图匹配的结果也就出来了。
算法复杂度：每个顶点寻找增广轨最坏情况下需要遍历所有的边（E），总共V个顶点，所以匈牙利算法的时间复杂度为O(VE)。
2、Hopcroft–Karp算法
匈牙利算法在顶点数较好的稠密图中，时间复杂度相当理想，但是在顶点数较多的稀疏图中，O(VE)的时间复杂度显得不怎么让人放心，这时候，对匈牙利算法的改良势在必行。
匈牙利算法对于一轮的增广轨查找只能找到一条增广轨，而增广轨的查找的时间复杂度是非常高，这显然是导致匈牙利算法低效的主要原因。
那我们思考一下，在一轮增广轨查找中，能否找到多条增广轨？这样就可以极大的降低时间复杂度。
事实是可行的，我们每一轮同时对于所有未匹配顶点的增广轨查找时，然后同时找出所有合法的增广轨（当然，这些增广轨的未匹配部分不允许重合），我们采用之前的增广轨取反法，分别用合适的顶点去匹配这些增广轨，每次匹配都可以给匹配数加1。直到再也找不到可匹配的增广轨，得到的即为最大匹配。这样，我们一轮查找就可以找到多条增广轨，极大提高了效率。
现在剩下的问题就是，如何确定合法的增广轨。比较简洁的办法就是，以未匹配顶点为基点，沿着增广轨的通路依次标上层次，这样就可以在一轮的查找中，寻找到所有合法的增广轨了。而层次图用简单BFS（广度优先搜索）便可实现。
这就是Hopcroft–Karp算法。
具体做法为：
（因为Hopcroft–Karp的优势是在顶点数较多的稀疏图中，因此我们需要用邻接表来代替邻接矩阵。）
（1）、检查所有未匹配顶点，BFS查看是否存在可用的匹配，同时给匹配点编上层次。所有的增广轨不允许相交。
这个是Hopcroft–Karp与匈牙利算法的最大区别。
boolsearchP()
{
queue<int>Q;
dis=INF;
_clr(dx,0);_clr(dy,0);
for(inti=0;i<Nx,i++)
if(xM[i]==-1)
Q.push(i);
while(!Q.empty())
{
intu=Q.front();Q.pop();
if(dx[u]>dis)break;
for(inti=0;i<q[u].size();i++)
if(!dy[q[u][i]])
{
dy[q[u][i]]=dx[u]+1;
if(yM[q[u][i]]==-1)dis=dy[q[u][i]];
else
{
dx[yM[q[u][i]]]=dy[q[u][i]]+1;
Q.push(yM[q[u][i]]);
}
}
}
returndis!=INF;
}
这个实质上是一个非常简单的BFS，初始化时，让所有未匹配点入队列。其中dx记录x集合顶点中的层次数，dy记录y集合顶点中的层次数，不断搜索下去并更新dx和dy的值即可。由于dx与dy的层次数是唯一的（初始值为0时才会更新，当再次搜索到相同匹配点时，值不为0，因此并不会更新），这就保证了增广轨不会相交。某匹配点的层次数取决于离这一点最近的未匹配点。
（2）遍历所有顶点，先判断顶点是否已经匹配，假如没有匹配，则以该顶点点出发判断是否有增广轨，有的话使匹配数加1。
while(searchP())
for(inti=0;i<Nx;i++)
if(xM[i]==-1&&DFS(i))
ret++;
returnret;
与匈牙利算法不同的是，这里每一次都必须遍历所有顶点，因为之前的BFS已经一次性找出多条合法增广轨，我们需要检查哪些顶点是可以匹配新找出的合法的增广轨。
（3）判断增广轨的同时，对所有边进行取反操作。
boolDFS(intu)
{
for(inti=0;i<q[u].size();i++)
if(dy[q[u][i]]==dx[u]+1)
{
dy[q[u][i]]=0;
if(yM[q[u][i]]==-1||DFS(yM[q[u][i]]))
{
xM[u]=q[u][i];
yM[q[u][i]]=u;
return1;
}
}
return0;
}
这里的合法连通路径的判断与匈牙利算法稍有不同，这里需要确定沿着层次数递增1的方向搜索下去。
（4）遍历完所有顶点以后，重复（1）（2）操作。
（5）重复（1）（2）（3）（4）操作，直到再也找不到增广轨可以匹配，则完成该算法。
与匈牙利算法的比较后可以发现，Hopcroft–Karp算法的核心实际上就是匈牙利算法，增广轨的判断，匹配数的检验代码基本都极其类似，只是Hopcroft–Karp算法多了一个优化，就是使用BFS一次寻找多条增广轨，减少判断增广轨的轮次，从而达到时间效率上的优化。
算法复杂度：由于一轮可以查找多条增广轨，因此最坏情况下查找的轮次已经不为V，经过证明，Hopcroft–Karp算法的时间复杂度为O(v^0.5*E)。
二、二分图匹配的应用：
1、二分图的概念：
（1）、最大边独立集：求二分图中的最大边集，该边集内的边互不相交（没有公共顶点），实际上就是最大匹配。
（2）、最大独立集：求二分图中的最大点集，该点集内的点互不相连（没有边相连）。
（3）、最大团：求二分图中的最大点集，该点集内的点两两相连。
（4）、最小支配集：求二分图中的最小点集，使得图中所有顶点要么属于该集合，要么与该集合中的点相邻（即有边相连）。
（5）、最小顶点覆盖：求在二分图中，用最少的点，让所有的边至少与一个顶点有关。
（6）、最小路径覆盖：指一个不含圈的有向图G中，G的一个路径覆盖是一个其结点不相交的路径集合P，图中的每一个结点仅包含于P中的某一条路径。路径可以从任意结点开始和结束，且长度也为任意值，包括0。
2、二分图的性质：
（1）、最小顶点覆盖 = 顶点集 - 最大独立集。
在一个二分图中，从顶点集中去掉最大独立集后，图中所有点边，都肯定会剩下至少一个端点（否则与独立集定义矛盾），剩下的这些顶点，相当于把所有的边都覆盖了，所以剩下的点集是独立集。
而且，剩下的顶点集肯定是满足条件的最小点集。假设不是最小点集，则意味着至少存在一个顶点，该顶点所在的所有边都已被其余顶点覆盖（这个顶点是多余的），那么可以推出，与该顶点所有相邻的点都不在最大独立集内（否则将会被去掉）。但是倒过来想，与该顶点所有相邻的点都不在最大独立集内，意味这这个点是与独立集内的点互不相连，则这个点也可以加入独立集，这与最大独立集定义矛盾。因此剩下的顶点集是满足条件的最小点集。
（2）、最小顶点覆盖 = 最大匹配数。
进行二分图最大匹配的时候，每条边都至少有一个顶点被匹配（假如有一条边没有顶点被匹配，则该边的两个端点进行匹配后会使得匹配数加1，与最大匹配数定义矛盾），因此选定被匹配的顶点后就可以覆盖所有的边。
假设被匹配的顶点并不是满足顶点覆盖的最小集合，则意味着至少存在一个点，这个点所在的边已经被覆盖（这个顶点是多余的），也就是说这个点所在的边有两个端点同时在集合内，这与二分图匹配的定义矛盾（根据二分图匹配的定义，每一条边不允许有两个端点同时参与匹配），因此，被匹配的顶点是满足顶点覆盖的最小集合。
（3）、最小路径覆盖 = 顶点集 - 最大匹配数。
首先需要强调的是，这里所说的最小路径覆盖的对象不再是二分图，而是有向无环图！而最大匹配数是指二分图而言。为了能进行二分图的计算，我们需要将有向图无环转换为二分图。
将有向无环图转换成二分图，通常采用拆点法。将图中的每个点i都拆成两半(Xi和Yi)，分在x和y两个集合里。假如存在i->j的一条边，则将这条边变成Xi->Yj（确定让边的起点都在X集合内，边的终点都在Y集合内）。
经过拆点以后的二分图是一个比较特殊的二分图，因为起点都在同一个集合。因此，并不存在由于被当做终点进行过匹配而导致该顶点无法当做起点。也就是说，只要一个顶点是起点，那么这个顶点肯定能进行匹配，而且要进行匹配必须有起点，因此最大起点数 = 最大匹配数。
我们现在来考虑一下定理。从路径的角度来说，求最小路径覆盖可以转化成求最少路径末尾的顶点数（一条路径有且仅有一个路径末尾），而路径末尾顶点实质上就是没有当成起点的顶点，那么显而易见：最少的路径末尾顶点数等于无法当成起点的顶点数（能当成起点的全当起点了）。由于最大起点数= 最大匹配数，我们只需要求出没有进行过匹配的顶点数，即可求出路径末尾顶点数，进而求出最小路径覆盖。
三、二分图最优权值匹配
之前讨论的二分图匹配，都是只考虑了匹配数，而没有考虑权值（或者说，所有权值都为1），具有相当大的局限性。我们有必要进一步讨论带权的二分图最优匹配。
一个二分图匹配，如果对于任意一个顶点，都有对应的匹配（都有边），我们就称这个匹配为二分图的完全匹配。
对于一般的二分图，并没有什么通用的算法来求解最优权值匹配，而对于有完全匹配的二分图，Kuhn-Munkras则可以比较高效的解决。
1、Kuhn-Munkras算法
Kuhn-Munkras算法的核心思想是贪心。
贪心步骤一：如果最大可匹配边数为1，我们显然选择权值最大的一条边。
贪心步骤二：如果最大可匹配边数为2，我们在步骤一的基础上，挑第二个匹配点中权值最大的。若不存在冲突，则得到的匹配即为最优权值匹配。假如存在冲突，则我们考虑下列两种匹配：（1）第一个匹配点挑选匹配边中权值最大的，第二个匹配点挑选权值次大的。（2）第一个匹配点挑选匹配边中权值次大的，第二个匹配点挑选权值最大的，总权值最大的匹配显然为最优权值匹配。这种根据贪心之后的冲突情况而不断向前修改选择的方法，我们称之为贪心回溯。
贪心步骤三：如果最大可匹配边数为3，我们在步骤二的基础上，继续采用贪心回溯加入第三条边。
贪心步骤四：……
对于这种贪心回溯，平时简单的DFS回溯显然会超时。
Kuhn-Munkras算法的精华便在于，采用可行顶标来进行快速的贪心回溯处理。
对于有完全匹配的二分图，我们定义一个X点集上的函数lx(i)及一个Y点集上的函数ly(j)，使得对于整个二分图的所有边权w（i,j），都有公式lx(i)+ly(j)>=w(i,j)成立，我们称这个lx(i)函数为X顶点集上的可行顶标，ly(j)为Y点集上的可行顶标，两者并称为可行顶标。
而对于任意一个二分图的子图，假如该子图包含原二分图的全部顶点，但只包含边权满足lx(i)+ly(j)=w(i,j)的边，则我们称这个子图为原二分图的相等子图。
如果一个相等子图具有完全匹配，则这个完全匹配就是原二分图的最优权值匹配。
根据lx(i)+ly(j)=w(i,j)，可知相等子图为完全匹配时，该子图的所有可行顶标之和，恰好等于完全匹配中的所有边权之和（根据二分图匹配的定义及完全匹配的定义，任意一条匹配边都对应，并且只对应两个顶点）。对于原图的任意一个子图（不一定包含原图中的所有顶点）已匹配的边权之和，都不大于原图所有顶点的可行顶标之和（因为任意一条边权，两端的可行顶标都满足lx(i)+ly(j)>=w(i,j)，相等子图包含原图的所有顶点，因此，任意一个子图已匹配的边权之和，都不大于任意一个相等子图的所有可行顶标之和。意味着，任意一个子图已匹配的边权之和都不大于具有完全匹配的相等子图的边权之和，显而易见，后者的匹配即为二分图最优权值匹配。
初始化过程中，为了使lx(i)+ly(j)>=w(i,j)成立，对于x点集中的所有点，我们令lx(i)为与点i有关联的边中的最大权值；对y点集中的所有点，我们令ly(j)=0。
for(i=0;i<m;i++)
{
for(lx[i]=-inf,j=0;j<n;j++)
lx[i]=g[i][j]>lx[i]?g[i][j]:lx[i];
if(lx[i]==-inf)return-1;
}
for(i=0;i<n;lx[i++]=0);
g[i][j]为原图的邻接矩阵，x顶点总数为m,y顶点总数为n。
需要注意的是,对于n和m,必须满足n>=m，假如不满足，则交换x，y两个点集。若原图不具有完全匹配，则返回-1。
这样初始化的效果，本质上是将每个待匹配点的的最大权值边加入了相等子图。也就是贪心步骤一。
