第九讲 二分图匹配问题 一、问题 设 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 ...