二分图匹配(匈牙利算法).doc

v      给定一个二分图G,在G的一个子图M中,M的边集{E}中的任意两条边都不依附于同一个顶点,则称M是一个匹配。v      选择这样的边数最大的子集称为图的最大匹配问题(maximalmatchingproblem)v      如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。最大匹配在实际中有广泛的用处,求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。匈牙利算法是求解最大匹配的有效算法,该算法用到了增广路的定义(也称增广轨或交错轨):若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。由增广路径的定义可以推出下述三个结论:v      ,第一条边和最后一条边都不属于M。v      (即非M中的边变为M中的边,原来M中的边去掉)可以得到一个更大的匹配M’。v      。从而可以得到求解最大匹配的匈牙利算法:v      (1)置M为空v      (2)找出一条增广路径P,通过取反操作获得更大的匹配M’代替Mv      (3)重复(2)操作直到找不出增广路径为止根据该算法,我选用dfs(深度优先搜索)实现。程序清单如下:intmatch[i]//存储集合m中的节点i在集合n中的匹配节点,初值为-1。intn,m,match[100];                     //二分图的两个集合分别含有n和m个元素。boolvisit[100],map[100][100];              //map存储邻接矩阵。booldfs(intk){intt;for(inti=0;i<m;i++)    if(map[k][i]&&!visit[i]){     visit[i]=true;     t=match[i];     match[i]=k;                           //路径取反操作。     if(t==-1||dfs(t))//寻找是否为增广路径      returntrue;     match[i]=t;}    returnfalse;}intmain(){//...........    int   s=0;    memset(match,-1,sizeof(match));    for(i=0;i<n;i++){     //以二分集中的较小集为n进行匹配较优     memset(visit,0,sizeof(visit));     if(dfs(i))         s++;         //s为匹配数    }//............return0;}什么是二分图,什么是二分图的最大匹配,这些定义我就不讲了,网上随便都找得到。二分图的最大匹配有两种求法,第一种是最大流(我在此假设读者已有网络流的知识);第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法,但是它跟据二分图匹配这个问题的特点,把最大流算法做了简化,提高了效率。匈牙