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