本文起自个人公众号：TechFlow，原创难，敬请关注
今天是算法与数据结构专题的第31篇文章，谈谈二分图匹配和匈牙利算法吧。
上一篇文章介绍了一个有趣的稳定婚姻问题。 研究了一种Gale-Shapley算法，模拟温柔群体配对的婚姻场景，使匹配更加稳定。 错过这篇文章的同学可以从下面的传送门回顾婚姻稳定问题的具体内容。
也可以通过学习算法来指导寻找对方吗？ 是的，这就是有名的稳定的婚姻算法
如前一篇文章结尾所述，婚姻匹配问题本质上是二分图匹配的问题。 那么，什么是二分图匹配呢？ 二分图匹配问题应该用什么算法来解决呢？ 那么，从基本概念开始吧。
二分图与二分图一致的概念很简单，在一个无向图中，所有点都可以分为两个子集。 在这两个子集中，点各自互不相交与图中所有边相关联的顶点属于两个不同的集合。 单纯用语言说明有点费劲，但实际上找一下图就知道了。
如上图所示，左边垂直的三个点是一个集合，右边垂直的三个点是另一个集合。 两个集合之间边相连，集合内部互不相连。
匹配和最大匹配在二分图中，选择一边连接对应的两点。 这构成了匹配，规定一个顶点最多只能构成一个匹配，即所有匹配之间没有共同之处。
对于一幅二分图，构成的匹配数可以不同，其中匹配数最多的情况称为最大匹配。 如果所有顶点都匹配，这称为完全匹配。
今天介绍的匈牙利算法是实现二分图最大匹配的算法。
匈牙利算法我知道匈牙利是国家的名字。 这和算法的发明者有关。 匈牙利算法的发明者Edmonds在1965年提出了匈牙利算法。 为什么算法的发明者把匈牙利的东西称为匈牙利的算法，也没有见过与其他国家相关的算法。 是因为匈牙利人提出的算法太少了吗？
匈牙利算法的核心原理非常简单，为寻找增广路径，达到最大匹配。
试着用通俗易懂的语言说明算法的意思吧。 以上图为例。 首先，匹配左侧1和右侧的a节点，左侧2和右侧的b节点。
这样尝试匹配左侧的第三个节点时，发现了能够匹配第三个节点的a和b节点已经被占用的问题。 因此，虽然3号节点不能构成匹配，但从图中可以看出，只要1号节点和2号节点稍微调整匹配情况，其实就可以将3号节点的位置错开。
具体怎么操作？
我们查了三号节点可以匹配的节点，首先找到了a节点，发现a节点已经被占用了。 因此，找到a节点一致的节点，即1号节点，试着让它重新找一个匹配，错开3号节点的位置。 于是我们递归地配置了第一个节点，遍历到b节点，发现b节点也被占用了。 因此，我们同样递归地调查与b节点匹配的2号节点，调查2号节点是否能找到新的孔并空出位置。
观察后发现，第二个节点与第c个节点匹配。 将位置放在第一个节点上，第一个可以将位置放在第三个节点上。 最终的匹配结果是这样的：
其中蓝线是调整匹配前的结果，红线是调整后的结果。
本质上，匈牙利算法是调整匹配的过程。 尝试调整以递归调用形式占据冲突发生位置的匹配，将位置放置在右侧节点上。
比较一下匈牙利算法的原理和Gale-Shapley算法。 找到什么了吗？ 其实这两种算法的核心原理是一样的，在GS算法中我们先从男生开始追求，尽量构成匹配。 然后单身男性再次开始告白，如果有更好的匹配就断绝之前的匹配。 在稳定婚姻的问题上定义了匹配的好坏，而在原生二分图匹配的问题上匹配没有好坏之分。 暂且不谈匹配的好坏，如果把高质量男人切断低质量男人女朋友的过程看作匹配调整的过程，其实这两种算法的核心是差不多的。
唯一的区别是，GS算法是重复的，直到所有节点都完成匹配。 在婚姻匹配问题上一定有完美匹配的解，在二分图匹配问题上是完美匹配的情况可能不一定存在，所以最好是递归进行，而不是用这种迭代的方法进行。 也就是说，匈牙利算法研究的是二分图匹配的一般解，而GS算法是二分图算法的特例。
记住了实现匈牙利算法的代码思路后，代码实际上是一个非常简单、简单的递归调用。
def find _ match [ x ] : foriinrange [ n ] : if graph [ x ] [ I ] and not tried [ I ] 3360 tried [ I ]=trueifmatch [ I ]
match(match[i]): match[i] = x return True return Falsefor i in range(n): tried = [0 for _ in range(n)] find_match(i)我们再试着用匈牙利算法来做一下婚姻稳定问题，因为在婚姻稳定问题当中每两个异性之间都有配对的可能，所以不需要再判断连通的情况了。并且构成的匹配有质量好坏的差别，所以需要去掉是否尝试过的判断。
girls_matched = [-1 for _ in range(n)]boys_round = [0 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 Falsefor i in range(n): # 对i男生进行匹配 find_match(i)我们运行一下这段代码：
结果当然是正确的，但是如果我们尝试用GS算法演示一下会发现这两个算法的结果不一样。这是为什么呢？原因也很简单，因为GS算法男生追求的顺序是自己喜好的顺序，而匈牙利算法当中是按照编号顺序，所以因此得到的结果不同。
总结
关于匈牙利算法的原理与介绍就到这里结束了，对于二分图匹配问题来说我们有很多种算法可以解决，但是匈牙利算法是其中比较简单易于理解与实现的一种。如果我们将它与之前介绍的GS算法相对比，可以发现很多共性和连通的部分。文中只是简单介绍了一些，如果仔细研究下去还会发现很多有趣的点。
今天的文章到这里就结束了，如果喜欢本文的话，请来一波素质三连，给我一点支持吧（关注、转发、点赞）。