二分图匹配基于匈牙利算法和KM算法.doc

《二分图匹配基于匈牙利算法和KM算法.doc》由会员分享，可在线阅读，更多相关《二分图匹配基于匈牙利算法和KM算法.doc（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二分图匹配-基于匈牙利算法和 KM 算法2007-09-19 16:54设 G=(V,R)是一个无向图。如顶点集 V 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图 G 为二分图。v给定一个二分图 G，在 G 的一个子图 M 中，M 的边集E中的任意两条边都不依附于同一个顶点，则称 M 是一个匹配。v选择这样的边数最大的子集称为图的最大匹配问题最大匹配问题(maximal matchingproblem)v如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配完全匹配，也称作完备匹配。完备匹配。最大匹配在实际中有广泛的用处，求最大匹配的一

2、种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若 P 是图 G 中一条连通两个未匹配顶点的路径，并且属 M 的边和不属 M 的边(即已匹配和待匹配的边)在 P 上交替出现，则称 P 为相对于 M的一条增广路径。由增广路径的定义可以推出下述三个结论：v1.P 的路径长度必定为奇数，第一条边和最后一条边都不属于 M。v2.P 经过取反操作（即非 M 中的边变为 M 中的边，原来 M 中的边去掉）可以得到一个更大的匹配 M。v3.M

3、 为 G 的最大匹配当且仅当不存在相对于 M 的增广路径。从而可以得到求解最大匹配的匈牙利算法：v(1)置 M 为空v(2)找出一条增广路径 P，通过取反操作获得更大的匹配 M代替 Mv(3)重复(2)操作直到找不出增广路径为止根据该算法，我选用 dfs(深度优先搜索)实现。程序清单如下：程序清单如下：int matchi/存储集合 m 中的节点 i 在集合 n 中的匹配节点,初值为-1。int n,m,match100;/二分图的两个集合分别含有 n 和 m 个元素。bool visit100,map100100;/map 存储邻接矩阵。bool dfs(int k)int t;for(in

4、t i=0;i m;i+)if(mapki&!visiti)visiti=true;t=matchi;matchi=k;/路径取反操作。if(t=-1|dfs(t)/寻找是否为增广路径return true;matchi=t;return false;int main()/.ints=0;memset(match,-1,sizeof(match);for(i=0;i=wi,j成立(wi,j表示边的权)，且对所有的边(i,j)in M,都有 lxi+lyj=wi,j成立，则 M 是图 G 的一个最优匹配。KuhnMunkras 算法（即 KM 算法）流程：v(1)初始化可行顶标的值v(2)用匈牙

5、利算法寻找完备匹配v(3)若未找到完备匹配则修改可行顶标的值v(4)重复(2)(3)直到找到相等子图的完备匹配为止KM 算法主要就是控制怎样修改可行顶标的策略使得最终可以达到一个完美匹配，首先任意设置可行顶标（如每个 X 节点的可行顶标设为它出发的所有弧的最大权，Y 节点的可行顶标设为 0），然后在相等子图中寻找增广路，找到增广路就沿着增广路增广。而如果没有找到增广路呢，那么就考虑所有现在在匈牙利树中的 X 节点（记为 S 集合），所有现在在匈牙利树中的 Y 节点（记为 T集合），考察所有一段在 S 集合，一段在 not T 集合中的弧，取delta=minl(xi)+l(yj)-w(xi,y

6、j),|xi in S,yjin not T。明显的，当我们把所有 S 集合中的l(xi)减少 delta 之后，一定会有至少一条属于(S,not T)的边进入相等子图，进而可以继续扩展匈牙利树，为了保证原来属于(S,T)的边不退出相等子图，把所有在 T集合中的点的可行顶标增加 delta。随后匈牙利树继续扩展，如果新加入匈牙利树的 Y 节点是未盖点，那么找到增广路，否则把该节点的对应的 X 匹配点加入匈牙利树继续尝试增广。复杂度分析：由于在不扩大匹配的情况下每次匈牙利树做如上调整之后至少增加一个元素，因此最多执行 n 次就可以找到一条增广路，最多需要找 n 条增广路，故最多执行 n2 次修改

7、顶标的操作，而每次修改顶标需要扫描所有弧，这样修改顶标的复杂度就是 O(n2)的，总的复杂度是 O(n4)的。对于 not T 的每个元素 yj，定义松弛变量 slack(yj)=minl(xi)+l(yj)-w(xi,yj),|xiin S，很明显每次的 delta=minslack(yj),|yjin not T，每次增广之后用 O(n2)的时间计算所有点的初始 slack，由于生长匈牙利树的时候每条弧的顶标增量相同，因此修改每个 slack 需要常数时间（注意在修改顶标后和把已盖 Y 节点对应的 X 节点加入匈牙利树的时候是需要修改 slack 的）。这样修改所有 slack 值时间是 O(n)的，每次增广后最多修改 n 次顶标，那么修改顶标的总时间降为 O(n2)，n 次增广的总时间复杂度降为 O(n3)。事实上这样实现之后对于大部分的数据可以比 O(n4)的算法快一倍左右。利用二分图匹配的匈牙利算法和 KM 算法，我们可以求解大部分的关于二分图的问题，它们提供了求解最大匹配和最优匹配的有效算法，在具体编程时我们只要多注意优化，我们就可以得出求解这类问题的有效方法，从而可以对这类实际问题进行有效合理的解决。