匈牙利法求二分图最大匹配.doc

什么是二分图，什么是二分图的最大匹配，这些定义我就不讲了，网上随便都找得到。二分图的最大匹配有两种求法，第一种是最大流（我在此假设读者已有网络流的知识）；第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。匈牙利算法其实很简单，但是网上搜不到什么说得清楚的文章。所以我决定要写一下。最大流算法的核心问题就是找增广路径（augment path）。匈牙利算法也不例外，它的基本模式就是：初始时最大匹配为空while 找得到增广路径 do 把增广路径加入到最大匹配中去可见和最大流算法是一样的。但是这里的增广路径就有它一定的特殊性，下面我来分析一下。（注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。每条边也不需要有方向。）图1 图2图1是我给出的二分图中的一个匹配：1，5和2，6。图2就是在这个匹配的基础上找到的一条增广路径：3-6-2-5-1-4。我们借由它来描述一下二分图中的增广路径的性质：(1)有奇数条边。(2)起点在二分图的左半边，终点在右半边。(3)路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。）(4)整条路径上没有重复的点。(5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。（如图1、图2所示，1，5和2，6在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。）(6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。（如图1、图2所示，原有的匹配是1，5和2，6，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。）(7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中去，并把增广路径中的所有第偶数条边从原匹配中删除（这个操作称为增广路径的取反），则新的匹配数就比原匹配数增加了1个。（如图2所示，新的匹配就是所有蓝色的边，而所有红色的边则从原匹配中删除。则新的匹配数为3。）不难想通，在最初始时，还没有任何匹配时，图1中的两条灰色的边本身也是增广路径。因此在这张二分图中寻找最大配匹的过程可能如下：(1)找到增广路径1-5，把它取反，则匹配数增加到1。(2)找到增广路径2-6，把它取反，则匹配数增加到2。(3)找到增广路径3-6-2-5-1-4，把它取反，则匹配数增加到3。(4)再也找不到增广路径，结束。当然，这只是一种可能的流程。也可能有别的找增广路径的顺序，或者找到不同的增广路径，最终的匹配方案也可能不一样。但是最大匹配数一定都是相同的。对于增广路径还可以用一个递归的方法来描述。这个描述不一定最准确，但是它揭示了寻找增广路径的一般方法：“从点A出发的增广路径”一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匹配中没有与任何点配对，则它就是这条增广路径的终点；反之，如果点B已与点C配对，那么这条增广路径就是从A到B，再从B到C，再加上“从点C出发的增广路径”。并且，这条从C出发的增广路径中不能与前半部分的增广路径有重复的点。比如图2中，我们要寻找一条从3出发的增广路径，要做以下3步：(1)首先从3出发，它能连到的点只有6，而6在图1中已经与2配对，所以目前的增广路径就是3-6-2再加上从2出发的增广路径。(2)从2出发，它能连到的不与前半部分路径重复的点只有5，而且5确实在原匹配中没有与2配对。所以从2连到5。但5在图1中已经与1配对，所以目前的增广路径为3-6-2-5-1再加上从1出发的增广路径。(3)从1出发，能连到的不与自已配对并且不与前半部分路径重复的点只有4。因为4在图1中没有与任何点配对，所以它就是终点。所以最终的增广路径是3-6-2-5-1-4。但是严格地说，以上过程中从2出发的增广路径（2-5-1-4）和从1出发的增广路径（1-4）并不是真正的增广路径。因为它们不符合前面讲过的增广路径的第5条性质，它们的起点都是已经配过对的点。我们在这里称它们为“增广路径”只是为了方便说明整个搜寻的过程。而这两条路径本身只能算是两个不为外界所知的子过程的返回结果。显然，从上面的例子可以看出，搜寻增广路径的方法就是DFS，可以写成一个递归函数。当然，用BFS也完全可以实现。至此，理论基础部份讲完了。但是要完成匈牙利算法，还需要一个重要的定理：如果从一个点A出发，没有找到增广路径，那么无论再从别的点出发找到多少增广路径来改变现在的匹配，从A出发都永远找不到增广路径。要用文字来证明这个定理很繁，话很难说，要么我还得多画一张图，我在此就省了。其实你自己画几个图，试图举两个反例，这个定理不难想通的。（给个提示。如果你试图举个反例来说明在找到了别的增广路径并改变了现有的匹配后，从A出发就能找到增广路径。那么，在这种情况下，肯定在找到别的增广路径之前，就能从A出发找到增广路径。这就与假设矛盾了。）有了这个定理，匈牙利算法就成形了。如下：初始时最大匹配为空for 二分图左半边的每个点i do 从点i出发寻找增广路径。如果找到，则把它取反（即增加了总了匹配数）。如果二分图的左半边一共有n个点，那么最多找n条增广路径。如果图中共有m条边，那么每找一条增广路径（DFS或BFS）时最多把所有边遍历一遍，所花时间也就是m。所以总的时间大概就是O（n * m）。在UVA上，二分图匹配的题目有670和10080，祝好运。以下是我的标程。是用BFS搜索增广路径的。虽然DFS可能写起来比较简单，但是我不想让它递归很多层。欢迎使用我的标程。/Bipartite graphic and maximum matching with Hungarian algorithm./#include #include using namespace std;const int MAX_LEFT = 500;const int MAX_RIGHT = 500;class Bipartite private: struct Edge int to; Edge* next; Edge(int _to) to = _to; ; Edge* m_adjListMAX_LEFT; int m_lCnt; int m_rCnt; int m_lMatchRMAX_RIGHT; int m_rMatchLMAX_LEFT; int m_preLMAX_LEFT; bool m_visitRMAX_RIGHT; /This matrix is just used to prevent adding two repeated edges. bool m_matrixMAX_LEFTMAX_RIGHT; void clear() for (int i = 0; i next; delete pre; m_adjListi = NULL; memset(m_matrix, 0, sizeof(m_matrix); void findAugment(int start) for (int i = 0; i m_lCnt; i+) m_preLi = -1; memset(m_visitR, 0, sizeof(bool) * m_rCnt); list que; que.push_back(start); bool found = false; while (!que.empty() & !found) int from = que.front(); que.pop_front(); Edge* edge = m_adjListfrom; while (edge != NULL & !found) int to = edge-to; if (!m_visitRto) m_visitRto = true; if (m_rMatchLto = -1) found = true; reverse(from, to); else que.push_back(m_rMatchLto); m_preLm_rMatchLto = from; edge = edge-next; void reverse(int left, int right) m_rMatchLright = left; while(m_preLleft != -1) int nextR = m_lMatchRleft; m_rMatchLnextR = m_preLleft; m_lMatchRleft = right; left = m_preLleft; right = nextR; m_lMatchRleft = right; public: Bipartite() memset(m_adjList, 0, sizeof(m_adjList); m_lCnt = 0; m_rCnt = 0; Bipartite() clear(); /Add an edge between vertex left and right while left and right are /the indices of two vertices in the left/right parts of the graph. Indices /in the left and right parts are separated and they both begin from 0. void addEdge(int left, int right) if (!m_matrixleftright) m_matrixleftright = true; Edge* newEdge = new Edge(right); newEdge-next = m_adjListleft; m_adjListleft = newEdge; /Before invoking this function, maxMatch() must be invoked. This function /returns the index of the matching vertex of left while left is the /index of a vertex in the left part of the graphic. int getLMatchR(int left) const return m_lMatchRleft; /See getLMatchR(), and this function is opposite to it. int getRMatchL(int right) const return m_rMatchLright; void init(int leftCnt, int rightCnt) clear(); m_lCnt = leftCnt; m_rCnt = rightCnt; for (int i = 0; i m_lCnt; i+) m_lMatchRi = -1; for (int i = 0; i m_rCnt; i+) m_rMatchLi = -1; int maxMatch() for (int i = 0; i m_lCnt; i+) findAugment(i); int result = 0; for (int i = 0; i m_lCnt; i+) if (m_lMatchRi != -1) result+; return result; ;/Test suites.#include int main() Bipartite match; match.init(300, 400); int a = 0, 0, 1, 1, 2, 2, 2; int b = 1, 2, 1, 3, 0, 1, 2; for (int i = 0; i 7; i+) match.addEdge(ai, bi); int maxMatch = match.maxMatch(); cout maxMatch ; for (int i = 0; i 3; i+) cout match.getLMatchR(i) ; for (int i = 0; i 4; i+) cout match.getRMatchL(i) ; cout endl;/Correct: 3 2 3 1 -1 2 0 1 return 0;二分图的最大匹配 Maximum Matching on Bipartite Graph这是一个经典中的经典问题。求解这类问题，最常用的就是匈牙利算法，复杂度为O(n3)。我在这里详细的介绍三种不同的实现，针对不同的题目，他们有不同的效果呦_。先定义一些框架：int nx , ny , gmaxnmaxn , cxmaxn , cymaxn ;/ cxi表示与Xi匹配的Y顶点/ cyi同理这三种方法不同的地方就在于不同的寻找增广路径的方法。1、DFS增广从某一个X顶点出发，用深度优先的策略寻找增广路，并在找到之后，巧妙地利用递归来修改匹配。int mkmaxn ;int path(int u) for (int v = 0 ; v ny ; v+) if (guv & !mkv) mkv = 1 ; if (cyv = -1 |path(cyv) cxu = v ; cyv = u ; return 1 ; return 0 ;int MaxMatch() int res=0 ; memset(cx , 0xff , sizeof(cx) ; memset(cy , 0xff , sizeof(cy) ; for (int i = 0 ; i = nx ; i+) if (cxi = -1) memset(mk , 0 , sizeof(mk) ; res += path(i) ; return res ;优点：实现简洁，理解容易适用：稠密图，由于边多，dfs找增广路很快复杂度：O(n3)2、BFS增广int predmaxn , mkmaxn , openmaxn ;int MaxMatch() int i ,u , v , t , d , e, cur , tail, res(0) ; memset(mk , 0xff , sizeof(mk) ; memset(cx , 0xff , sizeof(cx) ; memset(cy , 0xff , sizeof(cy) ; for (i = 0 ; i nx ; i+) predi = -1 ;for (opencur = tail = 0 = i ;cur = tail &cxi = -1 ; cur+) for (u = opencur , v = 0 ; v = 0) predopentail = u ; continue ; for (d = u , e = v ; d != -1 ;t = cxd , cxd = e , cye = d ,e = t , d = predd) ; break ; if (cxi != -1) res+ ; return res ;适用：稀疏二分图，边少，增广路短复杂度：O(n3)3、多增广路这是一类方法，每次增广同时寻找多条不相交增广路，由Hopcroft和Karp于1973年提出，有非常优秀的时间界。以下代码由BFS的框架直接修改而来：int predmaxn , mkmaxn , openmaxn , srcmaxn ;int MaxMatch() int i ,u , v , t , d , e, cur , tail, res(0), p,flag ; memset(mk , 0xff , sizeof(mk) ; memset(cx , 0xff , sizeof(cx) ; memset(cy , 0xff , sizeof(cy) ; for (p =1 , flag = 1 ; flag ;p+) flag = 0 ; for (cur = tail = 0 , i = 0 ; i nx ; i +) if (cxi = -1) open+tail = i ,predi = -1 , srci = i ;for ( ;cur = tail ; cur+) u = opencur ; if (cxsrcu !=-1) continue ;for (v = 0 ; v = 0) predopentail = u ; srcopentail = srcu ; continue ; for (tail- , flag = 1 , d = u , e = v ; d != -1 ;t = cxd , cxd = e , cye = d ,e = t , d = predd) ; break ; for (i = 0 ; i |M|，则称M是最大匹配。其中|M|表示 匹配M的边数。 7。对称差： A，B是两个集合，定义 AB = (AB)(AB) 则AB称为A和B的对称差。 定理：M为G的最大匹配的充要条件是G中不存在可增广道路。 Hall定理：对于二部图G，存在一个匹配M，使得X的所有顶点关于M饱和的充要条件是：对于 X的任意一个子集A，和A邻接的点集为T(A)，恒有： |T(A)| = |A| 匈牙利算法是基于Hall定理中充分性证明的思想，其基本步骤为： 1。任给初始匹配M； 2。若X已饱和则结束，否则进行第3步； 3。在X中找到一个非饱和顶点x0，作 V1 x0, V2 4。若T(V1) = V2则因为无法匹配而停止，否则任选一点y T(V1)V2； 5。若y已饱和则转6，否则做一条从x0 y的可增广道路P，MME(P)，转2； 6。由于y已饱和，所以M中有一条边(y,z)，作 V1 V1 z, V2 V2 y， 转4； 本文来自CSDN博客，转载请标明出处：/yyaadet/archive/2006/06/19/814598.aspx二分图是这样一个图，它的顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合，另一个属于集合。给定一个二分图G，M为G边集的一个子集， 如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。图中包含边数最多的匹配称为图的最大匹配。二分图的最大匹配有两种求法，第一种是最大流；第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。最大流算法的核心问题就是找增广路径（augment path）。匈牙利算法也不例外，它的基本模式就是：初始时最大匹配为空while 找得到增广路径 do 把增广路径加入到最大匹配中去可见和最大流算法是一样的。但是这里的增广路径就有它一定的特殊性，下面我来分析一下。（注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。每条边也不需要有方向。）#include bool gmaxnmaxm; int linkmaxm; bool donemaxm;/*其中n,m分别为2部图两边节点的个数,两边的节点分别用1.n,1.m编号 gxy=true表示x,y两个点之间有边相连 linky记录的是当前与y节点相连的x节点 downy记录的是y中的i节点是否被访问过. */bool find(int v) int i;for (i=1; i=m; i+)if (gvi & !donei) donei=true;if (linki=0) | find(linki) linki=v; return true; return false;int main() int ans=0;/read the graph into array g for (i=1; i=wi,j始终 成立。KM算法的正确性基于以下定理： 若由二分图中所有满足Ai+Bj=wi,j的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使Ai+Bj=wi,j恒成立，令Ai为所有与顶点Xi关联的边的最大权，Bj=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 两端都在交错树中的边(i,j)，Ai+Bj的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 两端都不在交错树中的边(i,j)，Ai和Bj都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 X端不在交错树中，Y端在交错树中的边(i,j)，它的Ai+Bj的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 X端在交错树中，Y端不在交错树中的边(i,j)，它的Ai+Bj的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。 现在的问题就是求d值了。为了使Ai+Bj=wi,j始终成立，且至少有一条边进入相等子图，d应该等于minAi+Bj-wi,j|Xi在交错树中，Yi不在交错树中。 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)需要找O(n)次增广路，每次增广最多需要修改O(n)次顶 标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数 slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slackj变成原值与A i+Bj-wi,j的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改 顶标后，要把所有的slack值都减去d。 #include #include #include / 使用其中的 min 函数using namespace std;const int MAX = 1024;int n; / X 的大小int weightMAXMAX; / X 到 Y 的映射（权重）int lxMAX, lyMAX; / 标号bool sxMAX, syMAX; / 是否被搜索过int matchMAX; / Y(i) 与 X(match i) 匹配/ 初始化权重void init(int size);/ 从 X(u) 寻找增广道路，找到则返回 truebool path(int u);/ 参数 maxsum 为 true ，返回最大权匹配，否则最小权匹配int bestmatch(bool maxsum = true);void init(int size) / 根据实际情况，添加代码以初始化 n = size; for (int i = 0; i n; i +) for (