二分图的概念
二分图的性质
定理：当且仅当无向图G的每一个回路的次数均是偶数时，G才是一个二分图。如果无回路，相当于任一回路的次数为0，故也视为二分图。
二分图的判定
二分图匹配
最大匹配
选择边数最大的子图称为图的最大匹配问题(maximal matching problem)
如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
图中所示为一个最大匹配，但不是完全匹配。
增广路径
寻找增广路
红边为三条已经匹配的边。从X部一个未匹配的顶点x4开始，找一条路径：
x4,y3,x2,y1,x1,y2
因为y2是Y部中未匹配的顶点，故所找路径是增广路径。
其中有属于匹配M的边为{x2,y3},{x1,y1}
不属于匹配的边为{x4,y3},{x2, y1}, {x1,y2}
可以看出：不属于匹配的边要多一条！
如果从M中抽走{x2,y3},{x1,y1}，并加入{x4,y3},{x2, y1}, {x1,y2}，也就是将增广路所有的边进行”反色”,则可以得到四条边的匹配M’={
{x3,y4}, {x4,y3},{x2, y1}, {x1,y2}}
容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对。另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.
可知四条边的匹配是最大匹配
增广路径性质
由增广路的定义可以推出下述三个结论：
- P的路径长度必定为奇数，第一条边和最后一条边都不属于M，因为两个端点分属两个集合，且未匹配。
- P经过取反操作可以得到一个更大的匹配M’。
- M为G的最大匹配当且仅当不存在相对于M的增广路径。
匈牙利算法
- 置M为空
- 找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
- 重复2操作直到找不出增广路径为止
找增广路径的算法
- 如果v未匹配，则已经找到一条增广路
- 如果v已经匹配，则取出v的匹配顶点w(w一定是X部顶点)，边(w,v)目前是匹配的，根据“取反”的想法，要将(w,v)改为未匹配，(u,v)设为匹配，能实现这一点的条件是看从w为起点能否新找到一条增广路径P’。如果行，则u-v-P’就是一条以u为起点的增广路径。
匈牙利算法
//伪代码 bool dfs(int u)//寻找从u出发的增广路径 { for each v∈u的邻接点 if(v未访问){ 标记v已访问; if(v未匹配||dfs(cy[v])){ cx[u]=v; cy[v]=u; return true;//有从u出发的增广路径 } } return false;//无法找到从u出发的增广路径 } //代码 bool dfs(int u){ for(int v=1;v<=m;v++) if(t[u][v]&&!vis[v]){ vis[v]=1; if(cy[v]==-1||dfs(cy[v])){ cx[u]=v;cy[v]=u; return 1; } } return 0; } void maxmatch()//匈牙利算法主函数 { int ans=0; memset(cx,0xff,sizeof cx); memset(cy,0xff,sizeof cy); for(int i=0;i<=nx;i++) if(cx[i]==-1)//如果i未匹配 { memset(visit,false,sizeof(visit)) ; ans += dfs(i); } return ans ; } 算法分析
时空分析
- 时间复杂度：
- 找一次增广路径的时间为：
- 邻接矩阵： O(n^2)
- 邻接表：O(n+m)
- 总时间：
- 邻接矩阵：O(n^3)
- 邻接表：O(nm)
- 找一次增广路径的时间为：
- 空间复杂度：
- 邻接矩阵：O(n^2)
- 邻接表： O(m+n)
KM算法详解
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/213305.html原文链接：https://javaforall.net
