匈牙利算法

您所在的位置：网站首页 › 二分算法例题 › 匈牙利算法

匈牙利算法

2024-07-12 00:59| 来源: 网络整理| 查看: 265

一、基本概念

1、匹配：在图论中，一个「匹配」是一个边的集合，其中任意两条边都没有公共顶点。

2、最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

3、完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

4、交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

5、增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。

6、匈牙利算法基于Hall定理中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。

二、基本模板

时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数

int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数 int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边 int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个 bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过 bool find(int x) { for (int i = h[x]; i != -1; i = ne[i])//遍历每个男生对应感兴趣的女生 { int j = e[i]; if (!st[j]) { st[j] = true;//暂时分配 if (match[j] == 0 || find(match[j]))//女生未被分配或者看已被分配的男生是和否还有其他选择 { match[j] = x;//确定分配 return true; } } } return false; } // 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点 int res = 0; for (int i = 1; i

【本文地址】

匈牙利算法

匈牙利算法

今日新闻

推荐新闻