下载文档原格式
匈⽛利算法解决⼆分图最⼤匹配预备知识 匈⽛利算法是由匈⽛利数学家Edmonds于1965年提出，因⽽得名。
匈⽛利算法是基于Hall定理中充分性证明的思想，它是⼆分图匹配最常见的算法，该算法的核⼼就是寻找增⼴路径，它是⼀种⽤增⼴路径求⼆分图最⼤匹配的算法。
⼆分图 ⼆分图⼜称作⼆部图，是图论中的⼀种特殊模型。
设G=(V,E)是⼀个⽆向图，如果顶点V可分割为两个互不相交的⼦集(A，B)，并且图中的每条边（i，j）所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集(i in A，j in B)，则称图G为⼀个⼆分图。
匹配 在图论中，⼀个图是⼀个匹配（或称独⽴边集）是指这个图之中，任意两条边都没有公共的顶点。
这时每个顶点都⾄多连出⼀条边，⽽每⼀条边都将⼀对顶点相匹配。
例如，图3、图4中红⾊的边就是图2的匹配。
图3中1、4、5、7为匹配点，其他顶点为⾮匹配点，1-5、4-7为匹配边，其他边为⾮匹配边。
最⼤匹配 ⼀个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最⼤匹配。
图 4 是⼀个最⼤匹配，它包含 4 条匹配边。
任意图中，极⼤匹配的边数不少于最⼤匹配的边数的⼀半。
完美匹配 如果⼀个图的某个匹配中，所有的顶点都是匹配点，那么它就是⼀个完美匹配。
显然，完美匹配⼀定是最⼤匹配，但并⾮每个图都存在完美匹配。
最⼤匹配数：最⼤匹配的匹配边的数⽬。
最⼩点覆盖数：选取最少的点，使任意⼀条边⾄少有⼀个端点被选择。
最⼤独⽴数：选取最多的点，使任意所选两点均不相连。
最⼩路径覆盖数：对于⼀个DAG（有向⽆环图），选取最少条路径，使得每个顶点属于且仅属于⼀条路径，路径长可以为0（即单个点）定理1：Konig定理——最⼤匹配数 = 最⼩点覆盖数定理2：最⼤匹配数 = 最⼤独⽴数定理3：最⼩路径覆盖数 = 顶点数 - 最⼤匹配数匈⽛利算法例⼦ 为了便于理解，选取了dalao博客⾥找妹⼦的例⼦： 通过数代⼈的努⼒，你终于赶上了剩男剩⼥的⼤潮，假设你是⼀位光荣的新世纪媒⼈，在你的⼿上有N个剩男，M个剩⼥，每个⼈都可能对多名异性有好感（惊讶，-_-||暂时不考虑特殊的性取向） 如果⼀对男⼥互有好感，那么你就可以把这⼀对撮合在⼀起，现在让我们⽆视掉所有的单相思（好忧伤的感觉，快哭了），你拥有的⼤概就是下⾯这样⼀张关系图，每⼀条连线都表⽰互有好感。
二分图的最大匹配、完美匹配和匈牙利算法August 1, 2013 / 算法这篇文章讲无权二分图（unweighted bipartite graph）的最大匹配（maximum matching）和完美匹配（perfect matching），以及用于求解匹配的匈牙利算法（Hungarian Algorithm）；不讲带权二分图的最佳匹配。
二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。
准确地说：把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。
如果存在这样的划分，则此图为一个二分图。
二分图的一个等价定义是：不含有「含奇数条边的环」的图。
图 1 是一个二分图。
为了清晰，我们以后都把它画成图 2 的形式。
匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。
例如，图3、图 4 中红色的边就是图 2 的匹配。
我们定义匹配点、匹配边、未匹配点、非匹配边，它们的含义非常显然。
例如图 3 中 1、4、5、7 为匹配点，其他顶点为未匹配点；1-5、4-7为匹配边，其他边为非匹配边。
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
图 4 是一个最大匹配，它包含 4 条匹配边。
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
图 4 是一个完美匹配。
显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。
但并非每个图都存在完美匹配。
举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。
是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。
如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。
基本概念讲完了。
最大权重匹配算法
最大权重匹配算法也叫做二分图匹配，它是解决二分图中最大匹配问题的一种常见算法。
二分图，顾名思义，就是可以分成两部分的图，即将所有节点分成两部分，使得同一
部分内的节点不连通。
下文中，我们以左侧节点为一部分，右侧节点为一部分。
最大权重匹配算法的目的是，在二分图中找到一种最大匹配方式，并且每条匹配边的
权重之和最大。
在实际问题中，这种算法经常用于任务分配、物流运输、职工配对等方
面。
算法过程：
1. 初始化所有匹配边的权重为0，同时记录每个节点是否被匹配过。
2. 从左侧部分的未匹配节点开始，遍历所有未匹配节点，将其标记为当前选中节
点。
3. 查找与当前选中节点有连通边的所有右侧节点，对于每个右侧节点，都计算出它
和当前选中节点形成的匹配边的权重。
如果该权重比之前已存在的匹配边权重要大，则更
新该匹配边权重，并将当前选中节点和右侧节点确定为一条新的匹配边。
如果需要更新匹
配边，则需要将之前的匹配边删除，统计删除边后，继续查找新的匹配边。
4. 如果当前选中节点不能形成新的匹配边，则回溯到上一个节点，并标记该节点为
已匹配。
5. 重复第2、3、4步操作，直到找出全部最大匹配边。
该算法的时间复杂度为O(n^3)，属于多项式时间内可解决问题的范围，而且是一种较为高效的匹配算法。
但是需要注意的是，该算法必须满足是一个二分图才可以使用。
同时，算法并不能保证是一个最小顶标和、最优匹配的算法，但在大多数情况下，都可以得到较
好的匹配效果。
最大匹配算法
在解释最大匹配算法之前，我们先来了解一下什么是二分图和最大匹配。
二分图是指一个图的所有顶点可分为两个互斥的顶点集合，且任意一条边的两个端点都分属于不同的顶点集合。
二分图可以用一个二元组(V,E)表示，其中V表示顶点集合，E表示边集合。
最大匹配是指在一个二分图中找到一个边的子集，使得该子集中的边两两没有公共顶点，并且该子集中的边数量最大。
匈牙利算法是通过增广路径的方式求解最大匹配。
增广路径是指在一个二分图中，通过一系列的未匹配边和匹配边交替组成的路径，起点和终点分别属于不同的顶点集合。
下面是匈牙利算法的步骤：
1.初始化一个空的最大匹配。
2.对二分图中的每个未匹配顶点，找到一个增广路径。
如果找到了增广路径，就将其上的匹配边和未匹配边互换，并将路径上的所有未匹配边变为匹配边，所有匹配边变为未匹配边。
3.重复步骤2，直到无法找到增广路径为止。
在匈牙利算法中，为了找到增广路径，通常会使用深度优先或广度优先。
具体的实现方式可以根据实际情况选取。
匈牙利算法的时间复杂度为O(VE)，其中V为顶点的数量，E为边的
数量。
由于每次找到增广路径后都会改变匹配边和未匹配边的状态，所以
算法的时间复杂度可能比较高。
但是在实际应用中，匈牙利算法在大多数情况下都能快速求解最大匹配问题。
总结起来，最大匹配算法（匈牙利算法）是一种用于求解二分图最大匹配的算法，通过不断寻找增广路径来实现。
它的时间复杂度为O(VE)，并且在实际应用中具有广泛的应用价值。
⼆分图的最⼤匹配—匈⽛利算法【基本概念】：⼆分图：⼆分图⼆分图⼜称作⼆部图，是图论中的⼀种特殊模型。
设G=(V,E)是⼀个⽆向图，如果顶点V可分割为两个互不相交的⼦集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为⼀个⼆分图。
⽆向图G为⼆分图的充分必要条件是，G⾄少有两个顶点，且其所有回路的长度均为偶数。
最⼤匹配最⼤匹配：给定⼀个⼆分图G，在G的⼀个⼦图M中，M的边集中的任意两条边都不依附于同⼀个顶点，则称M是⼀个匹配. 选择这样的边数最⼤的⼦集称为图的最⼤匹配问题，如果⼀个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配.最⼩覆盖：最⼩覆盖要求⽤最少的点（Ｘ集合或Ｙ集合的都⾏）让每条边都⾄少和其中⼀个点关联。
可以证明：最少的点（即覆盖数）＝最⼤匹配数最⼩路径覆盖：⽤尽量少的不相交简单路径覆盖有向⽆环图Ｇ的所有结点。
解决此类问题可以建⽴⼀个⼆分图模型。
把所有顶点i拆成两个：Ｘ结点集中的i 和Y结点集中的i',如果有边i->j，则在⼆分图中引⼊边i->j'，设⼆分图最⼤匹配为m,则结果就是n-m。
增⼴路（增⼴轨）：（增⼴轨）：增⼴路若P是图G中⼀条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的⼀条增⼴路径（举例来说，有A、B集合，增⼴路由A中⼀个点通向B中⼀个点，再由B中这个点通向A中⼀个点……交替进⾏）。
增⼴路径的性质：1 有奇数条边。
2 起点在⼆分图的左半边，终点在右半边。
3 路径上的点⼀定是⼀个在左半边，⼀个在右半边，交替出现。
（其实⼆分图的性质就决定了这⼀点，因为⼆分图同⼀边的点之间没有边相连，不要忘记哦。
）4 整条路径上没有重复的点。
5 起点和终点都是⽬前还没有配对的点，⽽其它所有点都是已经配好对的。
[算法]⼆分图最⼤匹配前⾔具体什么是⼆分图，如何判定，可以参考。
定义简单来说，就是⼆分图中有满⾜任意两条边没有相同的点的边的集合，称为⼀组匹配，⽽边数最多的⼀组匹配称为该⼆分图的最⼤匹配。
在⼀组匹配中，属于这组边的称为匹配边，不属于的称为⾮匹配边，属于这组匹配的点称为匹配点，不属于的称为⾮匹配点。
匈⽛利算法⼜称增⼴路算法。
对于⼀组匹配 \(M\) ，若存在⼀条路径连接两个⾮匹配点，且使得匹配边与⾮匹配边交替出现，则称这条路径为增⼴路。
如上图，已匹配的边为红⾊，未匹配的边为绿⾊，则可以找到⼀组增⼴路 \(8\) ~ \(2\) ~ \(7\) ~ \(4\) 。
不难发现增⼴路具有以下特点：以⾮匹配边开始，在以⾮匹配边结尾，那么长度必为奇数。
路径上第⼀条边因为第⼀个点为奇数，则该路径上的第⼀个点为⾮匹配边，按照匹配边与⾮匹配边交替出现的性质可以得出，该路径的第奇数条边必为⾮匹配边，已经匹配的边必为第偶数条边，则有⾮匹配边的边数⽐匹配边的边数多⼀。
最⼤匹配中不会有增⼴路。
证明：假设最⼤匹配中存在增⼴路，则可以将增⼴路中的所有边的状态取反（即把⾮匹配边转换为匹配边，将匹配边转换为⾮匹配边），得到另⼀组匹配，⽽这组匹配的匹配边肯定会⽐之前的⼀组匹配的边数多⼀，则之前的这组匹配就不是最⼤匹配，与假设⽭盾，证毕。
在⼀张⼆分图中，若最⼤匹配为 \(S\) ，当且仅当 \(S\) 中不存在增⼴路。
其确性基于 \(hall\) 定理，⽐较复杂就不在详讲，主要讲找⼆分图最⼤匹配的⽅法。
⼤体思想就是枚举左部点，找到增⼴路后将这条路上的所有边的状态取反，得到边数更⼤的⼀组匹配。
在匹配过程中，有两种情况会改变当前左部点 \(u\) 的匹配情况。
1. 与之对应的右部点 \(v\) 是⾮匹配点，则可以将其的连边变为匹配边。
2. 与之对应的右部点 \(v\) 是匹配点，但与 \(v\) 已经匹配的点 \(u'\) 可以找到另⼀个未匹配的右部点 \(v'\) ，则 \(u\) ~ \(v\) ~ \(u'\) ~ \(v'\) 为⼀条增⼴路，则将其状态取反。
⼆分图最⼤匹配总结⼆分图匹配（匈⽛利算法）1。
⼀个⼆分图中的最⼤匹配数等于这个图中的最⼩点覆盖数König定理是⼀个⼆分图中很重要的定理，它的意思是，⼀个⼆分图中的最⼤匹配数等于这个图中的最⼩点覆盖数。
如果你还不知道什么是最⼩点覆盖，我也在这⾥说⼀下：假如选了⼀个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边。
2。
最⼩路径覆盖=最⼩路径覆盖＝｜G｜－最⼤匹配数在⼀个N*N的有向图中，路径覆盖就是在图中找⼀些路经，使之覆盖了图中的所有顶点，且任何⼀个顶点有且只有⼀条路径与之关联；（如果把这些路径中的每条路径从它的起始点⾛到它的终点，那么恰好可以经过图中的每个顶点⼀次且仅⼀次）；如果不考虑图中存在回路，那么每每条路径就是⼀个弱连通⼦集．由上⾯可以得出：1.⼀个单独的顶点是⼀条路径；2.如果存在⼀路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．最⼩路径覆盖就是找出最⼩的路径条数，使之成为G的⼀个路径覆盖．路径覆盖与⼆分图匹配的关系：最⼩路径覆盖＝｜G｜－最⼤匹配数；3。
⼆分图最⼤独⽴集=顶点数-⼆分图最⼤匹配独⽴集：图中任意两个顶点都不相连的顶点集合。
⼆分图模板：模板⼀：匈⽛利算法/* **************************************************************************//⼆分图匹配（匈⽛利算法的DFS实现）//初始化：g[][]两边顶点的划分情况//建⽴g[i][j]表⽰i->j的有向边就可以了，是左边向右边的匹配//g没有边相连则初始化为0//uN是匹配左边的顶点数，vN是匹配右边的顶点数//调⽤：res=hungary();输出最⼤匹配数//优点：适⽤于稠密图，DFS找增⼴路，实现简洁易于理解//时间复杂度:O(VE)//***************************************************************************///顶点编号从0开始的const int MAXN=510;int uN,vN;//u,v数⽬int g[MAXN][MAXN];int linker[MAXN];bool used[MAXN];bool dfs(int u)//从左边开始找增⼴路径{int v;for(v=0;v<vN;v++)//这个顶点编号从0开始，若要从1开始需要修改if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){//找增⼴路，反向linker[v]=u;return true;}}return false;//这个不要忘了，经常忘记这句}int hungary(){int res=0;int u;memset(linker,-1,sizeof(linker));for(u=0;u<uN;u++){memset(used,0,sizeof(used));if(dfs(u)) res++;}return res;}//******************************************************************************/模板⼆： Hopcroft-Carp算法这个算法⽐匈⽛利算法的时间复杂度要⼩，⼤数据可以采⽤这个算法/* *********************************************⼆分图匹配（Hopcroft-Carp的算法）。
