算法简介:二分图最大匹配

算法简介

算法简介

二分图最大匹配

相关概念

• 二分图:如果一个图的所有顶点可以被分为X和Y两个集合,并且所有边的两个顶点恰好一个属于集合X,另一个属于集合Y,即每个集合内的顶点没有边相连,那么此图就是二分图.
• 无权二分图:没有权重
• 待权权二分图:有边权

相关算法

1. 无权二分图最大匹配----匈牙利算法

* 时间复杂度:

用邻接表存储:O(NM)

* 算法特点:

1. 首先从任意一个未被配对的点u开始,从点u的边中任意选一条边(假设这条边是u→ν)开始配对,如果此时点v还没有被配对,则配对成功.此时便找到了一条增广路(只不过这条增广路比较简单).
   如果此时点v已经被配对了,那就要尝试进行"连锁反应".如果尝试成功了,则找到一条增广路,此时需要更新原来的配对关系.这里要用一个数组match来记录配对关系,比如点v与点配对了,就记作match[v]=u和match[u]=v配对成功后,记得要将配对数加1.
   配对的过程我们可以通过深度优先搜索来实现,当然广度优先搜索也可以.
2. 如果刚才所选的边配对失败,要从点u的边中再重新选一条边,进行尝试.直到点u配对成功,或者尝试过点u所有的边为止.
3. 接下来继续对剩下没有被配对的点一一进行配对,直到所有的点都尝试完毕,找不到新的增广路为止,输出配对数.

* 代码示例

无权二分图最大匹配–匈牙利算法

2. 带权二分图最佳完美匹配—KM算法

这里强烈建议参考这位大神的博文:KM算法,
上面博文详细画图推演了算法流程.本文在上面基础上将图邻接矩阵存储法改为邻接表存储法,进一步降低了时间复杂度

* 时间复杂度:

1. 邻接矩阵存储:O(N^3),N为点的总数
2. 邻接表存储:O(M*N^2),M为边数,N为点的总数

* 算法特点

1. 首先将X中每个成员的期望初始化为它所有边权的最大值,Y的期望为0,假设X集合选择x1,Y集合选择y1,期望记录为exx[x1],exy[y1].
2. 为X中每个成员(此时为x1)尝试匹配,注意X和Y集合中的每个成员本轮只能匹配一次.
   若匹配成功,则进行X集合下一个成员尝试,若匹配失败,则需要调整期望,直到本次匹配成功为止.
3. 本轮匹配规则(x1匹配)为:gap = exx[x1] + exy[y1] - w(x1-y1),w表示x1到y1的边权.
   若gap==0,表示满足期望要求,记录匹配结果:match[y1] = x1;
   反之,则不满足要求,则需要计算slack,规则:在本轮中y1的所有值选择最小值.即:slack[y1]=std::min(slack[y1],gap),本轮尝试失败,执行4.
4. 计算slack中最小值规则:任意一个参与匹配的X中成员能换到任意一个这轮没有被选择过的Y中成员所需要降低的最小值.
   即:在所有slack[y1],slack[y2]…中选择最小的slack,这里记为d,
   为本轮参与的X集合对象降低期望:exx[x1]-=d,为本轮被选择的Y集合对象增加期望:exy[y1]+=d,没有被选择的Y集合对象更新slack[y2]-=d.然后再次匹配尝试,直到本次成功为止.

* 代码示例

带权二分图最佳完美匹配—KM算法

最后

以上就是高兴小丸子为你收集整理的算法简介:二分图最大匹配的全部内容，希望文章能够帮你解决算法简介:二分图最大匹配所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。