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

今天是算法与数据结构专题的第31篇文章，我们一起来聊聊二分图匹配与匈牙利算法。

在上一篇文章当中我们介绍了一个有趣的稳定婚姻问题，模拟了男男女女配对的婚恋场景，并且研究了一下让匹配更加稳定的Gale-Shapley算法。如果错过了这篇文章的同学可以从下方的传送门回顾一下婚姻稳定问题的具体内容。

学算法还能指导找对象？是的，这就是大名鼎鼎的稳定婚姻算法

在上一篇文章的末尾我们曾经提到过，婚姻匹配问题本质上来说其实是二分图匹配的问题。那么什么又是二分图匹配呢？二分图匹配的问题又该通过什么算法来解决呢？下面就让我们一起从基础的概念开始。

二分图匹配

二分图的概念很简单，就是在一个无向图当中，所有的点可以分成两个子集。这两个子集当中的点各自互不相交，并且图当中的所有边关联的顶点都属于两个不同的集合。单纯用语言描述有一点吃力，其实我们找一张图看一下就明白了。

在上图当中很明显左边的竖着的三个点是一个集合，右边竖着的三个点是另外一个集合。两个集合之间有边相连，集合内部互不连通。

匹配与大匹配

在二分图当中，如果我们选择了一条边就会连通对应的两个点。这也就构成了一个匹配，我们规定一个顶点多只能构成一个匹配，也就是说所有的匹配之间没有公共的点。

对于一张二分图而言，构成的匹配数量可以是不同的，其中匹配数量多的情况叫做大匹配。如果所有顶点都有了匹配，那么就称这种情况为完美匹配。

今天要介绍的匈牙利算法就是一种用来完成二分图大匹配的算法。

匈牙利算法

匈牙利我们都知道是一个国家的名字，这和算法的发明人有关。匈牙利算法的发明人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算法只是二分图算法的一个特殊案例。

代码实现

匈牙利算法的思路如果学会了，代码其实非常简单，就是一个简单的递归调用。

def find_match(x):
    for i in range(n):
        if graph[x][i] and not tried[i]:
            tried[i] = True
            if match[i] == -1 or find_match(match[i]):
                match[i] = x
                return True
            
     return False


for i in range(n):
    tried = [ for _ in range(n)]
    find_match(i)

我们再试着用匈牙利算法来做一下婚姻稳定问题，因为在婚姻稳定问题当中每两个异性之间都有配对的可能，所以不需要再判断连通的情况了。并且构成的匹配有质量好坏的差别，所以需要去掉是否尝试过的判断。

girls_matched = [-1 for _ in range(n)]
boys_round = [ for _ in range(n)]
boys_matched = [-1 for _ in range(n)]


def find_match(x):
 for i in range(n):
        idx = girls[i].index(x)
        mate = girls_matched[i]
        mate_id = n+1 if mate == -1 else girls[i].index(mate)
        # 如果女孩i没有对象或者是对象比x男生弱
        if mate == -1 or (idx < mate_id and find_match(girls_matched[i])):
            girls_matched[i] = x
            boys_matched[x] = i
            return True
                
    return False


for i in range(n):
    # 对i男生进行匹配
    find_match(i)

我们运行一下这段代码：

结果当然是正确的，但是如果我们尝试用GS算法演示一下会发现这两个算法的结果不一样。这是为什么呢？原因也很简单，因为GS算法男生追求的顺序是自己喜好的顺序，而匈牙利算法当中是按照编号顺序，所以因此得到的结果不同。

总结

关于匈牙利算法的原理与介绍就到这里结束了，对于二分图匹配问题来说我们有很多种算法可以解决，但是匈牙利算法是其中比较简单易于理解与实现的一种。如果我们将它与之前介绍的GS算法相对比，可以发现很多共性和连通的部分。文中只是简单介绍了一些，如果仔细研究下去还会发现很多有趣的点。