所谓二分图，是可以分为两个点集的图；
所谓二分图最大匹配，是两个点集之间，每两个不同点集的点连接,每个点只能连一个点，最大的连接数就是最大匹配。
如何解最大匹配，需要用到匈牙利算法。
匈牙利算法是一个递归的过程，它的特点，我觉得可以归为一个字：“让”。
例如这张图，按照匈牙利算法的思路就是：
1.1与5匹配，5没有被标记，将5标记，记录1与5匹配
2.清空标记
3.2与5匹配，5没有被标记，将5标记，发现5已经与1匹配，在[此处]重新递归1：
①1与5匹配，发现5已经被标记，跳出
②1与7匹配，发现7没有被标记，将7标记，记录1与7匹配，返回成功
4.回到2与5匹配的[此处]，发现返回成功，则直接记录2与5匹配
5.清空标记
6.3与5匹配，5没有被标记，将5标记，发现5已经与2匹配，在[此处]重新递归2：
①2与5匹配，发现5已经被标记，跳出
②2没有其他连接的边了，返回失败
7.回到3与5匹配的[此处]，发现返回失败，继续查找与3连接的边
8.3与6匹配，6没有被标记，将6标记，记录3与6匹配
9.清空标记
9.4与7匹配，7没有被标记，将7标记，发现7已经与1匹配，在[此处]重新递归1：
①1与5匹配，5没有被标记，将5标记，发现5已经与2匹配，在[此处A]重新递归2：
①2与5匹配，发现5已经被标记，跳出
②2没有连接的边了，返回失败
②回到1与5匹配的[此处A]，发现返回失败，继续查找1连接的边
③1与7匹配，发现7已经被标记，跳出
④1没有可以连接的边了，返回失败
10.回到4与7匹配的[此处]，发现返回失败，继续查找与4连接的边
11.4与8匹配，8没有被标记，将8标记，记录4与8匹配
12.清空标记
13.左边的点集枚举完毕，从记录中得到：1与7匹配，2与5匹配，3与6匹配，4与8匹配
这就是匈牙利算法（这就是人脑编译器吗）
原文：https://www.cnblogs.com/dudujerry/p/11519190.html