用于二分图匹配的匈牙利算法

二分图匹配问题

二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。

给定一个二分图G,M为G边集的一个子集,如果M满足当中的任意两条边都不依附于同一个顶点,则称M是一个匹配。

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。(见下图)

二分图
最大二分匹配

如图蓝线所示是一种最大二分匹配方案,匹配数=3
警告:使用IE6浏览会极不正常,不信你把图片下载下来用看图工具看看。

如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。

求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

(以上除图片均来自百度百科)

匈牙利算法

先考虑一道题:USACO-4.2.2-stall4

求最大匹配的一种显而易见的算法是:先找出全部匹配,然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此,需要寻求一种更加高效的算法。

可以用网络流的最大流实现,不过最大流比较复杂,使用匈牙利算法编程复杂度低。

算法最基本轮廓:


红线代表Find函数的调用,蓝线代表已有的配对

查看或下载GIF版本
样例动画演示

  1. 置边集M为空(初始化,谁和谁都没连着)
  2. 选择一个新的原点寻找增广路
  3. 重复(2)操作直到找不出增广路径为止(2,3步骤构成一个循环)

模拟步骤如右图所示(过于详细,大牛请无视):

  1. 初始化(清空)
  2. 从A所连接的点中找到一个未在本次循环中搜索过的点2,并将2标记为搜索过,因为2没有被连接过,匹配A2
  3. 结束上次,开始新的循环,将所有点标记为未搜索过
  4. 搜索B,找到一个未在本次循环中搜索过的点2,标记为搜索过
  5. 发现2被匹配过,从2的父亲A寻找增广路,递归搜索A{从A所连接的点中找到一个未在本次循环中搜索过的点5(1已经标记为绿色),将5标记为搜索过,因为5没有被匹配过,匹配A5}找到增广路(此处为增广路的关键
  6. 结束上次,开始新的循环,将所有点标记为未搜索过
  7. 搜索C,找到一个未在本次循环中搜索过的点1,并将1标记为搜索过,发现1未被匹配过,匹配C1
  8. 结束上次,开始新的循环,将所有点标记为未搜索过
  9. 搜索D,找到一个未在本次循环中搜索过的点1,并将1标记为搜索过,发现1被匹配过,递归搜索1的源C寻找增广路
  10. {搜索C,找到一个未在本次循环中搜索过的点5,标记为搜索过,发现5被匹配,进一步返现没有其他可连接点,返回找不到增广路}返回第9步
  11. 搜索D,找到一个未在本次循环中搜索过的点2,发现2被匹配,递归搜索2的源B寻找增广路
  12. {搜索B,找到一个未在本次循环中搜索过的点3,并将3标记为搜索过,发现3未被匹配,匹配B3返回找到}既然B另寻新欢,匹配D2
  13. 结束上次,开始新的循环,将所有点标记为未搜索过,递归搜索D寻找增广路
  14. 搜索E,找到一个未在本次循环中搜索过的点2,并将2标记为搜索过,发现2被匹配过,递归搜索2的源D寻找增广路
  15. {搜索D,发现1,5均被匹配过,返回找不到增广路}
  16. E无其他可连接节点,放弃E,E后无后续节点,已经遍历A-E,结束算法

附本体题解CODE:

另外,最小点集覆盖问题其实相当于二分图最大匹配问题,证明见Matrix67 博客二分图最大匹配的König定理及其证明

例题:POJ3041

原创文章,转载请注明(最好把图片带走): 转载自Comzyh的博客

本文链接地址: 用于二分图匹配的匈牙利算法

6 Responses

  1. 楼主这个图(多结点图和GIF)是什么软件做的,用visio画线段树之类的图好麻烦,也试过一个用代码画图的(Graphviz)但是不好看

发表评论