详解匈牙利算法与二分图匹配 _匈牙利算法

今天是算法与数据结构专题的第31篇文章，我们一起来聊聊二分图匹配与匈牙利算法。
在上一篇文章当中我们介绍了一个有趣的稳定婚姻问题，模拟了男男女女配对的婚恋场景，并且研究了一下让匹配更加稳定的Gale-Shapley算法。如果错过了这篇文章的同学可以从下方的传送门回顾一下婚姻稳定问题的具体内容。
学算法还能指导找对象？是的，这就是大名鼎鼎的稳定婚姻算法?mp.weixin.qq.com
在上一篇文章的末尾我们曾经提到过，婚姻匹配问题本质上来说其实是二分图匹配的问题。那么什么又是二分图匹配呢？二分图匹配的问题又该通过什么算法来解决呢？下面就让我们一起从最基础的概念开始。
二分图匹配二分图的概念很简单，就是在一个无向图当中，所有的点可以分成两个子集。这两个子集当中的点各自互不相交，并且图当中的所有边关联的顶点都属于两个不同的集合。单纯用语言描述有一点吃力，其实我们找一张图看一下就明白了。

文章插图

在上图当中很明显左边的竖着的三个点是一个集合，右边竖着的三个点是另外一个集合。两个集合之间有边相连，集合内部互不连通。
匹配与最大匹配在二分图当中，如果我们选择了一条边就会连通对应的两个点。这也就构成了一个匹配，我们规定一个顶点最多只能构成一个匹配，也就是说所有的匹配之间没有公共的点。
对于一张二分图而言，构成的匹配数量可以是不同的，其中匹配数量最多的情况叫做最大匹配。如果所有顶点都有了匹配，那么就称这种情况为完美匹配。
今天要介绍的匈牙利算法就是一种用来完成二分图最大匹配的算法。
匈牙利算法匈牙利我们都知道是一个国家的名字，这和算法的发明人有关。匈牙利算法的发明人Edmonds在1965年提出了匈牙利算法，我也不知道为什么算法发明人是匈牙利的就叫匈牙利算法，也没见过其他以国家命名的算法，是因为匈牙利人提出的算法太少了吗？
匈牙利算法的核心原理非常简单，就是寻找增广路径，从而达成最大匹配。
我们用通俗易懂的语言来解释一下算法的含义，我们还用上面那张图作为举例。我们首先将左边的1和右侧的a，左边的2和右侧的b节点匹配。

文章插图

这样当我们想要匹配左侧的3号节点的时候发现了一个问题，那就是能够和3号节点构成匹配的a和b节点都已经被占据了。所以3号节点无法构成匹配，但是我们观察一下图就能发现，如果1和2号节点稍微调整一下匹配的情况，其实是可以给3号节点挪出一个位置来的。
具体怎么操作呢？
我们遍历3号节点能够匹配的节点，首先找到a节点，发现a节点已经被占用了。于是我们找到a节点匹配的节点也就是1号节点，试着让它重新找一个匹配，给3号节点挪出位置来。于是我们递归安排1号节点，我们遍历到b节点，发现b节点也被占用了。于是我们同样递归与b节点匹配的2号节点，看看2号节点能不能找到新的坑腾出一个位置来。
我们观察一下发现2号节点可以和c节点构成匹配，腾出位置来给1号，这样1号就能腾出位置来给3号节点了。所以最终的匹配结果就成了这样：

文章插图

其中蓝线是调整匹配之前的结果，红色是调整之后的结果。
本质上来说，匈牙利算法就是一个调整匹配的过程。通过递归调用的形式去尝试调整已经占据了发生冲突位置的匹配，腾出位置来给右面的节点。
我们把匈牙利算法的原理和Gale-Shapley算法比较一下，有没有发现什么？其实这两个算法的核心原理是一样的，在GS算法当中我们是先由男生发起追求，尽可能构成匹配。然后单身的男生再一轮一轮发起表白，如果有更好的匹配则断开之前的匹配。在稳定婚姻问题当中我们定义了匹配的好坏，而在原生的二分图匹配的问题当中匹配是不分好坏的。如果我们抛开匹配好坏不谈，把优质男生抢占劣质男生女朋友的过程看成是匹配调整的过程，那么其实这两个算法的核心几乎是一样的。
唯一不同的是GS算法是一轮一轮的迭代，直到所有节点完成匹配为止。因为在婚姻匹配问题当中是一定有完美匹配的解的，而二分图匹配的问题当中，完美匹配的情况可能不一定存在。所以我们不能使用这样迭代的方式进行，而使用递归进行更好一些。换句话来说匈牙利算法研究的是二分图匹配的通解，而GS算法只是二分图算法的一个特殊案例。