图匹配总结-二分图匹配.doc

序言：回忆起最初学习图匹配算法的艰辛与困惑，苦中有乐，但很多时间都浪费在了资料的寻找与甄别上。因此，在对自己做一次知识总结的同时，整理与记录下了这些文字，希望能够给大家带来一定的帮助。 目录：第一部分：二分图的最大匹配第二部分：五种方式，两类构图第三部分：二分图匹配算法总结第四部分：二分图的最优权值匹配 第五部分：一般图的最大匹配第六部分：图匹配题目列表符号说明：N,V：点数E：边数u,v,i,j：节点的标号INF：正无穷大-INF：负无穷大名词说明：时间复杂度：算法的理论时间上界时间效率：实际中算法运行的平均时间效率引用说明：文中参考了一些来源于网络的资料，也有原文全段引用的部分。在这些资料被n+1次转载后，我已无法获知所有原作者的信息。在此，对所有前辈们表示真诚的歉意和诚挚的敬意。特别感谢Amber大神犀利的代码。作者：Snow_storm正文：第一部分：二分图匹配有这么两个奇怪的工厂：工厂X只生产杯具，工厂Y只生产洗具 。最近，两个工厂决定将产品实行打包策略：即一个杯具搭配上一个洗具。但由于杯具和洗具的形状和功能各不相同，对于某个类别的杯具来说，只能搭配某些类型的洗具。现在，两个工厂的厂长大人想知道最多能成功的搭配多少对杯具与洗具。类似于上面例子中提到的搭配问题，在图论中的有规范的名称：匹配。注意到，上面的例子中涉及到的物品只有两类（杯具与洗具），且问题只涉及杯具与洗具的匹配，我们把这种只涉及一种关系的匹配问题称为二分匹配问题。现在，让我们理清一些概念。二分图：若图G中的点可以分为X和Y两部分，且每部分内部无任何边相连，则称图G为二分图。匹配：无公共点的边集合（可以想象一下结婚这个词汇）。匹配数：边集中边的个数最大匹配：匹配数最大的匹配。如图1-1，展示的就是一个二分图：粗体线表示该二分图的一种匹配方式，不难发现，此时的匹配已经是最大匹配。XY 图 1-1 如何能得到一个二分图的最大匹配？运用简单的枚举：找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级，时间上通常无法承受。因此，需要寻求一种更加高效的算法。由此便引出了匈牙利算法（hungary），这个算法的名字很有趣，它是由匈牙利数学家Edmonds于1965年提出的。 在正式的讲这个算法之前，不妨想一想，还有什么办法可以比较快速的计算出二分图的最大匹配？没错，网络的最大流算法可以搞定：我们需要增加额外的源汇点S，T，则对于图 1-1我们很容易得到如图1-2所示的网络模型，图中所有的边容量都为1，粗体箭头表示流从该边经过： XYST由此，问题得到了等价的转换：最大匹配数=最大流。若采用sap算法计算最大流，则时间复杂度为O(V2E)，已经有了较高的效率。然则杀鸡焉用宰牛刀，实际上，我们没必要将问题复杂化，针对二分图的特殊性，我们可以采用效率更高，代码量更小的hungary算法解决。 首先，由于匹配中的限制条件是无公共点，所以我们是从点出发，寻找匹配（两个点对应一条边，即一个匹配），而不是直接找边。而hungary算法的实质是贪心:若点ix存在一种匹配jy（即两点之间有连边），若使ix，jy匹配，则至少不会得到更差的解。这种贪心思想正确性显然：如果让ix，jy匹配，且不去改变这个决策，导致的后果就是jy不再能被其它节点匹配，也就是这个决策可能会使匹配数-1，但同时ix，jy匹配一定会使匹配数+1，因此这种匹配至少不会使总匹配数减少。由此我们可以得到如下三个结论：1. 点匹配的先后顺序是任意的（即先匹配ix还是先匹配kx并不会影响结果）。2. 若点ix存在某种匹配jy，不会使匹配数减少（即不影响已经匹配的点），则点ix一定要被匹配。3. 反之，若点ix在第一验证时，不存在上述的匹配，则该点在以后也一定无法再找到上述匹配。 如果可以检验出当ix匹配jy时不会影响到已经匹配的点，那么我们就能得到计算最大匹配的一种方法：从任意点开始，若存在某种匹配使得该匹配不会影响之前的匹配，则匹配数+1，并且记录下该匹配。找下一个未尝试过的点，直到所有的点都被遍历过。 现在问题的关键就是如何检验：对于二分部的Y部分，令数组match表示Y部分的点在X部分对应匹配（例如当ix与jy匹配时，有matchjy=ix）。初始时，match都设为-1，即所有的点都还没有被匹配过，而没有被匹配过的点通常称之为未盖点。当验证ux，时，我们可以遍历它所有可能的匹配点vy（即与ux有连边的点），若matchvy=-1，显然ux与uy的匹配不会使之前的匹配减少，故ux一定要被匹配，且记matchvy=vx；若matchvy -1，那么我们知道vy之前匹配的点是matchvy，同样是X部分的点，处理方式必然等价，故不难想到，可以采用递归的方式对matchvy做相同的处理（其实就是在检验是否能通过修改之前的匹配方案，使得原来的匹配点仍旧都有匹配，即匹配数不减少，而冲突却被调和了）。 由此，我们得到了如下的hungary算法流程：1. 初始化匹配数cnt为0，标记数组match为-1。2. 若点ix是没有被遍历过，则执行3，否则执行5。3. 寻找该点可能的所有匹配点jy，若matchjy=-1，则执行4，否则把当前点ix设置为matchjy，继续执行3。若没有执行过4，则执行5。4. cnt+1，matchjy=ix，执行5。5. 寻找下个未遍历的点，若所有点都被遍历过，则算法结束，当前的cnt即为最大匹配数。实际上，上述验证的方式完全等价于在验证图中是否存在增广路（也称为交错轨）或者说二分图增广路的定义是为了采用更规范的阐述，用来表达实际效果。注意这里提到的二分图增广路和网络流中的增广路的异同：相同点：1.路径都可以在后面的决策中修改，从而使得答案逐渐趋于最大；2.当图中不存在增广路径时，便得到了最终答案。不同点：网络流的增广路的起点一定是源点S，终点一定是汇点T，对于增广路上的边，只要求剩余容量不为0。而二分图的增广路，起点和终点必须是未盖点，对于增广路上的边，从起点开始，边从划分来讲必须严格按照属于匹配边，不属于匹配边，属于匹配边.的这种方式，从数目来讲，边数必须是奇数。对于这样的增广路，如果进行取反操作（即匹配边变成非匹配边，非匹配边变为匹配边），可以发现匹配仍旧合法，但匹配数却增加了1。则hungary的算法流程可变为：1. 初始化匹配数cnt为1。2. 在图中寻找增广路，若无法找到任何增广路，则执行4，否则执行3。3. 将增广路的首尾两点设置为非未盖点，且将增广路上的边进行取反操作，cnt+1，执行2。4. 算法结束，当前的cnt即为最大匹配数。对于上面提到的方法，用图 1-3的具体计算来展示其实现的过程：（红色粗体边，表示匹配边；黑色细体边，表示未匹配边。天蓝色的点表示未盖点；靛蓝色的点表示非未盖点。且设节点编号0）X1X2X3Y1Y2Y3 X1X2X3Y1Y2Y3X1X2X3Y1Y2Y3 X1X2X3Y1Y2Y3 图1-3 初始时，match都设为-1。因为可以从任意点开始匹配，则不妨按照点的编号顺序开始。对于X1，可以找到Y2与之匹配，且令matchY2=X1。同样的，对于X2，可以找到Y3与之匹配，且令matchY3=X2。当验证X3时，会发现唯一能够与其匹配的点Y3已经被匹配过了，则尝试修改之前的匹配方案：可以找到X2还可以与Y2匹配，但是同样的matchY2=X1-1，于是再去寻找X1是否能有新的匹配；可以发现X1还可以与Y1匹配，且matchY1=-1，则令matchY1=X1，matchY2=X2，matchY3=X3。得到了最终的最大匹配数=3。 上面这段话描述的是算法具体的操作步骤，现在不妨从增广路的角度来考虑：初始时，所有的点都是未盖点，匹配数cnt=0；我们很容易找到一条增广路X1-Y2，进行取反操作后，边(X1,Y2)由非匹配边变成了匹配边，cnt+1=1，且X1，Y2变成了非未盖点；继续寻找，我们也很容易的找到了增广路X2-Y2，进行取反操作后，边(X2,Y3)由非匹配边变成了匹配边，cnt+1=2，且X2，Y3变成了非未盖点。最后，可以找到增广路X3-Y3-X2-Y2-X1-Y1，同样进行取反操作，累加匹配数：cnt+1=3，同时X1，Y1也变成了非未盖点。注意到此时图中已经不存在任何增广路了，即该图的最大匹配数为3。 注意到，我采用讲述方法类似于倒叙：先给出算法本质与具体操作方法，再从一般的规范性概念进行重复的对比阐述。而通常的学习方式是：“是什么”-“为什么”-“怎么样”。个人感觉这种先学习庞大概念的方法不太适宜思维的锻炼，且往往在看过一堆理论叙述后，还是一头雾水，举步维艰。因此我把“是什么”中较难懂的概念都挪到了“怎么样”之后，再进行阐述。同时希望这种学习方式，能给予大家帮助与启发。最终，我们得到了hungary算法的代码实现：#define MAXN 500 /X部分的最大顶点数#define MAXM 500 /Y部分的最大顶点数#define _clr(x,y) memset(x,y,sizeof(x)int n,m;int matchMAXM; /标记数组int gMAXNMAXM; /邻接矩阵bool usedMAXM; /判重bool find(int k) /dfs寻找增广路for(int i=1;im;i+)if(gki & !usedi)usedi=true;if(matchi=-1 | find(matchi)matchi=k;return true;return false; int hungary()int cnt=0;_clr(match,-1);for(int i=1;i匹配-未匹配.，的原则标记途中经过的顶点，则最后一条经过的边必定为匹配边。重复上述过程，直到右边不再含有未匹配边的点。记得到的左边已标记的点和右边未标记的点为S， 以下证明S即为所求的最小顶点集。1| S | = M 显然，左边标记的点全都为匹配边的顶点，右边未标记的点也为匹配边的顶点。因此，我们得到的点与匹配边一一对应。2S能覆盖G中所有的边。上途S中点所得到的边有以下几种情况：（1）左右均标记；（2）左右均无标记；（3）左边标记，右边未标记；若存在一条边e不属于S所覆盖的边集，则e 左边未标记右边标记。如果e不属于匹配边，那么左端点就可以通过这条边到达（从而得到标记）；如果e属于匹配边，那么右端点不可能是一条路径的起点，于是它的标记只能是从这条边的左端点过来的左端点就应该有标记。3S是最小的覆盖。因为要覆盖这M条匹配边至少就需要M个点。 综合几点可得最小点覆盖数 = 最大匹配数。这个结论便是著名的Konig定理。 最小路径覆盖数 = 顶点集数 - 最大匹配数 简单的证明：由二分图的性质易知：二分图中路径的长度只能是1（路径是一条边，两个顶点），或者0（路径是单个顶点）。因此在满足路径覆盖所有的顶点与任意路径不存在公共点的前提下，路径覆盖数 = 边数 + 点数。对于没有公共点的边集而言，不正是匹配的定义吗？同样的，与匹配边没有公共点的单个顶点正是未匹配点。因此，路径覆盖数 = 匹配数 + 未匹配顶点数；又因为，未匹配顶点数 = 顶点集数 - 匹配数 * 2 ，因此 路径覆盖数 = 顶点集数 - 匹配数。故最小路径覆盖数 = 顶点集数 - 最大匹配数。 从另一个角度出发，路径覆盖数实际上等于路径结尾的顶点数（即每条路径的最后一个节点），容易得到： 路径覆盖数 = 路径结尾顶点数 = 顶点数 非路径结尾顶点数。因此有，最小路径覆盖数 = 最小路径结尾顶点数 = 顶点数 最大非路径结尾顶点数。 结合之前的最小路径覆盖数 = 顶点集数 - 最大匹配数，我们可知：在二分图中，最大匹配数 = 最大非路径结尾顶点数。这个结论的具体分析与应用，将在下文的第一个例题中展示。 由于一般图的最大独立集是NPC问题，因此对于一般图来说，目前还没较好好的算法解决最大独立集、最小点覆盖、最大团、最小支配集问题。不过对于某些特殊的情况，有着对应的解决方法存在，例如:对于树型图的最小支配集，我们可以采用树状DP计算。对于二分图来说，我们拥有hungary等优秀的算法计算最大匹配数，因此对于二分图来说，上诉问题中除了最小支配集外，其它得都可以等价的转换为二分图匹配问题。 假设原图的共有N个顶点，最大匹配数为K；补图的最大匹配数为K，则有：最大独立集 = N - K最大团 = N - K最小点覆盖 = K最小路径覆盖 = N - K 于是，在二分匹配问题中，有着最常见的这五种考察方式：求最大匹配数，求最大独立集，求最大团，求最小点覆盖或求最小路径覆盖。对于第一种匹配问题，我们可以直接采用二分匹配算法解答；而对于后四种问题，我们可以先将其等价转换，且建立对应的二分图模型，而后同样的用二分匹配算法解答之。 在实际问题中，通常我们又会遇到两类构图：1.二分集合明显，即划分关系明确的。2.二分集合难以区分，即划分关系不明确的。 对于第一类，很好理解，即对于图中的点，我们很容易知道它是属于X部分，还是属于Y部分。此时，我们可以将边关系定为有向的（通常是X-Y），计算出的最大匹配数即为所求。 而对于第二类，虽然图满足二分图的定义，但对于图中的点，我们无法，或很难确定它到底应该属于X部分，还是属于Y部分。此时，我们可以将边关系定为无向的，则对 该图计算最大匹配后，得到的答案是真正最大匹配的两倍（因为i匹配了一次j，而j又重复匹配了一次i）。 下面针对两类构图各举一例：划分关系明确的构图： 以pku 1422 Air Raid 为例：l 给定一个有向无环图l 伞兵可以投放在任意节点，但只能沿一条路走l 需要将图中所有的点都覆盖问最小需要投放几个伞兵。 容易看出，这题是很明显的最小路径覆盖问题。但麻烦之处在于题目给出的是有向无环图，而不是二分图。对于二分图的最小路径覆盖，已经有了很简单的转换方法。于是在想不出其它办法时，我们尝试是否能在不违背题目要求的前提下，将有向无环图转换为二分图。将普通图转换成二分图，通常的做法就是拆点：将点i拆成i与i，对于原图中的边(i,j)，在二分图中引入边(i,j)。例如，对于图 2-2，经过变换之后，得到图 2-3。V1V2V3V4V5 V1V2V3V4V5V1V2V3V4V5图 2-2 图 2-3有了如上的转变后，我们不难验证：原图中的路径覆盖能与该二分图中的匹配一一对应，例如对于原图中的路径(V1,V2,V3)，则对应着二分图中的(V1,V2)和(V2,V3)这两个匹配。又因为路径覆盖中的每条路径除了最后一个节点之外都有唯一的后继和它对应（即匹配节点），因此二分图的匹配边数就等于非路径结尾的顶点数。结合前文，我们可以得到：路径覆盖数 = 顶点数 非路径结尾顶点数 = 顶点数 匹配数。因此，最小路径覆盖数 = 顶点数 最大匹配数。 于是我们可以计算出新构建二分图的最大匹配K ，则所求即为N-K 。 需要注意，划分关系明确和二分图模型明确是两个概念：二分图模型明确通常是指在构建二分图模型时非常容易。而划分关系明确是指建立的二分图模型很容易将原图中的点划分为二分图的两部分。正如我举的这个例题，其二分图模型并不那么容易确定，但在正确的建立二分图模型后，很自然的得到了点的划分关系（或者说此题二分图的第二部分实际上是我们利用拆点得到的，我们自然可以将原图的点归为第一部分）。 如果读到这里，仍旧对第二类构图很模糊，那么相信看了下面这个例题，你将会有个比较清晰的认识。划分关系不明确的构图： 以 pku 3020 Antenna Placement 为例：l 对于网格图的笛卡尔坐标系，给出若干坐标(x,y)，表示该点需要被天线覆盖。l 若天线装置放置在(x0,y0)处，则该天线可以覆盖(x0,y0)与(x0+1,y0),(x0-1,y0),(x0,y0+1),(x0,y0-1)四个中的一个。问最少用几个天线装置，可以覆盖全部给定的坐标。 稍加分析，可知天线实际上只能够覆盖一条边，或者单个顶点。故，此题也是最小路径覆盖问题。 接下来检验该图的模型是否是二分图，用反证法：假设该图不是二分图，则必然存在三个坐标(x0,y0)，(x1,y1)与(x2,y2)两两之间都有连边，又因为能与(x0,y0)有连边的点只可能是(x0+1,y0) , (x0-1,y0) , (x0,y0+1) 或 (x0,y0-1)。而显然这四个点之间不可能会有边存在，即(x1,y1)与(x2,y2)间不可能会有连边，与假设矛盾。因此该图的模型是二分图。（如果把坐标移到网格中，则对网格图作类似于国际象棋的黑白格染色，会有更直观的感受） 虽然我们可以确定该图是二分图模型，但具体到哪个点是属于X部分，哪个点是属于Y部分，我们却无法确定。因此，我们采用前面提到的方法，将边关系建立为无向的，若得到的最大匹配数为K，则所求即为 N - K/2 。 二分图构图的特点是：先根据题意确定考察点，然后再判断构造的图模型是否是二分图，或者能否转换为二分图，然后根据划分关系是否明确来定性边有无方向。最后，用二分图匹配算法解决之。第三部分：二分图匹配算法总结一：特殊的增广路算法 1. Hungary一般采用dfs递归实现寻找增广路。时间复杂度是O(VE)，时间效率较好。2. Hopcroft_Karp 基于Hungary算法的改进，每次寻找若干条结点不相交最短增广路，即每次沿多条增广路同时增广。时间复杂度是O(V1/2E)，时间效率较好。二：各种网络最大流算法 由于我的另外一篇文章对最大流算法已经有了较详细的介绍，这里就不再进行累述了。首先，介绍下Hungary算法的一个优化办法：贪心一个初始匹配。所谓初始匹配，其实就是花O(E)的时间进行一次任意匹配，当然匹配要合法。加了这个优化的Hungary算法的实际效率就变得更高了。事实的确如此，从时间复杂度对比和目前经验来看，比赛中一般没有什么题能卡贪心初始的匈牙利的。但注意到Hopcroft_Karp算法实际是基于Hungary算法的改进，因此学习该算法并没有什么太大的难度。开阔视野的同时，又拥有了双重保险，何乐而不为。 接下来，正式介绍Hopcroft_Karp算法：回忆匈牙利算法：算法一共进行V轮，每一轮都从左部的一个未遍历点开始查找增广路，每次查找花费O(E)的时间。改进的思想是一次性找到多条增广轨，这样就可以减少算法进行的轮数，可以证明Hopcroft_Karp算法只需进行O(V1/2) 轮，而每轮寻找不相交最短增广路所花费的时间同样是O(E) 。因此匈牙利算法得到了改进。给出算法描述如下：设初始匹配M为空；每一轮用当前图中的所有未匹配点求出相对于M的节点不相交最短增广轨集合P，如果P为空，则M此时已经是最大匹配，否则用P中的每条增广轨扩展M。 因此现在的任务就是如何找出：相对于M的节点不相交最短增广轨集合P。对于节点不相交，只需将已找过的节点标记即可；而路径最短的实现办法当然是用BFS计算层次图（层次图的概念已在另一篇网络流里有过较详细的介绍，这里就不再累述）；然后利用类似于Hungary算法中的DFS沿层次图寻找增广路。反复迭代，直到某次BFS已经找不到增广路。 最终，我们得到了Hopcroft_Karp的算法流程：1. 初始化匹配数cnt为0，matchx,matchy为-1 。2. 对于所有还未找到匹配的点，利用BFS计算其层次图，且层次图上的任意路径，节点不相交。若找不到增广路，则执行4，否则执行3 。3. 遍历X部分所有的点，若matchx=-1，则用DFS尝试能否找到增广路径。若能，则cnt+1，macthx修改为对于匹配点。遍历结束后，执行2 。4. 算法结束，此时的cnt即为最大匹配数。在给出具体的程序实现前，我先引入一段维基百科全书的HopcroftKarp算法的英文原文介绍，对于我上面的讲述有不理解之处或者想更深入了解此算法的读者，可以仔细的阅读下面这段文字。当然，你也完全可以选择跳过它。HopcroftKarp algorithmFrom Wikipedia, the free encyclopedia(Redirected fromHopcroft Karp)Incomputer science, theHopcroftKarp algorithmis analgorithmthat takes as input abipartite graphand produces as output a maximum cardinalitymatching a set of as many edges as possible with the property that no two edges share an endpoint. It runs in O(mn) time in theworst case, where O refers tobig O notation,mis the number of edges in the graph, andnis the number of vertices of the graph. In the case ofdense graphsthe time bound becomes O(n5/2), and forrandom graphsit runs in near-linear time.The algorithm was found byJohn HopcroftandRichard Karp(1973). As in previous methods for matching such as theHungarian algorithmand the work ofEdmonds (1965), the HopcroftKarp algorithm repeatedly increases the size of a partial matching by finding augmenting paths. However, instead of finding just a single augmenting path per iteration, the algorithm finds a maximal set of shortest augmenting paths. As a result only O(n) iterations are needed. The same principle has also been used to develop more complicated algorithms for non-bipartite matching with the same asymptotic running time as the HopcroftKarp algorithm.AlgorithmLetUandVbe the two sets in the bipartition ofG, and let the matching fromUtoVat any time be represented as the setM.The algorithm is run in phases. Each phase consists of the following steps. Abreadth first searchpartitions the vertices of the graph into layers. The free vertices inUare used as the starting vertices of this search, and form the first layer of the partition. At the first level of the search, only unmatched edges may be traversed (sinceUis not adjacent to any matched edges); at subsequent levels of the search, the traversed edges are required to alternate between unmatched and matched. That is, when searching for successors from a vertex inU, only unmatched edges may be traversed, while from a vertex inVonly matched edges may be traversed. The search terminates at the first layerkwhere one or more free vertices inVare reached. All free vertices inVat layerkare collected into a setF. That is, a vertexvis put into F if and only if it ends a shortest augmenting path. The algorithm finds a maximal set ofvertex disjointaugmenting paths of lengthk. This set may be computed bydepth first searchfromFto the free vertices inU, using the breadth first layering to guide the search: the depth first search is only allowed to follow edges that lead to an unused vertex in the previous layer, and paths in the depth first search tree must alternate between unmatched and matched edges. Once an augmenting path is found that involves one of the vertices inF, the depth first search is continued from the next starting vertex. Every one of the paths found in this way is used to enlargeM.The algorithm terminates when no more augmenting paths are found in the breadth first search part of one of the phases.AnalysisEach phase consists of a single breadth first search and a single depth first search. Thus, a single phase may be implemented in linear time. Therefore, the first nphases, in a graph withnvertices andmedges, take time O(mn).It can be shown that each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once the initial nphases of the algorithm are complete, the shortest remaining augmenting path has at least nedges in it. However, thesymmetric differenceof the eventual optimal matching and of the partial matchingMfound by the initial phases forms a collection of vertex-disjoint augmenting paths and alternating cycles. If each of the paths in this collection has length at least n, there can be at most npaths in the collection, and the size of the optimal matching can differ from the size ofMby at most nedges. Since each phase of the algorithm increases the size of the matching by at least one, there can be at most nadditional phases before the algorithm terminates.Since the algorithm performs a total of at most 2nphases, it takes a total time of O(mn) in the worst case.In many instances, however, the time taken by the algorithm may be even faster than this worst case analysis indicates. For instance, in theaverage caseforsparsebipartiterandom graphs,Bast et al. (200