二分图最大匹配.doc

二分图的最大匹配就是要在二分图的边集E中找到一个子集S，使S中的任两条边没有公共顶点，且｜S｜达到最大。二分图有很多实际应用，如工作分配问题。同时二分图最大匹配问题又可以转化成“最小顶点覆盖”、“最小路径覆盖”、“最大独立集“等问题，因此显得非常重要。下面就介绍二分图最大匹配算法。二分图最大匹配可以转换成最大流问题来解。假设二分图的两个顶点集分别为X， Y，那么我们在图中添加一个源s，和一个汇t。同时，在s与X的每个顶点间加一条有向边(s, vx)，在Y的每个顶点与t间加一条有向边(vy, t)。X与Y的每条边也变为X－Y的有向边。图中每条边的容量为1。则最大匹配问题就转换为求转换后的图G的最大流的问题。利用Ford－Fulkerson方法求最大流，时间复杂度为O（VE）， V为顶点数，E为边数。具体证明参考《算法导论》。经典的求二分图最大匹配的算法是Edmond于1965年提出的匈牙利算法。算法的核心思想是由一个初始匹配不断找增广路，直到找不到增广路为止。这里的增广路和网络流中的增广路有些不同。这里的增广路是这样的一条路：设已有的匹配为M，它的第一条边不在M中，最后一条边也不在M中，中间为在M中的边与不在M中的边交错出现。显然，这条路起点在X中，终点在Y中，且不在M中的边比在M中的边多1。所以我们若对增广路中的边进行取反，即原来不是匹配边的边变为匹配边，原来是匹配边的边变为不是匹配边的边，则我们能获得一个更大的匹配。所以这么一直找下去，直到找不到增广路为止，我们最后得到的匹配M就是要求的最大匹配。匈牙利算法中，初始匹配我们可以设为空，然后用DFS或者BFS找增广路。找一条增广路的复杂度为O（E），最多找V条增广路，故算法时间复杂度为O（VE）。下面给出匈牙利算法的两种实现：1.DFS找增广路 #include iostream#include cstringusing namespace std;const int MAXN = 100;int uN, vN; // u,ｖ数目 bool g[MAXN][MAXN]; // g[i][j] 表示 xi与yj相连 int xM[MAXN], yM[MAXN]; // 输出量 bool chk[MAXN]; // 辅助量 检查某轮 y[v]是否被check bool SearchPath(int u){ int v; for(v = 0; v vN; v++) { if(g[u][v] !chk[v]) { chk[v] = true; if(yM[v] == -1 || SearchPath(yM[v]))  { yM[v] = u; xM[u] = v; return true ; } } } return false ;}int MaxMatch(){ int u; int ret = 0 ; memset(xM, -1, sizeof (xM)); memset(yM, -1, sizeof (yM)); for(u = 0; u uN; u++) { if(xM[u] == -1) { memset(chk, false, sizeof (chk)); if(SearchPath(u)) ret++; } } return ret;} 优点：实现简洁，容易理解，适用于边比较多的图，DFS找增广路快。2.BFS找增广路 #include iostream#include cstringusing namespace std;#define MAXN 128int g[MAXN][MAXN], Mx[MAXN], My[MAXN], Nx, Ny;int chk[MAXN], Q[MAXN], prev[MAXN];int MaxMatch(void){ int res = 0; int qs, qe;  memset(Mx, -1, sizeof(Mx)); memset(My, -1, sizeof(My)); memset(chk, -1, sizeof(