Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 算法 » 

匈牙利算法

匈牙利算法是解决二分图最大匹配的经典算法,由匈牙利数学家Edmonds提出,核心是通过寻找增广路径以求得最大匹配。
本文将介绍匈牙利算法的思想及原理解释,最后提供一个C++代码实现。

算法原理

无向图G=(V, E)中,如果顶点V可以分成不相交的子集(X, Y),使得图中每一条边所关联的两个顶点分别属于两个不同的顶点集,称G为一个二分图(二部图或偶图)。

给定二分图G,如果G的一个子图中M,M中任意两条边都不依附于同一个顶点(不相邻),则称M为一个匹配。
所有匹配中边数最大的称为最大匹配。
如果原图的所有顶点都和M中的某条边关联,称M为完备匹配,也称完美、完全匹配。

Note:
图G=(V,E)的子图是指图G1=(V1,E1),其中V1⊆V,E1⊆E。
图G=(V,E)的生成子图是指图G2=(V2,E2),其中V2=V,E2⊆E。
生成子图的顶点一定跟原图一样,而子图可以不一样。

给定一个二分图G,怎么求其最大匹配?这就是匈牙利算法解决的问题。
从一个未匹配顶点出发,交替经过非匹配边和匹配边的路径,称为交错路。
起点和终点都是未匹配顶点的交错路称为增广路。

pic

左边红色为原匹配,中间蓝色和红色组成增广路,右边蓝色为增广后的匹配。注意到,增广路中非匹配边比匹配边多一条,匈牙利算法正是基于此从一个初始匹配不断寻找增广路改进匹配,最终得到最大匹配。

匈牙利算法的正确性由以下定理保证。
Berge定理 图G的匹配M是最大匹配的充要条件是G中不存在M的增广路。
证明思路,
如果M中存在增广路L,把L中的边与M中的边作对称差后得到的边集是比M更大的匹配。
如果M中不存在增广路,假设M不是最大匹配,M’才是最大匹配,则|M’|>|M|,把M’和M中的边作对称差后得到的边集是M的增广路,矛盾。
Note:对称差的定义为 A⊕B = A ∪ B – A ∩ B。

Hall定理:二分图G=(X,Y),G有饱和X每个顶点的匹配当且仅当对任意S⊆X,有|N(S)|>=|S|,N(S)为S的所有相邻顶点集合。
推论一:二分图G=(X,Y),若X中每个顶点至少关联k条边(k>=1),Y中每个顶点至多关联k条边,则G存在饱和X的匹配。
推论二:二分图G=(X,Y)有完美匹配的充要条件是|X|=|Y|,且对任意S⊆X,|N(S)| >= |S|。

匈牙利算法求最大匹配
从一个初始匹配M出发(一般为空匹配),不断寻找增广路径P,将已有匹配M和增广路径P的边作异或操作得到更大的匹配M’并更新M,直到找不到增广路径。

代码实现

C++邻接表算法实现

const int mx = 205;			//二分图两边最大的顶点数
bool map[mx][mx], vs[mx];	//二分图,找增广轨时右边的顶点是否访问过
int match[mx], n;			//匹配中右边的点所对应的点,二分图的顶点个数

//寻找以左边点x为起点的增广轨
bool find (int x)
{
	for (int i = 0; i < n; i++)
		if (map[x][i] && !vs[i])
		{
			vs[i]  = 1;
			//尚未匹配 || 已经匹配但从其出发仍然可以找到增广轨
			if (match[i]==-1 || find(match[i]))	
			{
				match[i] = x;	return 1;
			}
		}
	return 0;
}

int findMatch ()
{
	int ret = 0;
	memset(match, -1, sizeof(match));
	for (int i = 0; i < n; i++)	 //寻找从每个点开始的增广路径
	{
		memset(vs, 0, sizeof(vs));
		ret += find(i);
	}
	return ret;		//返回最大匹配的边数,具体匹配在match中
}

上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论