摘要:匈牙利算法 求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。增广路的定义(也称增广轨或交错轨):若P是图G中一条连通两个未匹配顶点的路径,并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现,则称P为相对于M的一条增广路径。 由增广路的定义可以推出下述三个结论: 1-P的路径长度必定为奇数,第一条边和最后一条边都不属于M。2-P经过取反操作可以得到一个更大的匹配M’。3-M为[阅读全文]