# 如何尋找男女之間最大的匹配數(匈牙利算法)? ## **問題來源:** 我司對外推出的是一個社交產品，其中有一個模塊，是男女之間進行匹配的。假設一群男和一群女中，N對N產生好感，但是最終只能是1男配1女，如何尋找最大結果集？ ## **問題描述:** 該問題可以采用匈牙利算法, 該算法是由匈牙利數學家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall定理中充分性證明的思想，它是部圖匹配最常見的算法，該算法的核心就是尋找增廣路徑，它是一種用增廣路徑求二分圖最大匹配的算法。 ## **解決方案:** 關于匈牙利算法，網上有很多，但是都是C++的，少量用JAVA，但是經過作者核實，網上的匈牙利JAVA算法都有誤。 下圖的匈牙利卡通解釋圖來自網絡，JAVA算法來自本文作者改造 > 算法流程 通過數代人的努力，你終于趕上了剩男剩女的大潮，假設你是一位光榮的新世紀媒人，在你的手上有N個剩男，M個剩女，每個人都可能對多名異性有好感（驚訝-_-||暫時不考慮特殊的性取向），如果一對男女互有好感，那么你就可以把這一對撮合在一起，現在讓我們無視掉所有的單相思（好憂傷的感覺快哭了），你擁有的大概就是下面這樣一張關系圖，每一條連線都表示互有好感。