代码实现匈牙利算法的思路如果学会了，代码其实非常简单，就是一个简单的递归调用 。
def find_match(x):for i in range(n):if graph[x][i] and not tried[i]:tried[i] = Trueif match[i] == -1 or find_match(match[i]):match[i] = xreturn Truereturn 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] = xboys_matched[x] = ireturn Truereturn Falsefor i in range(n):# 对i男生进行匹配find_match(i)我们运行一下这段代码：
文章插图
结果当然是正确的，但是如果我们尝试用GS算法演示一下会发现这两个算法的结果不一样 。这是为什么呢？原因也很简单，因为GS算法男生追求的顺序是自己喜好的顺序，而匈牙利算法当中是按照编号顺序，所以因此得到的结果不同 。
总结关于匈牙利算法的原理与介绍就到这里结束了，对于二分图匹配问题来说我们有很多种算法可以解决，但是匈牙利算法是其中比较简单易于理解与实现的一种 。如果我们将它与之前介绍的GS算法相对比，可以发现很多共性和连通的部分 。文中只是简单介绍了一些，如果仔细研究下去还会发现很多有趣的点 。
今天的文章到这里就结束了，如果喜欢本文的话，请来一波素质三连，给我一点支持吧（关注、转发、点赞） 。
- END -
本文始发于公众号： TechFlow
【详解匈牙利算法与二分图匹配】
推荐阅读
- 万能的Windows定时开关机设置方法详解，不需要BIOS支持
- 鸡兔同笼子问题看算法在编程中的重要性，终于明白为何工资低了
- Github上复旦小姐姐原创「数据结构和算法系列」
- 桃花彩妆步骤详解 如何画出桃花彩妆
- TypeScript实现八大排序与搜索算法
- 详解DBSCAN聚类
- pytorch实现 GoogLeNet——CNN经典网络模型详解
- MySQL索引背后的数据结构及算法原理
- CNN中常用的四种卷积详解
- 新媒体运营黎想：详解用户活跃、留存、流失3大问题