第九讲 二分图匹配问题(1)

《第九讲 二分图匹配问题(1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九讲二分图匹配问题一、问题设G=(V,{R})是一个无向图。如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题(maximalmatchingproblem)如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。即回溯法，但是这个算法的复杂度为

2、边数的指数级函数。因此，需要寻求一种更加高效的算法。二、算法分析    二分图的最大匹配有2种实现，网络流和匈牙利算法。1.匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若边集合P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。2.由增广路径的定义可以推出下述三个结论：（1）.P的路径长度必定为奇数，第一条边和最后一条边都不属于M。（2）.P经过“取反操作”（即非M中的边变为M中的边，原来M中的边去掉）可以得到一个更大的匹配M’。（3）.M为G的最大匹配当且仅当

3、不存在相对于M的增广路径。3.从而可以得到求解最大匹配的匈牙利算法：(1)置M为空；(2)找出一条增广路径P，通过“取反操作”获得更大的匹配M’代替M；(3)重复(2)操作直到找不出增广路径为止；根据该算法，可以选择深搜或者广搜实现，下面给出易于实现的深度优先搜索（DFS）实现。三、实现1.    匈牙利算法的算法轮廓 bool 寻找从k出发的对应项出的可增广路{while(j与k邻接){        if(j不在增广路上){            把j加入增广路;            if(j是未盖点 或者 从j的对应项出发有可增广路)                则从k的对

4、应项出有可增广路,返回true;            修改j的对应项为k;        }    }    从k的对应项出没有可增广路,返回false;}2.    匈牙利算法流程3.代码int   n,m,match[100];//二分图的两个集合分别含有n和m个元素,match[i]存储集合m中的节点i在集合n中的匹配节点,初值为-1。设当前匹配为Mbool   visited[100],map[100][100];//map存储邻接矩阵boolDFS(constint&k){     for(inti=0;i

5、isited[i]   )         {              visited[i]=true;            if(match[i]==-1

6、

7、DFS(match[i]))//寻找是否为增广路径        {           match[i]=k;           //路径取反操作。如果match[i]=-1,表示m集合中定点i不在M中，是增广路径；如果match[i]<>-1,由于DFS（match[i]）为true说明找到了增广路径，将定点i在原来M中的边替换掉。（即实现异或操作）          returntrue;             

8、}         }      returnfalse;}voidhungary(){   for(i=0;i

9、);//初始匹配M为空    Hungary（）；//............return0;}四、实例：n2n3n4n1m1m2m3map矩阵如下：执行过程：Hungary函数中第一次循环时，得到增广路径：n1----m1，也就是一个匹配第二次循环时，得到增广路径：n2----m1----n1----m2,得到新匹配：n2—m1,n1—m2第三次循环时，得到增光路径：n3—m2—n1—m1---n2----m3,得到新的匹配：n3---m2,n1---m