二分图的最大匹配（匈牙利算法的思想）

二分图的概念：二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。（来源于百度百科）

匹配的概念：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配.。

什么意思？我们给出下面这样的二分图（画的不好，见谅）

其中A E可以i匹配，AG也可以匹配，但是这俩个匹配不可以同时，也就是说一个点最多对应一个点，而点和点之间能否对应上还得看点与点是否有边。

最大匹配就是尽可能让匹配的边数最大。

这里我们采取二分图最大匹配（匈牙利算法）

算法思想：先拿上图这个样例说一下：当我们遍历到A这个点的时候，发现A可以匹配E,A可以匹配G，我们先让A匹配E，之后继续遍历B，C，D发现D只能匹配E,但是E已经被B匹配，这时我们回溯申请，看A可以不可以换一个匹配，发现可以，A可以与G进行匹配，而且此时G并没有点来与他匹配上，于是A与G匹配，D与E匹配。此图的最大匹配是4

设V为类似上图左边的点的集合，U为上图右边点的集合。不难看出这个算法方法在于 依次安排匹配，如果安排不了，就看我们安排的这个点V跟我们之前遍历的哪个点U匹配上了，看能否拆掉这个匹配给拆掉的点U换一个新的V，如果换的新的V也被其他U匹配上了，尝试去拆这个匹配，以此类推，直到把他们都安排好，如果有一环无法安排，那就代表这些匹配都无法拆去，那么需要我们拆掉匹配而安排的点就不需要安排了，因为它不会影响到最大匹配的数。

接下里看代码实现（俩个版本）

二分图的最大匹配（匈牙利算法）邻接矩阵版：https://blog.csdn.net/kirito9943/article/details/81436014

二分图的最大匹配（匈牙利算法）邻接表版：https://blog.csdn.net/kirito9943/article/details/81436210