二分图匹配--匈牙利算法

59 阅读 0 评论 39 点赞

我是靠谱客的博主背后向日葵，最近开发中收集的这篇文章主要介绍二分图匹配--匈牙利算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

文章目录

- 二分图：
- 匹配
- 匈牙利算法
- 代码：

二分图：

二分图是一个无向图，点集分成子集X和Y，图中每一条边都是一边在X一边在Y
当且仅当无向图G的每一个回路次数都是偶数时（包括0），G就是一个二分图
在这里插入图片描述

匹配

介绍完二分图后我们看看匹配
匹配：如果任意两个边的端点都不相同，我们就称之为匹配。匹配是边的集合
最大匹配：所含匹配边数最多的匹配
完美匹配：在一次匹配中，所有的顶点都是匹配点
完美匹配一定是最大匹配，但是反过来不一定

匈牙利算法

以上讲的均为离散知识，现在开始讲算法
交替路：从一个未匹配点开始，按照非匹配边，匹配边，非匹配边。。。。这样的顺序形成的路径
增广路：从一个未匹配点开始，走交替路，如果途中经过另一个未匹配点，则这条交替路叫做增广路
增广路特点：非匹配边比匹配边多一条
算法核心就是寻找增广路径，直到没有
匈牙利算法寻找最大匹配，就是通过不断寻找原有匹配M的增广路径，因为找到一条M匹配的增广路径，就意味着一个更大的匹配M ’ ，其恰好比M多一条边。这样不断更新，找不到就是最大情况
过程：
一开始随便选一个未匹配点，先是匹配（x1,y1），标记，然后给x2匹配，匹配（x2，y2），这样就形成匹配M，有两条边，目前没问题
然后x3匹配，发现y1已经被x1抢占了，然后x3横刀夺爱抢走y1，x1悲恨交加只能找下一个，然后把x2的对象y2也抢了，x2也只能顺位找y5，（这是个递归的过程，直到匹配到未被抢占的）,这就形成匹配M1
刚才的争执过程（x3,y1,x1,y2,x2,y5）,这就是匹配M的增广路
发现增广路就说明有更优的情况，所以我们由匹配M扩展到现在的M1
然后将x4加入，一次类推
如果争执过程中，最后一个人没找到对象怎么办？那这整个抢夺过程就算是失效的
在这里插入图片描述

代码：

我珍藏多年的模板

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 3;
int n = maxn, m = maxn;
int Map[maxn][maxn];//map[i][j]=1表示X部的i和Y部的j存在路径,是否可以匹配
int cx[maxn], cy[maxn];
bool vis[maxn];
//cx[i]表示X部i点匹配的Y部顶点的编号
//cy[i]表示Y部i点匹配的X部顶点的编号
 
bool dfs(int u)//dfs进入的都是X部的点
{
	for (int v = 0; v < n; v++)//枚举Y部的点，判断X部的u和Y部的v是否存在路径
	{
		//如果存在路径并且还没被标记加入增广路
		if (Map[u][v] && !vis[v])//vis数组只标记Y组
		{
			//标记加入增广路
			vis[v] = 1;
 
			//如果Y部的点v还未被匹配
			//或者已经被匹配了，但是可以从v点原来匹配的cy[v]找到一条增广路
			//说明这条路就可是一个正确的匹配
			//因为递归第一次进入dfs时，u是未匹配的
			//如果v还没有匹配对象，即和它相连的所有边都不在，已经选择的匹配边集合M（Min E）中，这时就找到了u-v增广路径
			//如果v已经有匹配对象了，那么u-v是一条未选择的边，
			//而v-cy[v] in M 则是一条已经选择的边, dfs(cy[v])从cy[v]开始搜索增广路径
				//如果新的v'没有匹配对象，那么u-v-cy[v]-v'就是一条增广路径，
				//如果v'已经有匹配对象了，那么根据匹配是唯一的，
				//cy[v]-v'一定不在已经选择的边中(和cy[v]-v冲突)，
				//u-v-cy[v]-v'-cy[v']符合增广路径对边顺序的要求，继续利用dfs(cy[v'])搜索u-v-cy[v]-v'-cy[v']-下面的点
				//当搜索到增广链时，如u-v-cy[v]-v',那么经过递归的匹配调整和return 1，进行匹配增广操作，假设dfs0 是main调用的dfs算法，dfs1是dfs0调用的dfs算法
				//在dfs1中进行cy[v]-v'的匹配，因为dfs1返回1，因此在dfs0中进行u-v的匹配，匹配增广操作的结果是{cy[v]-v}->{u-v,cy[v]-v'}
				//如果在一个dfs(k)自调用的dfs(k+1)中，遍历所有的v(k+1),要么已经有匹配点了，要么和输入u(k+1)没有连接可能，这时搜索终止，说明不存在经过u(k+1)的增广链，返回0
				//而在main调用的dfs(0)中，调用的dfs(1)返回的都是0，而且v都是已经有匹配了，那么不存在从该点出发的增广链，那么就该点就不在最大匹配当中
				//为什么找不到增广链就不在最大匹配当中呢？感觉可以用反证法证明，博客中下面内容可能有更新这方面的思考
			if (cy[v] == -1 || dfs(cy[v]))
			{
				cx[u] = v;//可以匹配，进行匹配
				cy[v] = u;
				return 1;
			}
		}
	}
	return 0;//不能匹配
}
int maxmatch()//匈牙利算法主函数
{
	int ans = 0;
	//匹配清空，全部置为-1
	memset(cx, -1, sizeof(cx));
	memset(cy, -1, sizeof(cy));
	for (int i = 0; i < n; i++)
	{
		if (cx[i] == -1)//如果X部的i还未匹配
		{
			memset(vis, 0, sizeof(vis));//每次找增广路的时候清空vis
			ans += dfs(i);
		}
	}
	return ans;
}
 
int main()
{
	//输入匹配的两个点集合的数量
	cin >> n >> m;
	//输入两个点集合成员间的匹配可能
	int x, y;
	for (int i = 0; i < m; i++)
	{
		cin >> x >> y;
		Map[x][y] = 1;
	}
	//执行匈牙利算法，输出最大匹配
	cout << maxmatch() << endl;
	return 0; 
}