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

序言： 目录： 第一部分：二分图匹配 第二部分：第三部分：第四部分： 第五部分：符号说明： N：点数 E：边数 u,v,i,j：节点的标号 INF：正无穷大 -INF：负无穷大 名词说明：时间复杂度：算法的理论时间上界 时间效率：实际中算法运行的平均时间效率 引用说明：文中参考了来源于网络的资料，也有原文全段引用的部分。在这些资料被n+1次转载后，我已无法获知所有原作者的信息。在此，对所有前辈们表示真诚的歉意和诚挚的敬意。正文： 第一部分：二分图匹配 ，让我们理清一些概念二分图：若图G中的点可以分为X和Y，每部分内部无任何边相连，则称图G为二分图。 匹配：无公共点的边集合。 匹配数：边集中边的个数 最大匹配：匹配数最大的匹配。 如图1-1，展示的就是一个二分图：粗体线表示该二分图的一种匹配方式，不难发现，此时的匹配已经是最大匹配。 图 1-1 如何能得到一个二分图的最大匹配？运用简单的枚举：找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级，时间上通常无法承受。因此，需要寻求一种更加高效的算法。由此便引出了匈牙利算法（hungary），这个算法的名字很有趣，它是由匈牙利数学家Edmonds于1965年提出的。 在正式的讲这个算法之前，不妨想一想，还有什么办法可以比较快速的计算出二分图的最大匹配？没错，网络的最大流算法可以搞定：我们需要增加额外的源汇点S，T，则对于图 1-1我们很容易得到如图1-2所示的网络模型，图中所有的边容量都为1，粗体箭头表示流从该边经过： 由此，问题得到了等价的转换：最大匹配数=最大流。若采用sap算法计算最大流，则时间复杂度为O(E)，已经有了较高的效率。然则杀鸡焉用宰牛刀，实际上，我们没必要将问题复杂化，针对二分图的特殊性，我们可以采用效率更高，代码量更小的hungary算法解决。 hungary算法的实质是贪心:若点ix存在一种匹配jy（即两点之间有连边），若使ix，jy匹配，则至少不会得到更差的解。这种贪心思想正确性显然：如果让ix，jy匹配，且不去改变这个决策，导致的后果就是jy不再能被其它节点匹配，也就是这个决策可能会使匹配数-1，但同时ix，jy匹配一定会使匹配数+1，因此这种匹配至少不会使总匹配数减少。 由此我们可以得到如下三个结论： 点匹配的先后顺序是任意的（即先匹配ix还是先匹配kx并不会影响结果）。 若点ix存在某种匹配jy，不会使匹配数减少（即不影响已经匹配的点），则点ix一定要被匹配。 反之，若点ix在第一验证时，不存在上述的匹配，则该点在以后也一定无法再找到上述匹配。 如果可以检验出当ix匹配jy时不会影响到已经匹配的点，那么我们就能得到计算最大匹配的一种方法：从任意点开始，若存在某种匹配使得该匹配不会影响之前的匹配，则匹配数+1，并且记录下该匹配。找下一个未尝试过的点，直到所有的点都被遍历过。 现在问题的关键就是如何检验：对于二分部的Y部分，令数组match[]表示Y部分的点在X部分对应匹配（例如当ix与jy匹配时，有match[jy]=ix）。初始时，match[]都设为-1，即所有的点都还没有被匹配过，而没有被匹配过的点通常称之为未盖点。当验证ux，时，我们可以遍历它所有可能的匹配点vy（即与ux有连边的点），若match[vy]=-1，显然ux与uy的匹配不会使之前的匹配减少，故ux一定要被匹配，且记match[vy]=vx；若match[vy] ≠ -1，那么我们知道vy之前匹配的点是match[vy]，同样是X部分的点，处理方式必然等价，故不难想到，可以采用递归的方式对match[vy]做相同的处理（其实就是在检验是否能通过修改之前的匹配方案，使得原来的匹配点仍旧都有匹配，即匹配数不减少，而冲突却被调和了）。 由此，我们得到了如下的hungary算法流程： 初始化匹配数cnt为0，标记数组match[]为-1。 若点ix是没有被遍历过，则执行3，否则执行5。 寻找该点可能的所有匹配点jy，若match[jy]=-1，则执行4，否则把当前点ix设置为match[jy]，继续执行3。若没有执行过4，则执行5。 cnt+1，match[jy]=ix，执行5。 寻找下个未遍历的点，若所有点都被遍历过，则算法结束，当前的cnt即为最大匹配数。 实际上，上述验证的方式完全等价于在验证图中是否存在增广路（也称为交错轨）或者说二分图增广路的定义是为了采用更规范的阐述，用来表达实际效果。注意这里