匈牙利算法

来源：今日头条

一、定义

匈牙利算法（Hungarian algorithm），其核心就是寻找增广路径，是一种用增广路径求二分图最大匹配的算法。

匈牙利算法是一种在P问题内（多项式时间内）求解任务分配问题的组合优化算法。它推动了后来的原始对偶方法。

匈牙利算法是美国数学家哈罗德·库恩于1955年提出的。此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。

二、名词解释

1、二分图与匹配

二分图（Bipartite graph）又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，A、B内部的点不相交，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈A, j∈B)，则称图G为一个二分图。

如图2-1左边图转换成一个二分图。

图2-1

一个图为二分图的充分必要条件是至少有两个点，并且如果存在回路的话，那么回路的长度(长度指的是该回路连接的点的数目)必须为偶数。

二分图的匹配：

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

极大匹配是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。

最大匹配是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。匈牙利算法就是找出这样一个最大匹配的边数。对于图来说，最大匹配不是唯一的，但是最大匹配的大小是唯一的。

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完美匹配。图2-2中图d就是二分图的一个完全匹配（同时也是最大匹配），但是最大匹配不总是完全匹配。

例子1 如图2-2所示

图2-2

图a，图b，图c，图d中任意两条边的连接的顶点都没有相同的(换句话说，n条边必须连接2 * n个不相同的顶点)。所以他们都是图G的匹配。

例子2 如图2-3所示

图2-3

红线部分代表匹配或完美匹配。

2、增广路径

交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

增广路径：若P是图G中一条连通两个未匹配顶点的路径，并且属于M的边和不属于M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

换一个说法，从一个未匹配点出发，走交替路，如果途径另一个未匹配点，则这条交替路称为增广路。如图2-4所示，红色结点代表匹配结点， 红色边代表匹配边，黑色边代表非匹配边。

图2-4

增广路径：1 -> 2->3->4->5->6。1、6非匹配点，中间结点2、3、4、5是匹配点。黑色标记 1—>2、3—>4、5—>6是非匹配边，红色标记2-3、4-5是匹配边。

增广路径的首尾是非匹配点。因此，增广路径的第一条和最后一条边，必然是非匹配边；同时它的第二条边（如果有）和倒数第二条边（如果有），必然是匹配边；以及第三条边（如果有）和倒数第三条边（如果有），一定是非匹配边。

增广路径从非匹配边开始，匹配边和非匹配边依次交替，最后由非匹配边结束。这样一来，增广路径中非匹配边的数目会比匹配边大 1。

如果我们置换增广路径中的匹配边和非匹配边，由于增广路径的首尾是非匹配点，其余则是匹配点，这样的置换不会影响原匹配中的匹配点，匹配中不包含在该路径中的其他匹配边也不受到影响，因而不会破坏匹配；增广路径的置换，可以得到比原有匹配更大的匹配（具体来说，匹配的边数增加了 1）。

增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，匹配边数目比原来多了 1 条。

由于二分图的最大匹配必然存在（比如，上限是包含所有顶点的完全匹配），所以，在任意匹配的基础上，如果我们有办法不断地搜寻出增广路径，直到最终我们找不到新的增广路径为止，我们就有可能得到二分图的一个最大匹配。这就是匈牙利算法的核心思想。

唯一的问题在于，在这种贪心的思路下，我们如何保证不存在例外的情况，即：当前匹配不是二分图的最大匹配，但已找不到一条新的增广路径。

我们从反证法考虑，即假设存在这样的情况。因为当前匹配不是二分图的最大匹配，那么在两个集合中，分别至少存在一个非匹配点。那么情况分为两种：

1)、这两个点之间存在一条边——那么我们找到了一条新的增广路径，产生矛盾；

2)、这两个点之间不存在直接的边，即这两个点分别都只与匹配点相连——那么：

a、如果这两个点可以用已有的匹配点相连，那么我们找到了一条新的增广路径，产生矛盾；

b、如果这两个点无法用已有的匹配点相连，那么这两个点也就无法增加匹配中边的数量，也就是我们已经找到了二分图的最大匹配，产生矛盾。

在所有可能的情况，上述假设都会产生矛盾。因此假设不成立，亦即贪心算法必然能求得最大匹配的解。

由增广路径的定义可以推出的三个结论：

①P的路径长度必定为奇数，第一条边和最后一条边都不属于M；

②P经过置换(取反)操作可以得到一个更大的匹配M；

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

增广路的应用

• 增广路用于证明最大匹配问题。
• 增广路主要应用于匈牙利算法中，用于求二分图最大匹配。

3、匈牙利树

匈牙利树一般由 BFS 构造（类似于 BFS 树）。从一个未匹配点出发运行 BFS（唯一的限制是，必须走交替路），直到不能再扩展为止。如图2-5，由Fig.7，可以得到Fig.8的一棵 BFS 树。

图2-5

这棵树存在一个叶子结点为非匹配点（7号），但是匈牙利树要求所有叶子结点均为匹配点，因此这不是一棵匈牙利树（顺便说一句，Fig.8 中非匹配根节点2到非匹配叶结点7显然是一条增广路，沿这条增广路扩充后将得到一个完美匹配）。在Fig.9中，从2号结点出发就会得到一棵匈牙利树。

匈牙利树要求所有叶子结点均为匹配点，它就是把存在的可连接的匹配点都列出来。

4、二分图最大匹配数=最小点覆盖率

二分图的最小点覆盖的理解：找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。

三、匈牙利算法复杂度

设V为二分图左边的顶点数，E为二分图中边的数目。匈牙利算法的实现以与点集合 V 为基础，每次在集合V中选一个顶点 Vi 做增广路径的起点搜索增广路径。搜索增广路径需要遍历边及E内的所有边，遍历方法可以采用深度优先遍历（DFS），也可以采用广度优先遍历（BFS），无论什么方法，其时间复杂度都是 O(E)。
匈牙利算法每个顶点 Vi 只能选择一次，因此算法的整体时间复杂度是 O(V*E)，总的来说，是一个相当高效的算法。

四、举例说明

例子1

假设在婚介公司的手上有4位剩男，4位剩女，还没见面只是互相看了资料，每个人都对多名异性有好感。婚介公司做了一张互有好感关系图。如图4-1所示。

图4-1

是否可能让所有男孩和女孩一对一配对，使得每对儿都互相喜欢呢？在图论中，这就是完美匹配问题。如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。匈牙利算法就是为了求解最大匹配问题。

解法一

第1步 初始为空匹配。如图4-2所示。

图4-2

第2步 选择空匹配点Al、Alice，建立第1条增广路径Al—>Alice, 并进行置换，创建第1个匹配：红色标记Al**—>**Alice。如图4-3所示。

图4-3

第3步 选择空匹配点Bob，建立第2条增广路径Bob–>Carol, 并进行置换，创建第2个匹配：红色标记Bob—>Carol。如图4-4所示。

图4-4

第4步，选择空匹配点Christ，建立增广路径Christ—>Alice—>Al—>Beatrice

（增广路径满足：头部Christ、尾部Beatrice都是非匹配点， 中间Alice、Al都是匹配点；蓝色标记Christ—>Alice是非匹配边，红色标记Alice—>Al是匹配边，蓝色标记Al—>Beatrice是非匹配边）。如图4-5所示。

图4-5

第5步，置换增广路径中的匹配边和非匹配边。建立新的匹配：Christ—>Alice**—>**Al—>Beatrice

（红色标记Christ—>Alice是匹配边，Alice—>Al是非匹配边，红色标记Al—>Beatrice是匹配边）。如图4-6所示。

图4-6

第6步，选择空匹配点Dan，建立增广路径Dan—>Carol—>Bob—>Danielle

（增广路径满足：头部Dan、尾部Danielle都是非匹配点， 中间Carol、Bob都是匹配点；蓝色标记Dan—>Carol是非匹配边，红色标记Carol—>Bob是匹配边，蓝色标记Bob—>Danielle是非匹配边）。如图4-7所示。

图4-7

第7步，置换增广路径中的匹配边和非匹配边。建立新的匹配：Dan—>Carol—>Bob—>Danielle

（红色标记Dan—>Carol是匹配边，Carol—>Bob是非匹配边，红色标记Bob—>Danielle是匹配边）。如图4-8所示。

图4-8

已经无法添加新的增广路径了，算法结束。男女双方达到最大配对，红色标记最大配对边:{Al—>Beatrice，Bob—>Danielle，Christ—>Alice, Dan—>Carol}。

解法二

第1步 初始为空匹配。。如图4-9所示。

图4-9

第2步 选择空匹配点Al、Alice，建立第1条增广路径Al—>Alice, 并进行置换，创建第1个匹配：红色标记Al**—>**Alice。如图4-10所示。

图4-10

第3步，选择空匹配点Christ，建立增广路径Christ—>Alice—>Al—>Carol

（增广路径满足：头部Christ、尾部Carol都是非匹配点， 中间Alice、Al都是匹配点；蓝色标记Christ—>Alice是非匹配边，红色标记Alice—>Al是匹配边，蓝色标记Al—>Carol是非匹配边）。如图4-11所示。

图4-11

第4步，置换增广路径中的匹配边和非匹配边。建立新的匹配：Christ—>Alice**—>**Al—>Carol

（红色标记Christ—>Alice是匹配边，黑色标记Alice—>Al是非匹配边，红色标记Al—>Carol是匹配边）。如图4-12所示。

图4-12

第5步，选择空匹配点Dan，建立增广路径Dan—>Carol—>Al—>Beatrice

（增广路径满足：头部Dan、尾部Beatrice都是非匹配点， 中间Carol、Al都是匹配点；蓝色标记Dan—>Carol是非匹配边，红色标记Carol—>Al是匹配边，蓝色标记Al—>Beatrice是非匹配边）。如图4-13所示。

图4-13

第6步，置换增广路径中的匹配边和非匹配边。建立新的匹配：Dan—>Carol—>Al—>Beatrice

（红色标记Dan—>Carol是匹配边，Carol—>Al是非匹配边，红色标记Al—>Beatrice是匹配边）。如图4-14所示。

图4-14

第7步，选择空匹配点Bob，建立匹配边Bob–>Danielle。如图4-15所示。

图4-15

已经无法添加新的增广路径了，算法结束。男女双方达到最大配对，红色标记最大配对边:{Al—>Beatrice，Bob—>Danielle，Christ—>Alice, Dan—>Carol}。

例子2

匈牙利算法的核心是：不断寻找增广路，并扩展增广路。不断重复这一过程直到找不到增广路为止。如图4-16所示。

图4-16

具体步骤：

1. 首先从左边第一个点出发，寻找增广路黑色标记 1->2(没错，这个也是增广路)，然后翻转关系变为红色标记1->2。
2. 从左边第二个点出发，寻找增广路3->2->1->4,然后翻转关系变为红色标记3->2->1->4。
3. 从左边第三个点出发，寻找增广路5->4->1->2->3->6,然后翻转关系5->4->1->2->3->6。
4. 至此，我们已经找到二分图G的最大匹配数，同时这个也是完全匹配。

五、应用

例子1 矩阵游戏

**题目描述

**小Q是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 N×N黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：
行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）
列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）
游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
对于某些关卡，小Q百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小Q决定写一个程序来判断这些关卡是否有解。

解：

解题思路：我们把矩阵转化为二分图（左侧集合代表各行，右侧集合代表各列，某位置为1则该行和该列之间有边）。我们想进行一系列交换操作，使得X1连上Y1，X2连上Y2，……

假设N=4, 建立4×4的01矩阵。如图5-1所示。

图5-1

原问题变为将矩阵转化为二分图，求最大匹配。

图5-2

如图5-2所示，采用匈牙利算法，红色标记最大匹配为｛X1—>Y4, X2—>Y2, X3—>Y1, X4—>Y3｝。

结果矩阵为(如图5-3所示)：

图5-3

例子2 柯南开锁

面对OIBH组织的嚣张气焰, 柯南决定深入牛棚, 一探虚实.
他经过深思熟虑, 决定从OIBH组织大门进入………..
OIBH组织的大门有一个很神奇的锁.
锁是由M*N个格子组成, 其中某些格子凸起(灰色的格子). 每一次操作可以把某一行或某一列的格子给按下去.

图5-4

如果柯南能在组织限定的次数内将所有格子都按下去, 那么他就能够进入总部. 但是OIBH组织不是吃素的, 他们的限定次数恰是最少次数.
请您帮助柯南计算出开给定的锁所需的最少次数。

解：

解题思路

按下一行或一列，其实就是删掉与某个点相连的所有边。现在要求最少的操作次数，想想看，这不就是求最小点覆盖数吗？ 由Kőnig定理：二分图最小点覆盖数 = 最大匹配数，也就是求二分图的最大匹配，用匈牙利算法可解决此问题。

具体步骤

第1步，先将图5-4中的矩阵行与列分别设定了二分图中的集合X与Y，标出灰色格子对应的连接边。

第2步，采用匈牙利算法求出该二分图的最大匹配：{X2—>Y4, X4—>Y2}。如图5-5所示。

第3步，在图5-4中找到最大匹配所对应的灰色格子，灰色格子数就是开锁所需的最小次数。

图5-5

六、附录

附录1 相关概念与定理

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

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

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

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

最大匹配数=最大流=最小割=最小点集覆盖

定理1：最大匹配数 = 最小点覆盖数（这是Knig 定理）

定理2：最大匹配数量 = 顶点数 - 最大独立数

定理3：最小路径覆盖数 = 顶点数 - 最大匹配数

附录2 Kőnig定理及其证明

Kőnig定理：二分图中的最大匹配数等于这个图中的最小点覆盖数。

证明：

图6-1