web analytics

从零开始的匈牙利算法(二分图匹配)

前言: NOIP开考前几天。把不会的算法。赶紧学掉。感觉自己简直是不要命了。。。真是绝了。
所以会以自己认为的理解来讲述这个问题。
 讲之前我觉得得讲一下二分图的相关知识:
设G=(V,E)是一个无向图,顶点集V可分割为两个互不相交的子集V1,V2,那么称此图G为二分图。
例如,下图就是一个二分图:
1
二分图的匹配:
二分图中的子图中,每个节点只连一条边,则称该子图是二分图中的一个匹配。
极大匹配:
无法再向二分图中加入边,使得满足匹配条件。
最大匹配:
所有极大匹配中边数最多的一个匹配。
完美匹配:
如果一个图的某个匹配中,所有的顶点都是匹配点,那么它就是一个完美匹配。

正文部分

匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。
而匈牙利算法是解决二分图匹配时常用到的一种算法。当然如果够作,其实二分图匹配可以直接拿网络流写。当然。由于不会~所以这种算法还是有出路的。
时间复杂度 邻接表:O( nm )
这里介绍个名词。这也就是匈牙利算法的基础了。
增广路 : 如果在一个二分图上。存在一条路径。它上面的边是以一种 一条已经匹配过 一条没有匹配过 一条已经匹配过 一条没有匹配过 。这种交替的方式呈现出。那么我们就叫它为该图增广路。

而整个匈牙利的主体思想就是:
每次枚举左侧的点 (其实就是一部风),扩展增广路。如果找到一条增广路。就将整个匹配图,按照当前的增广路来改变。因为每次找到一条增广路,匹配数都会加1 。(这个地方可以很显然明白,因为增广路是以交替匹配与没匹配而呈现,这就会让那些匹配的重新改变匹配方式。而且还新增一个匹配方式。) 。当我们不能再找到增广路的时候,那么。。结,束,了。

具体的模拟,将在文章后链上一些参考。里面会有配图 模拟。(毕竟是考前写的。才不是不想配图了。)

这里给出基本模板:

参考:
有图有简单代码版。

有图有代码版。

Post a Comment

You must be logged in to post a comment.