二分图匹配----基于匈牙利算法和 KM 算法2025-05-1916:54设 G=(V,{R})是一个无向图。如顶点集 V 可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属两个不同的子集。则称图 G 为二分图。v 给定一个二分图 G，在 G 的一个子图 M 中，M 的边集{E}中的随意两条边都不依附于同一个顶点，则称 M 是一个匹配。v 选择这样的边数最大的子集称为图的最大匹配问题(maximal matching problem)v 假如一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。最大匹配在实际中有广泛的用处，求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。匈牙利算法是求解最大匹配的有效算法，该算法用到了增广路的定义(也称增广轨或交错轨)：若 P 是图 G 中一条连通两个未匹配顶点的路径，并且属 M的边和不属 M 的边(即已匹配和待匹配的边)在 P 上交替出现，则称 P 为相对于M 的一条增广路径。由增广路径的定义可以推出下述三个结论：v1.P 的路径长度必定为奇数，第一条边和最后一条边都不属于 M。v2.P 经过取反操作（即非 M 中的边变为 M 中的边，原来 M 中的边去掉）可以得到一个更大的匹配 M’。v3.M 为 G 的最大匹配当且仅当不存在相对于 M 的增广路径。从而可以得到求解最大匹配的匈牙利算法：v(1)置 M 为空v(2)找出一条增广路径 P，通过取反操作获得更大的匹配 M’代替 Mv(3)重复(2)操作直到找不出增广路径为止根据该算法，我选用 dfs (深度优先搜索)实现。程序清单如下：int match[i]//存储集合 m 中的节点 i 在集合 n 中的匹配节点,初值为-1。int n,m,match[100]; //二分图的两个集合分别含有 n 和 m 个元素。bool visit[100],map[100][100]; //map 存储邻接矩阵。bool dfs(int k){int t;for(int i =0; i < m; i++) if(map[k][i] && !visit[i]){ visit[i] = true; t = match[i]; match[i] = k; //路径取反操作。 if(t == -1 || dfs(t)) //寻找是否为增广路径 return true; match[i] = t;} return false;}int main(){//........... int s =0; memset(match,-1,sizeof(match)); for(i =0; i < n; i++){ //以二分集中的较小集为 n 进行匹配较优 memset(visit,0,sizeof(visit)); if(d...
