先把二分图的2侧命名为A侧和B侧。匈牙利算法求二分图的最大匹配有一个关键名词是增广路径，定义是：

若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。

例：（1）如果A侧一个点a1和B侧一个点b1之间有边相连，且边a1b1不在匹配中，且点a1、b1也不属于其他匹配边的点，那么a1b1是一条增广路径。换句话这么理解，对于一个二分图，初始情况下，任意A和B中相连的边都是增广路径。（2）如果有边a1b1、b1a2、a2b2，且b1a2属于匹配，a1b1、a2b2不属于匹配，且点a1和b2不属于其他匹配边的点，那么这3条边组成一个增广路径。

由增广路的定义可以推出下述三个结论：

1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。

2. P经过取反操作可以得到一个更大的匹配M’。

3. M为G的最大匹配当且仅当不存在相对于M的增广路径。

算法轮廓：

(1)置M（匹配）为空

(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M

(3)重复(2)操作直到找不出增广路径为止。

如果你没有学过这一算法，到这里应该能理解了。很多文章提到找增广路径就没下文了，完整的代码比较也比较难找，下面问题来了：（3）重复（2）怎么做？进一步细化，应该是这样的：

初始时最大匹配为空

for 二分图A侧的每个点i

do 从点i出发寻找增广路径

如果找到，则把它取反（即增加了总了匹配数）。

这个算法的正确性证明我还没做，先顾上实现再说。我们在设计算法的时候，一般不会想到去做正确性证明，一般算法书的贪心算法一章会涉及到正确性证明理论（拟阵），但是很少引起重视。遇到这个问题就知道正确性证明的重要性了，否则总是有点不放心。可以先体会一下：加入我们从A侧每个点出发都能找到增广路径使最大匹配加一，那么最后得到的最大匹配的边数和A侧点的数目一样，即A侧的点都用上了，自然是最大匹配。

到这里还没完，顶多算是会了1/2，对于循环中的每一次找增广路径，实现起来也不是特别简单。想起图灵奖获得者一个著名的公式：“程序=算法+数据结构”。我没看过发表这个言论的论文，以前我对这句话总是持一种不确定的感觉，或者需要更多印证。后来我在写算法程序的过程中终于意识到，这句话的意思是说，如果只大体上弄懂了算法轮廓，其实还差的远，只有把这个算法在合适的数据结构下实现出来，才算是真的懂了，因为从懂得算法框架到实现出来这之间有时候还有很大的差距。这只是悟出的一个方面。

算法进一步细化：把二分图分为A、B两侧，这种方法可以看作对A侧的深度遍历，A侧和B侧的点处理方法不同。

复制代码

对于二分图A侧（可以把点少的一侧看作A侧）的每个点，依次如下操作：

1.设置A[i]为当前点。

2.用A侧和B侧的点轮流进行如下操作。

（1）对A侧的点A[i]：找到一条没有匹配的边。如果边的B侧的点不属于匹配中另外的边，那么这个时候表示增广路径找到了（初始情况下直接相连的一条边的最大匹配就属于这种情况），修改最大匹配。如果边的B侧的点属于匹配中另外的边，设B侧的点为B[j]，则进入（2）。如果这些都做不到，需要进行回溯。如果回溯到了起点，表明从起点A[i]找增广路径失败了。注意，能否找到增广路径全由A侧的点决定（找边和回溯），B侧的点做的操作非常简单。

（2）对B侧的点B[j]，由于是找增广路径，已匹配的边需要用到，故直接找到B[j]所在的匹配边在A侧对应的点A[k]，把A[k]置为当前点继续进行步骤（1）。

复制代码

在这个过程中用一个队列记录寻找增广路径在A和B中经过的点，便于回溯和找到增广路径后修改最大匹配。

在自己设计算法的时候，伪代码的作用就体现出来了。下面是在伪代码的基础上完整的实现代码：

复制代码

#include

#include

using namespace std;

const int COUNTA=6,COUNTB=7; //二分图A、B两边点的数量

int connection[COUNTA][COUNTB] = {0}; //存放A、B两侧点的连接（边）

int match[COUNTA][COUNTB] = {0}; //A、B两侧点的匹配

struct elem{

int element;

int currentpartner;

};

deque que;

void init()

{

connection[0][0] = 1;

connection[0][1] = 1;

connection[0][3] = 1;

connection[1][1] = 1;

connection[1][4] = 1;

connection[2][0] = 1;

connection[2][3] = 1;

connection[2][6] = 1;

connection[3][2] = 1;

connection[3][3] = 1;

connection[3][5] = 1;

connection[4][3] = 1;

connection[5][3] = 1;

}

bool bPointInMatch(int point)//判断B中某个点是否在匹配中

{