二分图匹配的基本思想（匈牙利算法）

二分匹配
1、二分图
在一个图中，以边为条件，能够将两个端点划分为两个集合的图叫做二分图，比如：

2、二分图匹配算法（匈牙利算法）
二分图匹配就是找到一个边的集合，是的图中每个顶点的度数为1；
比如目标是：

二分图的完美匹配：就是所有的顶点都有匹配点，这样的叫做完美匹配，上图中的所有点都有匹配点，所以可以成为完美匹配。
那二分图的匹配一般可以用匈牙利算法，匈牙利算法的核心思想是：能上就上，不能上创造条件也要上。

举个栗子：

Step1：首先给1号同学找对象，找到5号，所以可以；

Step2:再给2号同学找对象，2号找到了5号，但是5号已经有对象了，所以让1号和5号分手，那么1号能够找到7号，所以1号可以，那么此时2号也可以，和5号。所以结果为：

Step3:再给3号找对象，3号找到了5号，于是让2和5分手，但是如果2和5分手，那么2就找不到对象了，所以3只有继续找另一个合适的了，于是找到了6，此时6是单身，所以可以匹配。所以3-6；

Step4:然后再给4找对象，4找到了7.于是让1和7分手，但是1和7分手之后，找不到新得对象，所以4只有再找其他对象，于是4找到了8，因为8也是单身，所以8可以和4匹配，那么就为：

SO：那么此时所有的点都有对应的唯一对象了，所以此时已经完美匹配了，算法结束。这就是匈牙利算法的基本思想了。