最新精编医学专题—二分图匹配基于匈牙利算法和KM算法.docx

二分图匹配----基于匈牙利算法和KM算法2007-09-1916:54设G=(V{R})是一个无向图。如顶点集V可分割为两个互不相交的子集并且图中每条边依附的两个顶点都分属两个不同的子集。则称图G为二分图。v给定一个二分图G在G的一个子图M中M的边集{E}中的任意两条边都不依附于同一个顶点则称M是一个匹配。v选择这样的边数最大的子集称为图的最大匹配问题(maximalmatchingproblem)v如果一个匹配中图中的每个顶点都和图中某条边相关联则称此匹配为完全匹配也称作完备匹配。最大匹配在实际中有广泛的用处求最大匹配的一种显而易见的算法是：先找出全部匹配然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此需要寻求一种更加高效的算法。匈牙利算法是求解最大匹配的有效算法该算法用到了增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现则称P为相对于M的一条增广路径。由增广路径的定义可以推出下述三个结论：v1.P的路径长度必定为奇数第一条边和最后一条边都不属于M。v2.P经过取反操作（即非M中的边变为M中的边原来M中的边去掉）可以得到一个更大的匹配M’。v3.M为G的最大匹配当且仅当不存在相对于M的增广路径。从而可以得到求解最大匹配的匈牙利算法：v(1)置M为空v(2)找出一条增广路径P通过取反操作获得更大的匹配M’代替Mv(3)重复(2)操作直到找不出增广路径为止根据该算法我选用dfs(深度优先搜索)实现。程序清单如下：intmatch[i]//存储集合m中的节点i在集合n中的匹配节点初值为-1。intnmmatch[100];//二分图的两个集合分别含有n和m个元素。boolvisit[100]map[100][100];//map存储邻接矩阵。booldfs(intk){intt;for(inti=0;i<m;i++)if(map[k][i]&&!visit[i]){visit[i]=true;t=match[i];match[i]=k;//路径取反操作。if(t==-1||dfs(t))//寻找是否为增广路径returntrue;match[i]=t;}returnfalse;}intmain(){//...........ints=0;memset(match-1sizeof(match));for(i=0;i<n;i++){//以二分集中的较小集为n进行匹配较优memset(visit0sizeof(visit));if(dfs(i))s++;//s为匹配数}//............return0;}二分图最优匹配：对于二分图的每条边都有一个权（非负）要求一种完备匹配方案使得所有匹配边的权和最大记做最优完备匹配。（特殊的当所有边的权为1时就是最大完备匹配问题）解二分图最优匹配问题可用穷举的方法但穷举的效率=n！所以我们需要更加优秀的算法。先说一个定理：设M是一个带权完全二分图G的一个完备匹配给每个顶点一个可行顶标(第i个x顶点的可行标用lx[i]表示第j个y顶点的可行标用ly[j]表示)如果对所有的边(ij)inG都有lx[i]+ly[j]>=w[ij]成立(w[ij]表示边的权)且对所有的边(ij)inM都有lx[i]+ly[j]=w[ij]成立则M是图G的一个最优匹配。Kuhn－Munkras算法（即KM算法）流程：v(1)初始化可行顶标的值v(2)用匈牙利算法寻找完备匹配v(3)若未找到完备匹配则修改可行顶标的值v(4)重复(2)(3)直到找到相等子图的完备匹配为止KM算法主要就是控制怎样修改可行顶标的策略使得最终可以达到一个完美匹配首先任意设置可行顶标（如每个X节点的可行顶标设为它出发的所有弧的最大权Y节点的可行顶标设为0）然后在相等子图中寻找增广路找到增广路就沿着增广路增广。而如果没有找到增广路呢那么就考虑所有现在在匈牙利树中的X节点（记为S集合）所有现在在匈牙