二分图的最大匹配经典之匈牙利算法

匈⽛利算法解决⼆分图最⼤匹配预备知识 匈⽛利算法是由匈⽛利数学家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个剩⼥，每个⼈都可能对多名异性有好感（惊讶，-_-||暂时不考虑特殊的性取向） 如果⼀对男⼥互有好感，那么你就可以把这⼀对撮合在⼀起，现在让我们⽆视掉所有的单相思（好忧伤的感觉，快哭了），你拥有的⼤概就是下⾯这样⼀张关系图，每⼀条连线都表⽰互有好感。

运筹学匈牙利法运筹学匈牙利法（Hungarian Algorithm），也叫匈牙利算法，是解决二部图最大（小）权完美匹配（也称作二分图最大权匹配、二分图最小点覆盖）问题的经典算法，是由匈牙利数学家Kuhn和Harold W. Kuhn发明的，属于贪心算法的一种。

问题描述在一个二分图中，每个节点分别属于两个特定集合。

找到一种匹配，使得所有内部的节点对都有连边，并且找到一种匹配方案，使得该方案的边权和最大。

应用场景匈牙利算法的应用场景较为广泛，比如在生产调度、货车调度、学生对导师的指定、电影的推荐等领域内，都有广泛的应用。

算法流程匈牙利算法的伪代码描述如下：进行循环ɑ、选择一点未匹配的点a作为起点，它在二分图的左边β、找出a所有未匹配的点作为下一层节点ɣ、对下一层的每个节点，如果它在右边未匹配，直接匹配ɛ、如果遇到一个已经匹配的节点，进入下一圈，考虑和它匹配的情况δ、对已经匹配的点，将它已经匹配的点拿出来，作为下一层节点，标记这个点作为已被搜索过ε、将这个点作为当前层的虚拟点，没人配它，看能否为它找到和它匹配的点ζ、如果能匹配到它的伴侣，令它们成对被匹配最后输出最大权匹配。

算法优缺点优点：相比于暴力求解二分图最大权匹配来说，匈牙利算法具有优秀的解决效率和高效的时间复杂度，可以在多项式时间（O(n^3)）内解决二分图最大权匹配问题。

缺点：当二分图较大时，匈牙利算法还是有很大的计算复杂度，复杂度不佳，算法有效性差。

此时就需要改进算法或者使用其他算法。

总结匈牙利算法是一个常见的解决二分图最大权匹配问题的算法，由于其简洁、易用、效率优秀等特性，广泛应用于学术和实际问题中。

匈牙利算法虽然在处理较大规模问题时效率不佳，但仍然是一种值得掌握的经典算法。

匈牙利算法一、算法概述匈牙利算法是一种解决二分图最大匹配问题的经典算法，由匈牙利数学家DénesKőnig于1931年提出。

二分图是指图中的节点可以分为两个互不相交的集合，并且图中的边只能连接两个集合中的节点。

最大匹配问题是在二分图中找到最大的边集合，使得每个节点都只与一条边相连。

匈牙利算法通过不断寻找增广路径来寻找最大匹配。

增广路径是指一条路径，其起点和终点都不属于当前的匹配边集合，并且路径中的边交替属于匹配边和非匹配边。

通过不断寻找增广路径，匈牙利算法可以将非匹配边转化为匹配边，从而逐步增大匹配边集合的大小，直到无法找到增广路径为止。

二、算法步骤匈牙利算法的基本思路是通过深度优先搜索来寻找增广路径。

具体步骤如下：1. 初始化将所有节点的匹配状态设为未匹配。

2. 寻找增广路径从一个未匹配节点开始，进行深度优先搜索，寻找增广路径。

在搜索过程中，每次选择一个未匹配的邻接节点进行继续搜索，直到找到一条增广路径或者无法继续搜索为止。

3. 更新匹配边集合如果找到了增广路径，就将路径中的非匹配边转化为匹配边，同时将原来的匹配边转化为非匹配边。

然后回到第2步，继续寻找下一个增广路径。

4. 输出最大匹配当无法找到增广路径时，算法结束。

此时，最大匹配就是匹配边集合中的边。

三、算法示例为了更好地理解匈牙利算法，下面以一个具体的示例来说明。

假设有一个二分图，左侧的节点集合为A，右侧的节点集合为B，边集合为E。

图中的边表示两个节点之间的关系。

A = {a1, a2, a3}B = {b1, b2, b3}E = {(a1, b1), (a1, b2), (a2, b1), (a3, b2), (a3, b3)}初始时，所有节点的匹配状态都为未匹配。

1. 寻找增广路径从一个未匹配的节点开始，进行深度优先搜索，寻找增广路径。

假设从节点a1开始，我们找到了一条增广路径：a1-b1-a2-b2-a3。

2. 更新匹配边集合将路径中的非匹配边转化为匹配边，同时将原来的匹配边转化为非匹配边。

二分图的最大匹配完美匹配和匈牙利算法匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。

匈牙利算法是基于Hall定理中充分性证明的思想，它是二部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

这篇文章讲无权二分图（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 是一个完美匹配。

显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突）。

但并非每个图都存在完美匹配。

举例来说：如下图所示，如果在某一对男孩和女孩之间存在相连的边，就意味着他们彼此喜欢。

是否可能让所有男孩和女孩两两配对，使得每对儿都互相喜欢呢？图论中，这就是完美匹配问题。

前言：高中时候老师讲这个就听得迷迷糊糊，有一晚花了通宵看KM的Pascal代码，大概知道过程了，后来老师说不是重点，所以忘的差不多了。

都知道二分图匹配是个难点，我这周花了些时间研究了一下这两个算法，总结一下1.基本概念M代表匹配集合未盖点：不与任何一条属于M的边相连的点交错轨：属于M的边与不属于M的边交替出现的轨（链）可增广轨：两端点是未盖点的交错轨判断M是最大匹配的标准：M中不存在可增广轨2.最大匹配，匈牙利算法时间复杂度：O(|V||E|)原理：寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。

修改M 为M&P。

即这条轨进行与M进行对称差分运算。

所谓对称差分运算，就是比如X和Y都是集合，X&Y=(X并Y)-(x交Y)有一个定理是：M&P的边数是|M|+1，因此对称差分运算扩大了M实现：关于这个实现，有DFS和BFS两种方法。

先列出DFS的代码，带注释。

这段代码来自中山大学的教材核心部分在dfs(x)，来寻找可增广轨。

如果找到的话，在Hungarian()中，最大匹配数加一。

这是用了刚才提到的定理。

大家可以想想初始状态是什么，又是如何变化的view plaincopy to clipboardprint?第二种方法BFS，来自我的学长cnhawk核心步骤还是寻找可增广链，过程是：1.从左的一个未匹配点开始，把所有她相连的点加入队列2.如果在右边找到一个未匹配点，则找到可增广链3.如果在右边找到的是一个匹配的点，则看它是从左边哪个点匹配而来的，将那个点出发的所有右边点加入队列这么说还是不容易明白，看代码吧view plaincopy to clipboardprint?3.最佳匹配加权图中，权值最大的最大匹配KM算法：概念：f(v)是每个点的一个值，使得对任意u,v C V，f(u)+f(v)>=w[e u,v]集合H：一个边集，使得H中所有u,v满足f(u)+f(v)=w[e u,v]等价子图：G f(V,H)，标有f函数的G图理论：对于f和G f，如果有一个理想匹配集合M p，则M p最优。

设G=(V,{R})是一个无向图。

如顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。

则称图G为二分图。

v给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

v选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)v如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。

但是这个算法的复杂度为边数的指数级函数。

因此，需要寻求一种更加高效的算法。

匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M 的一条增广路径。

由增广路径的定义可以推出下述三个结论：v 1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。

v 2. P经过取反操作（即非M中的边变为M中的边，原来M中的边去掉）可以得到一个更大的匹配M’。

v 3. M为G的最大匹配当且仅当不存在相对于M的增广路径。

从而可以得到求解最大匹配的匈牙利算法：v(1)置M为空v(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替Mv(3)重复(2)操作直到找不出增广路径为止根据该算法，我选用dfs (深度优先搜索)实现。

程序清单如下：int match[i] //存储集合m中的节点i在集合n中的匹配节点,初值为-1。

int n,m,match[100]; //二分图的两个集合分别含有n和m个元素。

bool visit[100],map[100][100]; //map存储邻接矩阵。

bool dfs(int k){int t;for(int i = 0; i < m; i++)if(map[k][i] && !visit[i]){visit[i] = true;t = match[i];match[i] = k; //路径取反操作。

⼆分图匹配--匈⽛利算法⼆分图匹配--匈⽛利算法⼆分图匹配匈⽛利算法基本定义：⼆分图 —— 对于⽆向图G=(V,E)，如果存在⼀个划分使V中的顶点分为两个互不相交的⼦集，且每个⼦集中任意两点间不存在边 ϵ∈E,则称图G为⼀个⼆分图。

⼆分图的充要条件是，G⾄少有两个顶点，且所有回路长度为偶数。

匹配 —— 边的集合，其中任意两条边都不存在公共顶点。

匹配边即是匹配中的元素，匹配点是匹配边的顶点，同样⾮匹配边，⾮匹配点相反定义。

最⼤匹配——在图的所有匹配中，包含最多边的匹配成为最⼤匹配 完美匹配——如果在⼀个匹配中所有的点都是匹配点，那么该匹配称为完美匹配。

附注：所有的完美匹配都是最⼤匹配，最⼤匹配不⼀定是完美匹配。

假设完美匹配不是最⼤匹配，那么最⼤匹配⼀定存在不属于完美匹配中的边，⽽图的所有顶点都在完美匹配中，不可能找到更多的边，所以假设不成⽴，及完美匹配⼀定是最⼤匹配。

交替路——从⼀个未匹配点出发，依次经过⾮匹配边，匹配边，⾮匹配边…形成的路径称为交替路，交替路不会形成环。

增⼴路——起点和终点都是未匹配点的交替路。

因为交替路是⾮匹配边、匹配边交替出现的，⽽增⼴路两端节点都是⾮匹配点，所以增⼴路⼀定有奇数条边。

⽽且增⼴路中的节点(除去两端节点)都是匹配点，所属的匹配边都在增⼴路径上，没有其他相连的匹配边，因此如果把增⼴路径中的匹配边和⾮匹配边的“⾝份”交换，就可以获得⼀个更⼤的匹配(该过程称为改进匹配)。

⽰例图Fig1_09_09.JPG注释：Fig3是⼀个⼆分图G=(V,E),V={1,2,3,4,5,6,7,8},E={(1,7),(1,5),(2,6),(3,5),(3,8),(4,5),(4,6)},该图可以重绘成Fig4，V可分成两个⼦集V={V1,V2},V1={1,2,3,4},V2={5,6,7,8}。

Fig4中的红⾊边集合就是⼀个匹配{(1,5),(4,6),(3,8)}Fig2中是最⼤匹配Fig1中红⾊边集合是完美匹配Fig1中交替路举例(4-6-2-7-1-5)Fig4中增⼴路(2-6-4-5-1-7)匈⽛利树匈⽛利树中从根节点到叶节点的路径均是交替路，且匈⽛利树的叶节点都是匹配点。

⼆分图的最⼤匹配—匈⽛利算法【基本概念】：⼆分图：⼆分图⼆分图⼜称作⼆部图，是图论中的⼀种特殊模型。

设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和N，其中M或N中任意两个在同一集合中的点都不相连。

二分图匹配是指求出一组边，其中的顶点分别在两个集合中，并且任意两条边都没有相同的顶点，这组边叫做二分图的匹配，而所能得到的最大的边的个数，叫做最大匹配。

计算二分图的算法有网络流算法和匈牙利算法（目前就知道这两种），其中匈牙利算法是比较巧妙的，具体过程如下（转自组合数学）：令g=（x,*,y）是一个二分图，其中x={x1,x2...},y={y1,y2,....}.令m为g中的任意匹配。

1。

将x的所有不与m的边关联的顶点表上￥，并称所有的顶点为未扫描的。

转到2。

2。

如果在上一步没有新的标记加到x的顶点上，则停，否则，转33。

当存在x被标记但未被扫描的顶点时，选择一个被标记但未被扫描的x的顶点，比如xi，用（xi）标记y 的所有顶点，这些顶点被不属于m且尚未标记的边连到xi。

现在顶点xi 是被扫描的。

如果不存在被标记但未被扫描的顶点，转4。

4。

如果在步骤3没有新的标记被标记到y的顶点上，则停，否则转5。

5。

当存在y被标记但未被扫描的顶点时。

选择y的一个被标记但未被扫描的顶点，比如yj，用（yj）标记x的顶点，这些顶点被属于m且尚未标记的边连到yj。

现在，顶点yj是被扫描的。

如果不存在被标记但未被扫描的顶点则转道2。

由于每一个顶点最多被标记一次且由于每一个顶点最多被扫描一次，本匹配算法在有限步内终止。

代码实现：bfs过程：#include<stdio.h>#include<string.h>main(){bool map[100][300];inti,i1,i2,num,num1,que[300],cou,stu,match1[100],match2[300],pqu e,p1,now,prev[300],n;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d%d",&cou,&stu);memset(map,0,sizeof(map));for(i1=0;i1<cou;i1++){scanf("%d",&num);for(i2=0;i2<num;i2++){scanf("%d",&num1);map[i1][num1-1]=true;}}num=0;memset(match1,int(-1),sizeof(match1)); memset(match2,int(-1),sizeof(match2)); for(i1=0;i1<cou;i1++){p1=0;pque=0;for(i2=0;i2<stu;i2++){if(map[i1][i2]){prev[i2]=-1;que[pque++]=i2;}elseprev[i2]=-2;}while(p1<pque){now=que[p1];if(match2[now]==-1)break;p1++;for(i2=0;i2<stu;i2++){if(prev[i2]==-2&&map[match2[now]][i2]){prev[i2]=now;que[pque++]=i2;}}}if(p1==pque)continue;while(prev[now]>=0){match1[match2[prev[now]]]=now; match2[now]=match2[prev[now]]; now=prev[now];}match2[now]=i1;match1[i1]=now;num++;}if(num==cou)printf("YES\n");elseprintf("NO\n");}}dfs实现过程：#include<stdio.h>#include<string.h>#define MAX 100bool map[MAX][MAX],searched[MAX]; int prev[MAX],m,n;bool dfs(int data){int i,temp;for(i=0;i<m;i++){if(map[data][i]&&!searched[i]){searched[i]=true;temp=prev[i];prev[i]=data;if(temp==-1||dfs(temp))return true;prev[i]=temp;}}return false;}main(){int num,i,k,temp1,temp2,job;while(scanf("%d",&n)!=EOF&&n!=0) {scanf("%d%d",&m,&k);memset(map,0,sizeof(map));memset(prev,int(-1),sizeof(prev)); memset(searched,0,sizeof(searched));for(i=0;i<k;i++){scanf("%d%d%d",&job,&temp1,&temp2); if(temp1!=0&&temp2!=0)map[temp1][temp2]=true;}num=0;for(i=0;i<n;i++){memset(searched,0,sizeof(searched)); dfs(i);}for(i=0;i<m;i++){if(prev[i]!=-1)num++;}printf("%d\n",num);}}。

用匈牙利算法求二分图的最大匹配二分图的最大匹配有两种求法，第一种是最大流；第二种就是匈牙利算法。

这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。

最大流算法的核心问题就是找增广路径（augment path）。

匈牙利算法也不例外，它的基本模式就是：初始时最大匹配M为空while 找得到增广路径do 把增广路径加入到最大匹配中去可见和最大流算法是一样的。

但是这里的增广路径就有它一定的特殊性，下面我来分析一下。

（注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。

每条边也不需要有方向。

）图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个。

⼆分图匹配之匈⽛利算法⼆分图的基本概念：⼆分图⼜称作⼆部图，是图论中的⼀种。

设G=(V,E)是⼀个⽆向图，如果顶点V可分割为两个互不相交的⼦集(A,B)，并且图中的每条边(i，j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为⼀个⼆分图。

⽐如：我们⼀般把图的两部分称为X部和Y部，⼀个图的所有点如果能被两个独⽴的点集，那就认为这个图是⼆分图⼆分图的判断⼀般通过染⾊的⽅法来进⾏判段，可以写成dfs或则bfs的写法bool dfs(int v,int c){color[v]=c;for(int i=0;i<n;i++){if(edge[v][i]==1){if(color[i]==c) return false;if(color[i]==0&&!dfs(i,-c)) return false;}}return true;}void solve(){int flag=0;for(int i=0;i<n;i++){if(color[i]==0){if(!dfs(i,1)){cout<<"no"<<endl;flag=1;break;}}}if(!flag) cout<<"yes"<<endl;}bfs写法bool bfs(int s){color[s] = 1;queue<int> que;que.push(s);while(!que.empty()){int from = que.front();que.pop();for(int i = 1; i <= V; i++){// 如果相邻的点没有上⾊就给这个点上⾊if(G[from][i] && color[i] == 0){que.push(i);color[i] = -color[from];}// 如果相邻的颜⾊相同则返回falseif(G[from][i] && color[i] == color[from])return false;}}// 如果所有的点都被染过⾊，且相邻的点颜⾊都不⼀样，返回truereturn true;}接下来就是介绍匹配：⼀个匹配是⼀个边的集合，任何匹配的边之间没有公共顶点。

匈牙利算法描述匈牙利算法是图论中一种用于解决二分图匹配问题的算法。

它首次由匈牙利数学家Denzel匈牙利在1955年发表，因而得名。

匈牙利算法属于图匹配算法的范畴，在实际应用中有着很强的效率和准确性。

本文将介绍匈牙利算法的原理、实现方法和应用领域等相关内容。

一、匈牙利算法原理匈牙利算法是解决二分图最大匹配问题的经典算法之一。

在二分图中，匈牙利算法的目标是寻找图中的最大匹配，即尽可能多地找到满足匹配条件的边，也就是找到尽可能多的配对节点。

在匈牙利算法中，主要使用了增广路的概念，通过不断地寻找增广路，来不断地扩展匹配。

具体而言，匈牙利算法的核心思想是利用增广路径寻找最大匹配。

在每一次匹配的过程中，首先选择一个未匹配的节点，然后通过交替路径寻找增广路径，直到无法找到增广路径为止。

当无法找到增广路径时，说明找到了最大匹配。

增广路径指的是一条由未匹配的节点和匹配节点交替构成的路径，其中未匹配节点为起点和终点。

通过不断地寻找增广路径，可以逐步扩展匹配。

在匈牙利算法中，为了记录节点的匹配状态和寻找增广路径，通常使用匈牙利标号和匈牙利交错路的方式。

匈牙利标号是为每个节点标记一个代表节点匹配状态的值，而匈牙利交错路则是一种用于寻找增广路径的方法。

借助这些工具，匈牙利算法可以高效地解决最大匹配问题。

二、匈牙利算法实现方法匈牙利算法的实现方法较为复杂，需要结合图论和图匹配的相关知识。

在实际应用中，匈牙利算法通常通过编程实现，以解决特定的二分图匹配问题。

下面简要介绍匈牙利算法的一般实现方法。

1. 初始化匈牙利标号：首先对图中的所有未匹配节点进行初始化标号，即给它们赋予一个初始的匈牙利标号。

2. 寻找增广路径：选择一个未匹配的节点作为起点，通过交替路径和增广路的方法寻找增广路径。

在寻找增广路径的过程中，要根据节点的匈牙利标号来选择下一个节点，从而找到满足匹配条件的路径。

3. 匹配节点：如果成功找到一条增广路径，就可以将路径中的节点进行匹配，即将原来未匹配的节点与匹配节点进行匹配。

匈牙利规则
"匈牙利规则"通常指的是在图论中解决二分图匹配问题的一个算法，也称为匈牙利算法或Kőnig算法。

这个算法由匈牙利数学家Dénes Kőnig在1925年提出，用于寻找二分图中的最大匹配。

二分图是一种特殊的图，其顶点可以分成两个不相交的集合，并且图中的每条边都连接这两个集合中的一个顶点。

匈牙利算法的步骤如下：
1. 选择一个未匹配的顶点u from U，U是图中的一半顶点集合。

2. 对于u的每个邻接顶点v from V，如果v尚未匹配，则将其标记为未使用的。

3. 如果u的所有邻接顶点都已被使用，则算法结束，当前匹配是最大匹配。

4. 如果存在一个未使用的顶点v，则将v与u匹配，并转步骤1。

5. 如果u的所有邻接顶点都已被使用，但不是都与u匹配，选择一个与u匹配的顶点w，并找出通过u和w形成的未使用的环。

在这个环上，交替取消匹配的边，直到找到一个未匹配的顶点x。

6. 选择x的一个未使用的邻接顶点y，并取消u与y的匹配。

7. 匹配x和y，并转步骤1。

这个算法可以找到二分图中最大的匹配，并且在实现上相对高效。

它在理论计算机科学和组合优化中有着广泛的应用，例如在网络流问题、调度问题以及一些经济和生物信息学问题中。

匈牙利算法 by gqp1、算法原理：用找增广路的方式来解决二分图最大匹配问题。

流程大致如下。

（1）从一个点出发找增广路，直到所有点都找过。

（2）如果找到增更新路径并匹配数加1，重复（1）。

（3）如果未找到增广路则重复（1）。

这个算法很简单，就是找增广路。

所谓的增广路也就是在图中找到一条交错路（见图示，红色找过，蓝色没找过），也就是已经找过的边和未找过的边交替出现，并且开始和结尾都是没找过的。

如下图所示就是一条增广路。

我可以发现这条路一定是奇数，并且把这条路取反就可以获得一种更多匹配的方案，也就是把蓝色边取，而放弃红色边。

从实际出发就是本来是A ——C ，而现在发现D ——C 并且还有A ——B ，由于A 还可以匹配C 之外的点，而C 又可以被D 匹配，那么我们就用D 代替A ，让A 可以匹配其他点，这样显然方案变得更优。

而算法就是不断找增广路。

找到增广路就意味着我们的方案变得更优。

而当找不到方案时，一定就已经找到最优解。

我们可以这样考虑，如果没有达到最优，那么一定是有这样一种情况，有点C 已经匹配A ——C ，而这时C 还可被其他闲置点匹配且A 还可以匹配其他闲置点。

而这种情况与上图一致，我们可以发现这时一定可以找到增广路。

所以当找不到增广路时就找到了最优解。

2、算法实现，dfs 很简单，就不说了。

可以上网找代码。

不过递归总归是有缺点，于是我写了个bfs 来实现。

Dfs 实现和算法思想很一致，找到个点就增广，如果找到闲置点则找到增广路，否则看谁跟此点匹配，再继续找增广。

也就是一条路走完看是不是增广再找其他路。

而bfs 则是同时多路查找，一旦找到增广路就停止。

对于常见题目，稀疏的图，bfs 显然更好。

当然他们的复杂度差的不多，至少我跑十万点的图，时间上只差0.1以内。

不过由于栈的限制，所以还是bfs 更实用。

Bfs 的实现其实也很简单，不过要引入一个数组fa 来记录找寻的路径，因为bfs 无法回溯改路径，所以要记录每次查找的路径。

一、用匈牙利算法求二分图(二部图,偶图的最大匹配算法中的几个术语说明:1。

二部图:如果图G=(V,E的顶点集何V可分为两个集合X,Y,且满足X∪Y =V, X∩Y=Φ,则G称为二部图;图G的边集用E(G表示,点集用V(G表示。

2。

匹配:设M是E(G的一个子集,如果M中任意两条边在G中均不邻接,则称M是G的一个匹配。

M中的—条边的两个端点叫做在M是配对的。

3。

饱和与非饱和:若匹配M的某条边与顶点v关联,则称M饱和顶点v,并且称v是M-饱和的,否则称v是M-不饱和的。

4。

交互道:若M是二分图G=(V,E的一个匹配。

设从图G中的一个顶点到另一个顶点存在一条道路,这条道路是由属于M的边和不属于M的边交替出现组成的,则称这条道路为交互道。

5。

可增广路:若一交互道的两端点为关于M非饱和顶点时,则称这条交互路是可增广路。

显然,一条边的两端点非饱和,则这条边也是可增广路。

6。

最大匹配:如果M是一匹配,而不存在其它匹配M',使得|M'|>|M|,则称M是最大匹配。

其中|M|表示匹配M的边数。

7。

对称差:A,B是两个集合,定义A⊕B = (A∪B\(A∩B ,则称A⊕B为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,M←M⊕E(P,转2;6。

由于y已饱和,所以M中有一条边(y,z,作V1 ←V1∪{z}, V2←V2∪{y},转4;二、用匈牙利算法求二分图的最大匹配(伪代码给定一个二分图(x,y,x中的点和y中点的连接情况,一个匹配是二分图的子图,其中任一个x中的点只能和最多一个y中的点连接,一个y中的点也只能和一个x中的点连接,最大匹配就是使子图中的边数(我们称为匹配边最多的匹配。

匈牙利算法原理
匈牙利算法是一种用于解决二分图最大匹配问题的算法。

在二分图中，将图中的节点分为两个集合，分别为左侧节点集合和右侧节点集合，且左侧节点集合中的节点与右侧节点集合中的节点之间不存在边，只有左侧节点集合中的节点与右侧节点集合中的节点之间存在边。

二分图最大匹配问题就是找到一种最优的匹配方式，使得左侧节点集合中的每个节点都与右侧节点集合中的一个节点匹配。

匈牙利算法的基本思想是：从左侧节点集合中的每个节点开始，依次寻找与其匹配的右侧节点，如果找到了一个右侧节点，就将该右侧节点与左侧节点匹配，并继续寻找下一个左侧节点的匹配。

如果找不到一个右侧节点与该左侧节点匹配，就回溯到上一个左侧节点，并尝试匹配其他右侧节点，直到找到一个能够匹配的右侧节点或者所有的右侧节点都已经尝试过。

匈牙利算法的实现过程可以分为以下几个步骤：
1. 初始化：将所有的左侧节点都标记为未匹配状态。

2. 从左侧节点集合中的每个未匹配节点开始，依次进行匹配。

3. 对于每个未匹配节点，寻找与其相连的所有右侧节点，并尝试将其与该左侧节点匹配。

4. 如果找到了一个未匹配的右侧节点，就将该右侧节点与该左侧节点匹配，并将该左侧节点标记为已匹配状态。

5. 如果找不到一个未匹配的右侧节点与该左侧节点匹配，就回溯到上一个左侧节点，并尝试匹配其他右侧节点。

6. 如果所有的左侧节点都已经匹配完成，就得到了一个最大匹配。

7. 如果还存在未匹配的左侧节点，就说明无法找到一个最大匹配。

匈牙利算法的时间复杂度为O(n^3)，其中n为节点的数量。

虽然时间复杂度比较高，但是匈牙利算法在实际应用中表现良好，可以处理大规模的二分图最大匹配问题。

⼆分图匹配算法（最⼤流匈⽛利）⼆分图匹配相关概念⽆向⼆分图G(U⋃V,E)：U是⼀个顶点集合，V是另⼀个顶点集合，对于⼀个集合内的点⽆边直接相连，⽽对于不同集合的点可以连边，即(u,v)∈E。

匹配：两两不含公共端点的边的集合M称为匹配（就是两个集合之间连的边，只不过不同边的端点不能重合）最⼤匹配：元素最多的M，即⽽G中两两不含公共端点的边的集合M⊆E的基数|M|的最⼤值就是最⼤匹配。

完美匹配：当最⼤匹配的匹配数满⾜2∗|M|=V时，称为完美匹配。

形象的解释就是⼀各集合的所有点到另⼀个集合都有互不相同且唯⼀对应的点。

（类似于函数的双射），想象⼀下图增⼴路：设M为⼆分图G已匹配边的集合，若P是图G中⼀条连通两个未匹配顶点的路径（P的起点在X部，终点在Y部，反之亦可），并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的⼀条增⼴路径。

(就是连了两个还没有配对的顶点的路径，路径有⼀个配对边，⼀个⾮配对边交替组成)更多详细概念解释见匈⽛利部分的参考⽂章最⼤流的⽅法⼆分图的匹配可以看成是⼀种最⼤流问题（这谁想得出来啊）。

具体过程如下：现在有两个点集U和V，之间已经有了写连边，我们需要引⼊⼀个源，⼀个汇，把源跟集合U的所有点有向地连起来，把V的所有点和汇有向地连起来，就构成了⼀个流⽹络。

现在由于⼆分图匹配的限制，⼀个点不能连⾃⼰内部的点（在原来的⼆分图中这关系已经成⽴），不能连两个或多个边。

那么就把每个边的权值赋为⼀。

这样边的流量只有零壹两种，要么有边，要么不连边。

在上⾯跑最⼤流算法即可（具体讲解参见上篇博客）下⾯是代码：代码:#include <iostream>#include <memory.h>#include <vector>#include <queue>#define max_n 10005#define INF 0x3f3f3f3fusing namespace std;//邻接表struct edge{int v;//到达顶点int cap;//最⼤流量int rev;//对应反向边的编号};vector<edge> G[max_n];int level[max_n];//Dinic算法⽤到的层次图int iter[max_n];//当前弧优化void add_edge(int u,int v,int cap){G[u].push_back((edge){v,cap,G[v].size()});//最后⼀个表⽰uv这条边的反向边在G[v]⾥的标号G[v].push_back((edge){u,0,G[u].size()-1});}void bfs(int s)//处理层次图{memset(level,-1,sizeof(level));queue<int> que;level[s] = 0;que.push(s);while(!que.empty()){int v = que.front();que.pop();for(int i = 0;i<G[v].size();i++){edge& e = G[v][i];if(e.cap>0&&level[e.v]<0){level[e.v] = level[v]+1;que.push(v);}}}}int dfs(int v,int t,int f)//Dinic的dfs{if(v==t) return f;for(int& i = iter[v];i<G[v].size();i++){edge& e = G[v][i];if(e.cap>0&&level[e.v]==level[v]+1){int d = dfs(v,t,min(f,e.cap));if(d>0){G[e.v][e.rev].cap+=d;return d;}}}return 0;}int max_flow(int s,int t)//Dinic算法{int flow = 0;for(;;){bfs(s);if(level[t]<0){return flow;}memset(iter,0,sizeof(iter));int f;while(f=dfs(s,t,INF)>0){flow += f;}}}int N,K;//N,K为两个集合的点数bool can[max_n][max_n];//⼆分图中原有的边void solve(){//0~N-1是U中的点//N~N+K-1是V中的点int s = N+K;int t = s+1;for(int i = 0;i<N;i++)//s与U连边{add_edge(s,i,1);}for(int i = 0;i<K;i++)//t与V连边{add_edge(i+N,t,1);}for(int i = 0;i<N;i++){for(int j = 0;j<K;j++){if(can[i][j]){add_edge(i,j,1);//⼆分图原有边的链接}}}cout << max_flow(s,t) << endl;//求最⼤流即得最⼤匹配}int main(){cin >> N >> K;solve();return 0;}匈⽛利算法这个算法是专门处理⼆分图的最⼤匹配问题的，有很好的博客讲解，下⾯是推荐阅读⽅式：我上⾯的概念可能不太全，那就先来看看⼆分图的相关概念：可能还对增⼴路径不是很理解，什么是增⼴路，⾮配对配对交替什么的很混乱，那不妨先看看这个：现在到了算法流程了，在正式介绍前，先有个有趣⽽深刻的认识，下⾯是⼗分清晰的讲解：好了，该正式⼀点了，相信你也有了⼀定的了解：上⾯的代码其实已经够清晰了，如果还想看⼀下，就这篇吧：代码：#include <iostream>#include <memory.h>#define max_n 200005using namespace std;int n,m;int con_y[max_n];int visit[max_n];int head[max_n];struct edge{int v;int nxt;}e[max_n<<1];int cnt = 0;void add(int u,int v){++cnt;e[cnt].v = v;e[cnt].nxt = head[u];head[u] = cnt;}int dfs(int u){for(int i = head[u];i;i=e[i].nxt){int v = e[i].v;if(visit[v]==0){if(con_y[v]==-1||dfs(v))//结合上⾯算法流程部分的有趣博客再理解了⼀下这⾥的递归，好奇妙 {con_x[u] = v;con_y[v] = u;return 1;}}}return 0;}int Hungary(){memset(con_x,-1,sizeof(con_x));memset(con_y,-1,sizeof(con_y));int ans = 0;for(int i = 1;i<=n;i++){memset(visit,0,sizeof(visit));ans += dfs(i);}return ans;}int main(){cin >> n >> m;for(int i = 1;i<=m;i++){int a,b,c;cin >> a >> b;add(a,b);}cout << Hungary() << endl;return 0;}参考⽂章以上Processing math: 100%。

数学建模匈牙利算法
（实用版）
目录
一、匈牙利算法简介
二、匈牙利算法的基本原理
三、匈牙利算法的应用实例
四、匈牙利算法的优点与局限性
正文
一、匈牙利算法简介
匈牙利算法（Hungarian algorithm）是一种求解二分图最大匹配问题的经典算法，由匈牙利数学家 Mátyás Klán 首先提出。

该算法主要用于解决一些实际问题，如任务分配、资源调度等，其核心思想是尽可能地将两个顶点之间的距离缩小，从而实现图的最大匹配。

二、匈牙利算法的基本原理
1.匈牙利算法的基本思想是“贪心”，即每一步都选择当前可以得到的最佳匹配。

2.从未匹配的顶点中选择距离最小的两个顶点进行匹配，直到所有顶点都匹配完毕或者再也找不到匹配的顶点为止。

3.如果当前未匹配的顶点数量为奇数，则无法进行匹配，算法结束。

三、匈牙利算法的应用实例
1.任务分配：假设有 n 个任务和 n 个工人，每个工人完成不同任务的效率不同，匈牙利算法可以帮助我们找到最优的任务分配方案，使得总效率最大。

2.资源调度：假设有 m 个资源和 n 个任务，每个任务需要不同数量
的资源，匈牙利算法可以帮助我们找到最优的资源调度方案，使得总资源消耗最小。

四、匈牙利算法的优点与局限性
1.优点：匈牙利算法思路简单，计算效率较高，可以解决实际生活中的许多问题。

2.局限性：匈牙利算法只能解决无向图的最大匹配问题，对于有向图和带权图，需要进行相应的改进。