匈牙利算法

1 二分图

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

简单来说,如果图中所有顶点可以被分为两个集合,图中所有的边的头和尾不属于同一个顶点集合,而是跨越两个集合,则这个图是一个二分图。

例如:图1.1所示的图,无论如何划分顶点集合,也不能保证所有边的头和尾隶属于不同集合,因此,图1.1所示的图不是二分图。

图1.1

例如:图1.2所示的无向图:

图1.2

将顶点a,b,c,d作为集合A,将e,f,g,h作为集合B,将图1.2转化为图1.3所示:

图1.3

可以看出,图中顶点可以划分为A,B两个集合,而任意一条边的头和尾又分别隶属于集合A和集合B,因此,此图为二分图。

2 匹配

匹配:在图论中,一个匹配(matching)是指一个边的集合,其中任意两条边都没有公共顶点。 例如:图2.1中红色的边,可以为图1.3所示图的一个匹配。

图2.1

3 最大匹配

最大匹配:一个图所有匹配中,所含匹配边数最多的匹配,称为这个图的最大匹配。图 3.1是一个最大匹配,它包含4条匹配边。

图3.1

4 完美匹配

完美匹配:如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。完美匹配一定是最大匹配(完美匹配的任何一个点都已经匹配,添加一条新的匹配边一定会与已有的匹配边冲突),但并非每个图都存在完美匹配。

5 交替路径

交替路径:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边…形成的路径称为交替路径。

6 增广路径

增广路径:从一个未匹配点出发,走交替路,如果途径另一个未匹配点(出发的点不算),则这条交替路称为增广路(agumenting path)。

增广路径性质:     (1)P的路径长度必定为奇数,第一条边和最后一条边都不属于M,因为两个端点分属两个集合,且未匹配。     (2)P经过取反操作可以得到一个更大的匹配M’。     (3)M为G的最大匹配当且仅当不存在相对于M的增广路径。

7 匈牙利算法

匈牙利算法:利用增广路径求二分图的最大匹配算法称作匈牙利算法。(匈牙利数学家Edmonds于1965年提出)。 基本思想:通过寻找增广路径,把增广路径中的匹配边和非匹配边的相互交换,这样就会多出一条匹配边,直到找不到增广路径为止。

例如:以图2.1所示的二分图为例,使用匈牙利算法求解图的最大匹配。 (1)从顶点a出发,按照交替路径前进,第一个非匹配边为,到达顶点e,e为非匹配点,构成增广路径。令为匹配边,顶点a,e为匹配顶点。

(2)从顶点b出发,第一非匹配边为,到达顶点e,选择匹配边,到达a,选择非匹配边,g为非匹配点,找到一条增广路径。

(3)交换增广路径中的匹配边与非匹配边,得到如下匹配。

(4)从顶点c出发,第一非匹配边为,到达顶点e,然后按照交替路径前进,到达顶点b,无法继续前进。

(5)从顶点c出发,选择第二条非匹配边。

(6)从顶点d出发,选择非匹配边,到达顶点g,选择匹配边,到达顶点a,选择非匹配边到达顶点e,选择匹配边,到达顶部b,没有可以选择的边,且没有找到增广路径。

(7)继续从顶点d出发,选择非匹配边,找到增广路径,将边变为匹配边,算法结束。

8 结语

匈牙利算法多用于指派问题中,例如任务匹配问题。通过转化为二分图的形式,求解最大匹配,保证实现最优分配。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:进击的Helloworld

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-29

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动画:浅谈什么是 Sunday 算法

    Sunday 算法 是 Daniel M.Sunday 于 1990 年提出的字符串模式匹配。

    五分钟学算法
  • 资深技术 Leader 曹乐:如何成为技术大牛

    很多同学都有关于工程师该如何成长的问题,大家普遍对如何成长为牛人,如何获得晋升,如何在繁忙的工作中持续学习充满了困惑,这其实是每一位同学成长过程中必经之路。最近...

    五分钟学算法
  • 动画:什么是 BF 算法 ?

    Brute-Force算法,简称为 BF算法,是一种简单朴素的模式匹配算法,常用于在一个主串 S 内查找一个子串 T 的出现位置。

    五分钟学算法
  • 详细的正则表达式

    只能输入数字:"^[0-9]*$"。 只能输入n位的数字:"^\d{n}$"。 只能输入至少n位的数字:"^\d{n,}$"。 只能输入m~n位的数字:。"^\...

    Dawnzhang
  • 正则表达式学习笔记

    正则表达式学习笔记 (原创内容,转载请注明来源,谢谢) 首先,学习正则表达式,很推荐一篇博客,http://www.cnblogs.com/deerchao...

    用户1327360
  • python中正则表达式的学习

    我们以match_str=”abcdefghc“、pattern=”a.*c”例,

    菜鸟小白的学习分享
  • 正则表达式符号代表的意义

    无邪Z
  • 正则表达式简介

    正则表达式(Regular Expression)是一门通用的知识,我们的工作中随处可见,掌握了它,可以显著提升我们的工作效率。它的主要作用是根据一串规则串用来...

    未来sky
  • 还不会正则表达式?看这篇!

    正则表达式是很多程序员,甚至是一些有了多年经验的开发者薄弱的一项技能。大家都很多时候都会觉得正则表达式难记、难学、难用,但不可否认的是正则表达式是一项很重要的技...

    Nealyang
  • 正则表达式全部符号解释

    Text-to-speech function is limited to 200 characters

    botkenni

扫码关注云+社区

领取腾讯云代金券