第九讲二分图匹配问题

第九讲 二分图匹配问题 一、问题 设 G=(V,{R})是一个无向图。如顶点集 V 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图 G 为二分图。 给定一个二分图 G，在 G 的一个子图 M 中，M 的边集{E}中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。 选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem) 如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。 最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。即回溯法，但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。 二 、算法分析 二分图的最大匹配有 2 种实现，网络流和匈牙利算法。 1.匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若边集合 P是图 G 中一条连通两个未匹配顶点的路径，并且属 M 的边和不属 M 的边(即已匹配和待匹配的边)在 P 上交替出现，则称 P 为相对于 M 的一条增广路径。 2.由增广路径的定义可以推出下述三个结论： （1）. P 的路径长度必定为奇数，第一条边和最后一条边都不属于 M。 （2）. P 经过“取反操作”（即非 M 中的边变为 M 中的边，原来 M 中的边去掉）可以得到一个更大的匹配 M’。 （3）. M 为 G 的最大匹配当且仅当不存在相对于 M 的增广路径。 3.从而可以得到求解最大匹配的匈牙利算法： (1)置 M 为空； (2)找出一条增广路径P，通过“取反操作”获得更大的匹配 M’代替M； (3)重复(2)操作直到找不出增广路径为止； 根据该算法，可以选择深搜或者广搜实现，下面给出易于实现的深度优先搜索（DFS）实现。 三、实现 1. 匈牙利算法的算法轮廓 bool 寻找从 k 出发的对应项出的可增广路{ while(j 与 k 邻接){ if(j 不在增广路上){ 把 j 加入增广路; if(j 是未盖点 或者 从 j 的对应项出发有可增广路) 则从 k 的对应项出有可增广路,返回 true; 修改 j 的对应项为 k; } } 从 k 的对应项出没有可增广路,返回 false; } 2. 匈牙利算法流程 3.代码 int n, m, match[100]; //二分图的两个集合分别含有n 和m 个元素,match[i]存储集合m 中的节点i 在集合n中的匹配节点,初值为-1。设当前匹配为M bool ...