阅读本文之前需要先看关于最大流的一些概念，我前面也写过。

1. 算法简介

二分图匹配是图论中研究二分图结构的经典问题，指在顶点集划分为两个独立子集的图中，选取互不相邻的边集，使得无法通过添加未匹配边来扩大匹配规模。最大二分匹配是一种特殊的最大流问题。

在图论的世界里，二分图是一种特殊且迷人的图结构。想象一下，有一群学生和一系列课程，每个学生只能选择某些特定的课程，而每门课程也只对部分学生开放，这样学生与课程之间的选课关系就可以用二分图来表示。在这个二分图中，学生是一组顶点，课程是另一组顶点，选课关系就是连接这两组顶点的边。

2. 算法推导

2.1 基本概念

2.1.1 二分图

二分图，又称二部图，它的顶点集V可以分割为两个互不相交的子集X和Y ，并且图中每条边连接的两个顶点，一个在X中，另一个在Y中，也就是说，X和Y内部的顶点彼此不相邻，如下图所示。

从图形上看，二分图就像是将所有顶点分成了两个阵营，所有的边都跨越这两个阵营，而阵营内部没有边相连。例如，在一场男女配对的活动中，男生组成一个集合，女生组成另一个集合，配对关系就是边，这就构成了一个二分图（注意一般是无向图）。

那如何判断二分图？常见方法是染色法：用两种颜色，对所有顶点逐个染色，且相邻顶点染不同的颜色，如果发现相邻顶点染了同一种颜色，就认为此图不是二分图。 当所有顶点都被染色且相邻顶点均不同色时判断此图为二分图。具体实现时可以用dfs和bfs两种方式去实现。

2.1.2 最大二分匹配

匹配：在图论中，一个匹配是一个边的集合，要求任意两条边都没有公共顶点。例如下图左右两部分中红色的边就是对应图的匹配，但是左图中的1-5、1-7两条边就不算匹配，因为他们有公共顶点1。

伴随而来的就有匹配点、匹配边、未匹配点、未匹配边。例如上面左侧图中1、4、5、7为匹配点，其他为未匹配点；1-5、4-7为匹配边，其他为非匹配边。

最大匹配：一个图中所有的匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。上面右图红线构成的匹配就是一个最大匹配，它包含4条匹配边。

最大二分匹配：是在这个二分图的基础上，寻找一组边的集合，使得集合中的任意两条边都没有公共顶点，并且这组边的数量达到最大。比如男女配对活动中，找到最多的配对组合，让尽可能多的男生和女生成功配对，并且每个男生和女生都只参与一次配对。在计算机科学和数学领域，最大二分匹配问题有着广泛的应用，比如任务分配、资源调度、电路设计等场景。例如，在任务分配中，将任务看作二分图的一个顶点集，将执行者看作另一个顶点集，任务与执行者之间的关系看作边，通过求解最大二分匹配，就可以找到最优的任务分配方案，使任务完成效率最大化。

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。上面右图红线构成的匹配也是一个完美匹配。显然，完美匹配一定是最大匹配（完美匹配的任何一个点都已经匹配，添加一条新的匹配边一定会与已有的匹配边冲突），但并非每个图都存在完美匹配。而且最大匹配和完美匹配有可能不唯一，但不同的最大匹配的边数是一样的。

最大匹配数：最大匹配的匹配边的数目。

最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择。

最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

最大独立数：选取最多的点，使任意所选两点均不相连。

以上定义对应着一个定理：

最大匹配数 = 最小点覆盖数（Konig 定理）最大匹配数 = 最大独立数最小路径覆盖数 = 顶点数 - 最大匹配数

2.1.3 增广路径

求解最大匹配问题需要一些算法支持，比如匈牙利算法，下面的概念也要提前了解。

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边....形成的路径叫做交替路。如下图中1-6、4-8为匹配边，8-1、6-2为非匹配边，两者交替形成的8-1-6-2就是交替路。

增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，上图中的一条增广路如下图所示（图中的匹配点均用红色标出）。

记住增广路和交替路的区别：当一条交替路径的起始和终点都不在匹配边的顶点上时，就是一条增广路径。我们可以通过不停找增广路来增加匹配中的匹配点和匹配边。找不到增广路时，达到最大匹配这就是（增广路定理）。在二分图最大匹配的求解过程中，增广路径是一个极为关键的概念，在一个已经有部分匹配的二分图中，我们可以通过增广路径来增加匹配的边数。

增广路径具有一些重要的性质：

（1）增广路径的长度必定为奇数，且其首尾边都不属于当前匹配M（因为它从非匹配顶点开始，以非匹配顶点结束，所以这两个顶点分别属于两个不同的集合且均未匹配，中间则交替经过匹配边和非匹配边，所以边的数量必然是奇数）；

（2）通过对增广路径进行取反操作，我们可以得到一个更大的匹配M’。怎么理解这句话呢。

（3）当且仅当不存在相对于当前匹配M的增广路径时，M才能成为图G的最大匹配。

在最大匹配问题中，我们不断寻找增广路径，当再也找不到增广路径时，此时的匹配就是最大匹配。这是因为只要存在增广路径，就意味着还可以通过调整边的匹配关系来增加匹配的数量，只有当不存在增广路径时，说明已经无法再增加匹配边数，也就达到了最大匹配状态。 增广路径就像是一把钥匙，为我们打开了寻找最大匹配的大门，通过不断利用它来调整匹配，最终找到二分图的最大匹配。

2.1.4 匈牙利树

匈牙利树是匈牙利算法中用于寻找二分图最大匹配的核心结构，通过交替路（匹配边与非匹配边交替组成的路径）构建，其构造方式有DFS和BFS两种：都是从未匹配点出发，沿交替路进行深度/宽度优先搜索，直到无法扩展 。匈牙利树用于寻找增广路径（可扩展匹配的路径），当无法找到增广路径时，当前匹配即为最大匹配 。注意匈牙利树是必须严格沿交替路扩展（匹配边与非匹配边交替） ，所有叶子节点都是匹配点，通过树结构判断是否存在增广路径，从而调整匹配 。

下图左侧存在一个叶子节点为非匹配点（7 号），因此这不是一棵匈牙利树。

2.2 匈牙利算法

匈牙利算法是求解二分图最大匹配的经典算法（叫做匈牙利算法的事实上有两个算法，分别解决指派问题和二分图最大匹配求解问题，此处算法指求解二分图最大匹配的匈牙利算法），它的工作原理基于增广路径的概念。该算法由匈牙利数学家 Edmonds （看过最大流问题的对这个名字肯定不陌生）于 1965 年提出，因此得名。

在铺垫了以上定义和概念原理之后，可以直接给出匈牙利算法的核心步骤如下：

（1）初始化匹配：从一个空的匹配开始，即所有顶点都未匹配。

（2）寻找增广路径：对于二分图中的每个未匹配顶点，尝试寻找一条从该顶点出发的增广路径。在寻找增广路径时，采用深度/宽度优先搜索（DFS、BFS）的策略。从当前未匹配顶点出发，沿着非匹配边访问相邻顶点，如果该相邻顶点未匹配，则找到了一条增广路径；如果该相邻顶点已匹配，则尝试让与该相邻顶点匹配的顶点寻找其他未匹配的邻接顶点，即通过递归的方式，尝试为已匹配顶点重新寻找匹配，以腾出位置给当前顶点，形成增广路径。

（3）更新匹配：一旦找到了增广路径，就对路径上的边进行取反操作，即将原来的匹配边变为非匹配边，非匹配边变为匹配边，这样匹配的边数就会增加 1。由于找到增广路之后需要沿着路径更新匹配，所以我们需要一个结构来记录路径上的点。DFS 版本通过函数调用隐式地使用一个栈，而 BFS 版本使用 prev 数组。

（4）重复步骤：不断重复上述寻找增广路径和更新匹配的过程，直到再也找不到新的增广路径为止。此时得到的匹配就是二分图的最大匹配。

匈牙利算法的递归思想体现在为已匹配顶点重新寻找匹配的过程中。当遇到一个顶点已匹配且当前未匹配顶点需要与其邻接顶点匹配时，通过递归调用函数，尝试为已匹配顶点在其邻接顶点中找到新的未匹配顶点，从而实现匹配的调整和增广路径的构建。这种递归的方式使得算法能够有效地在二分图中搜索所有可能的匹配组合，以找到最大匹配。 匈牙利算法通过巧妙地利用增广路径和递归搜索，为二分图最大匹配问题提供了一种高效的解决方案。

2.3 KM（Kuhn - Munkres）算法

匈牙利算法主要用于解决无权二分图的最大匹配问题，或者说在边权值都相等的情况下寻找最大匹配。除了匈牙利算法，还有一些其他算法也可用于求解最大二分匹配问题，其中比较著名的是 KM（Kuhn - Munkres）算法。

KM 算法主要用于解决带权二分图的最优匹配问题，也称为二分图的最大权匹配。在带权二分图中，每条边都有一个权值，KM 算法的目标是找到一种匹配方案，使得匹配边的权值总和最大，比如k个任务交给m个人完成，但是每个人的能力和效率是不一样的，如何分配能使得任务能最快完成。

2.3.1 顶点标号

与匈牙利算法相比，KM 算法引入了顶点标号（简称顶标）的概念。顶标是为二分图的每个顶点分配的一个数值，通过不断调整顶标值，并利用匈牙利算法的思想来寻找满足条件的匹配方案。具体来说，首先为每个顶点初始化顶标，使得对于任意边 (u, v)，都有顶标值之和大于等于边的权值（也称为可行顶点标号），即：

每个结点分配一个权值 l(i)，对于所有边 (u,v) 满足 w(u,v)≤l(u)+l(v)。

然后在寻找匹配时，只考虑顶标值之和等于边权值的边。如果在这个限制下无法找到完美匹配（即所有顶点都匹配），则调整顶标值，扩大可能的匹配边集合，继续寻找匹配。具体的调整策略为：

令，S和T分别为二分图x、y所在的集，对于每个顶点u，修改其标号为：

上面这个修改标号的过程是KM算法区别于匈牙利算法的地方。修改的目的是在目前找到的M匹配的基础上增加可行顶点，从而得到增广路。

例如，假设有一个带权二分图，左边顶点 A、B 与右边顶点 C、D 相连，边 (A - C) 权值为 3，边 (A - D) 权值为 1，边 (B - C) 权值为 2，边 (B - D) 权值为 4。

初始时设置顶标，假设左边顶点 A、B 顶标分别为 3、4，右边顶点 C、D 顶标分别为 0、0。按照顶标和边权值的关系，首先考虑边 (A - C) 和 (B - D) 进行匹配尝试。如果在这个过程中发现无法实现完美匹配，就调整顶标，比如降低左边顶点的顶标（-1），同时相应地调整右边顶点顶标（+1），以改变可能的匹配边组合，继续寻找最大权匹配。（还看不懂的话可以直接跳过去看实例分析）

2.3.2 相等子图

相等子图是在顶点标号基础上继续推进的概念，具体描述为：假如G是一个负权二部图，l是G的可行顶点标号，边（u,v）上的权为w(u,v)，令，G中以为边集的生成子图成为G的l相等子图，记为。

见下图，假设x和y两边之间的相互权重如左侧已给出，中间的x1顶上的5就是其顶点标号，因为x1与y1、y2、y3、y4的权重分别为3、5、5、4，5为最大，同理得到x2、x3、x4的顶点标号。首先看x1，满足与x1相连边权重为5的有y2、y3，所以保留x1与y2、y3之间的权重连线，然后看x2，满足与x2相连边权重为2的有y1、y2、y4，所以保留x2与y1、y2、y4之间的权重连线……得到相等子图。

可以这么说，相等子图是原来二分图抽取出重点链接部分的子图，但什么要做这件事呢？因为有这么一个定理：

设是赋权二部图G的一个可行顶点标号，若相等子图有完美匹配，则该完美匹配是G的最大权完美匹配。

在这个定理的保证之下，可以求出二分图的最大权完美匹配（当然，前提得是有完美匹配，如果没有完美匹配，那就使用实例分析中的求解过程求出最大权匹配）。

总体而言，KM 算法适用于需要考虑边权值的场景，如任务分配中不同任务与执行者之间的效益不同，希望找到总效益最大的分配方案；匈牙利算法则更适用于简单的最大匹配数量求解，如资源分配中只关注资源与需求的匹配数量最大化，不涉及匹配的质量差异 。在实际应用中，应根据具体问题的特点选择合适的算法来求解二分图的最大匹配。

2.4 Hopcroft-Karp算法

匈牙利算法和KM算法两个都一个比较大的问题，就是算法复杂度较高，都是（n为顶点数，m为边数），而HK算法的精确度更高、时间复杂度降低为。实际上HK算法也是在匈牙利算法上的优化，匈牙利算法在每次迭代中，只是找到一条增广路，然后基于该增广路，对当前解进行改进。但是每次迭代中，却往往存在多条增广路，如果能找到多条增广路，算法效果会得到进一步提升。而HK算法正式利用了这一点，但注意，HK和匈牙利算法一样，也无法处理带有权重的匹配。

2.4.1 基本原理

HK之所以快是因为采取了BFS+DFS策略，BFS负责分多条路径并行，DFS负责深入搜索。举个例子说明，如下图所示：

上述的匹配过程，如果使用匈牙利算法，会第一次匹配左1-右2（左侧图），第二次匹配时找到左2-右2-左1-右1的增广路径（第三幅图），得到第二次匹配结果左1-右1、左2-右2，然后再匹配3-3……它是一步一步匹配的，而实际上我们会发现，再第一幅图中，可缺点以同时开始匹配左1-右2和左3-右3两条路线，HK算法就是使用BFS同时开启多条增广路，然后在每条增广路中运用DFS进行延伸，上图同时对左1-右2和左3-右3两条路线增广后得到最右侧的完美匹配结果，可以明显的节约时间。

并且为了防止多条增广路重叠，在进行DFS深入搜索时还借鉴了Dinic算法的分层标记方法，HK大概思路为：用BFS对X部分的所有未被覆盖的点进行寻找增广路，列出所有的可行增广路，进行分层标记（距离标号），即（u,v）边的距离标号满足；再用类似匈牙利算法中的DFS对未被匹配的点进行匹配。

2.4.2 算法流程

这里总结一下HK的详细步骤（来自于文献，如果看不懂可先看实例分析，再回来看就能看懂了）。

（1）从G=(X,Y;E)中取一个初始匹配。

（2）若X中的所有顶点都被M匹配，则表明M为一个完美匹配，返回；否则，以所有未匹配顶点为源点进行一次BFS，标记各个点到源点的距离。

（3）在满足dis[v] = dis[u] + 1的边集<v,u>中，从X中找到一个未被M匹配的顶点x0，记S = {x0}，T 为空。

（4）若Next(S)= T，则表明当前已经无法得到更大匹配，返回；否则取一个y0∈N(S) - 。

（5）若y0已经被M匹配则转步骤（6），否则做一条x0->y0的M-增广路径P(x0,y0),更新M = M△P(x0,y0)。

（6）由于y已经被M匹配，所以M中存在一条边(x0,y0)，去S = S∪ {z0}，T = T∪{y0}，转步骤（2）。

3. 实例分析

3.1 匈牙利算法求解最大匹配

以图所示的二分图为例，我们可以使用匈牙利算法来求解其最大匹配。

（1）从顶点a出发，沿着交替路径前行，当遇到第一个非匹配边时，我们抵达了非匹配点e，从而形成了一条增广路径。随后，我们将这条增广路径中的匹配边和非匹配边进行交换，使得顶点a和e都成为了匹配顶点。

（2）接着，从顶点b出发，我们遇到的第一条非匹配边连接至顶点e。在e处，我们选择一条匹配边进入，进而抵达a点。在a点，我们再次选择一条非匹配边离开，这样，g点就成为了一个新的非匹配点。由此，我们找到了一条新的增广路径。

（3）通过交换增广路径中的匹配边与非匹配边，我们可以得到如下的新匹配。

（4）以顶点c为起点，我们找到的第一条非匹配边延伸至顶点e。接着，我们沿着交替路径前行，直至顶点b，但在此处无法再继续前进。

（5）继续从顶点c出发，我们探寻第二条非匹配边。

（6）接着，我们以顶点d为起点，寻找非匹配边，并沿着这条边移动至顶点g。在顶点g，我们选择匹配边，继续前行直至顶点a。在顶点a，我们再次选择非匹配边，移动到顶点e，并最终选择匹配边抵达顶部b。然而，在顶部b，我们并未找到可供选择的边，也没有发现增广路径的存在。

（7）从顶点d出发，我们再次选择非匹配边，并找到了增广路径。接下来，我们将这条增广路径上的某条边从非匹配状态转变为匹配状态，从而结束了整个算法的执行。

3.2 KM算法求最大权重匹配

下面使用KM算法解决带权二分图的最优匹配问题，各点之间的权重如下图所示。

（1）首先对左侧所以点赋值，也就是顶标，例如a点的外界连线有0.8和0.6，取较大的0.8，同理b、c、d的顶标分别为0.9、0.9、0.2，右侧全部初始为0，如下图所示：

（2）对于a点，与顶标分值相同的边先匹配（标蓝），同样b点找到与顶标相同的边匹配。

但是到c点时，我们发现与顶标相同的点为e，但是它已经跟a匹配了，于是重新找匹配，但是根据匹配原则，只能找大于等于(0.9+0=)0.9的边，而另一个f对象的权值为(0.8+0=)0.8<0.9，因此c无法换边。这时a能不能换边呢？对于a来说，只有权值大于等于(0.8+0=)0.8的边能满足要求，而另一匹配对象的权值为(0.6+0=)0.6<0.8，也无法换边。

（3） 此时根据KM算法，应该对所有冲突的边的顶点做加减操作。加减的幅度（注意这里出了c-e之间的增加幅度为0不算以外，仅剩f点，如果还有其他连线的话则需要比较，将最小的座位调整幅度），因此令左边顶点值减0.1，右边顶点值加0.1，结果如下图所示：

再进行匹配操作，发现c多了一条可匹配的边，因为此时c对f的匹配要求只需权重大于等于0.8+0即可，所以c与f可以匹配，得到结果如下：

（4）最后进行d的匹配。由于d唯一的匹配对象g已被b匹配，发生冲突。进行一轮加减d操作，再匹配，d还是匹配失败。两轮以后d期望值降为0，放弃匹配d。

至此KM算法流程结束，三对目标成功匹配。

3.3 HK算法求解最大匹配

以如下二分图为例（左部点集X={A,B,C}，右部点集Y={D,E,F}，边集E={(A,D),(A,E),(B,E),(B,F),(C,D)}）：

步骤1：初始化

• 所有顶点未匹配，匹配集M=∅。
• 左部未匹配点：A、B、C；右部未匹配点：D、E、F。

步骤2：第一轮BFS分层

• 起点：将左部未匹配点A、B、C加入队列，标记dx=0。

• 分层过程：

• 从A出发：访问D(dy[D]=1)、E(dy[E]=1)。因D、E未匹配，分层终止于dis=1。
• 从B出发：访问E(dy[E]已标记)、F(dy[F]=1)。
• 从C出发：访问D(dy[D]已标记)。

• 分层结果：

  
• X层：A(dx=0)、B(dx=0)、C(dx=0)
• Y层：D(dy=1)、E(dy=1)、F(dy=1)
• 最短增广路径长度dis=1。

步骤3：第一轮DFS增广

• 对左部未匹配点A、B、C依次DFS：

• A→D：D未匹配，形成增广路径，更新M={(A,D)}。
• B→E：E未匹配，形成增广路径，更新M={(A,D),(B,E)}。
• C→F：无边相连，失败。

• 匹配数增至2。

  

步骤4：第二轮BFS分层

• 起点：左部未匹配点C（A、B已匹配）。

• 分层过程：

• 从C出发：访问D(dy[D]=1)。D已匹配于A，继续访问A的匹配点A，标记dx[A]=2。
• 从A出发：访问E(dy[E]=3)。E已匹配于B，标记dx[B]=4。
• 从B出发：访问F(dy[F]=5)。F未匹配，分层终止于dis=5。

• 分层结果：

• X层：C(dx=0)→D(dy=1)→A(dx=2)→E(dy=3)→B(dx=4)→F(dy=5)

• 最短增广路径长度dis=5。

  

步骤5：第二轮DFS增广

• 从C出发DFS：

• C→D：D已匹配于A，递归访问A。

• A→E：E已匹配于B，递归访问B。

• B→F：F未匹配，形成增广路径C→D←A→E←B→F。

  

• 翻转路径：移除(A,D)、(B,E)，新增(C,D)、(A,E)、(B,F)，匹配集更新为{(C,D),(A,E),(B,F)}。

  

• 匹配数增至3，算法结束。

4. 算法总结

最大二分匹配广泛运用于社交网络分析、推荐系统、电路设计、考试安排等，涉及的匈牙利算法、Hopcroft-Karp算法和Kuhn-Munkres算法是三种常见的二分图匹配算法，它们在实现方式、时间复杂度和适用场景上有所差异。以下是它们的区别和优缺点：

4.1 匈牙利算法

• 实现方式：匈牙利算法使用深度优先搜索(DFS)来寻找增广路径，通过不断更新匹配的顶点对来找到最大匹配。
• 时间复杂度：匈牙利算法的时间复杂度为O(VE)，其中V是顶点数，E是边数。
• 优点：实现简单，易于理解和实现。
• 缺点：在稀疏图中，可能会遍历大量的边，导致算法效率较低。

4.2 Hopcroft-Karp算法

• 实现方式：Hopcroft-Karp算法基于广度优先搜索和层次图的思想，通过构建层次图和多次的广度优先搜索来寻找增广路径，直到无法找到新的增广路径为止。
• 时间复杂度：Hopcroft-Karp算法的时间复杂度为O(sqrt(V)E)，其中V是顶点数，E是边数。
• 优点：时间复杂度较低，在稠密图中表现优异。
• 缺点：实现较为复杂，需要构建层次图并进行多次广度优先搜索。

4.3 Kuhn-Munkres算法

• 实现方式：Kuhn-Munkres算法是一种带权二分图匹配算法，基于匈牙利算法的思想，在每次增广路径寻找后引入了辅助顶标的更新过程，通过不断优化辅助顶标来找到最优匹配。
• 时间复杂度：Kuhn-Munkres算法的时间复杂度为O(V^3)，其中V是顶点数。
• 优点：能够处理带有权重的二分图匹配问题，得到最优匹配。
• 缺点：时间复杂度较高，在大规模图中可能效率较低。

综合来说，匈牙利算法简单易懂但效率较低，适用于小规模问题；Hopcroft-Karp算法在稠密图中表现优异，适用于较大规模问题；Kuhn-Munkres算法适用于带权重的二分图匹配问题，可以得到最优匹配，但时间复杂度较高。选择算法时应根据具体情况和需求进行权衡。

5. 参考文献

（1）【经典算法】最大二分匹配理论及其Python实现：https://blog.csdn.net/xiaoyingxixi1989/article/details/153183654

（2）二分图最大匹配 —— 匈牙利算法：https://cloud.tencent.com/developer/article/2068928

（3）Kuhn-Munkres 算法详细解析：https://blog.csdn.net/liu_y_r/article/details/79219405

（4）利用匈牙利算法&Hopcroft-Karp算法解决二分图中的最大二分匹配问题：https://www.cnblogs.com/penseur/archive/2013/06/16/3138981.html

（5）二分图匹配算法：https://blog.csdn.net/qq_34213260/article/details/130859040

（6）二分图最大匹配之Hopcroft-Karp算法：https://blog.csdn.net/Wall_F/article/details/8248373

需要代码的自取：https://gitee.com/qingwang1987/My-Machine_learning/tree/master/81-BGM