# 如何寻找男女之间最大的匹配数(匈牙利算法)? ## **问题来源:** 我司对外推出的是一个社交产品,其中有一个模块,是男女之间进行匹配的。假设一群男和一群女中,N对N产生好感,但是最终只能是1男配1女,如何寻找最大结果集? ## **问题描述:** 该问题可以采用匈牙利算法, 该算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。 ## **解决方案:** 关于匈牙利算法,网上有很多,但是都是C++的,少量用JAVA,但是经过作者核实,网上的匈牙利JAVA算法都有误。 下图的匈牙利卡通解释图来自网络,JAVA算法来自本文作者改造 > 算法流程 通过数代人的努力,你终于赶上了剩男剩女的大潮,假设你是一位光荣的新世纪媒人,在你的手上有N个剩男,M个剩女,每个人都可能对多名异性有好感(惊讶-_-||暂时不考虑特殊的性取向),如果一对男女互有好感,那么你就可以把这一对撮合在一起,现在让我们无视掉所有的单相思(好忧伤的感觉快哭了),你拥有的大概就是下面这样一张关系图,每一条连线都表示互有好感。