Hopcroft-Karp 算法用于最大匹配

引言

在二分图中，我们可以说匹配是边的集合，其选择方式是任何一个端点不共享多于一条边。我们也可以说最大边数的匹配称为最大匹配。如果我们在最大匹配中添加任何其他边，则它不再是匹配。在二分图中，可能存在多个最大匹配。

让我们讨论一些与该算法相关的术语

1. 自由节点或顶点

在匹配 M 中，存在一个不属于匹配的节点。我们可以将此节点称为自由节点。在下面的图中，u2 和 v2 是自由节点。在第三个图中，没有顶点是自由的。

2. 匹配边和非匹配边

在匹配 M 中，属于匹配的边，我们称之为匹配边。不属于匹配的边可以称为非匹配边。在下面的图中，第一个图包含所有非匹配边；在第二个图中，(u0, v1)、(u1, v0) 和 (u3, v3) 是匹配边，其他是非匹配边。

3. 交替路径

在给定的匹配 M 中，当一条路径连接了匹配边和非匹配边时，我们可以称之为交替路径。我们也可以说所有单边路径都是交替路径。在下面的图中，u0-v1-u2 和 u2-v1-u0-v2 被称为交替路径。

4. 增广路径

在给定的匹配 M 中，当一条交替路径从自由节点开始并结束于自由节点时，我们可以称之为增广路径。我们也可以说所有从自由顶点开始和结束的单边路径都是增广路径。

我们必须注意一点：增广路径总是多一条匹配边。在 Hopcroft-Karp 算法中，如果存在增广路径，则匹配 M 不是最大匹配。

Hopcroft-Karp 算法

该算法基于以下步骤。

1. 首先，我们必须将最大匹配 M 初始化为空。
2. 如果存在增广路径 P，那么我们必须移除 P 的所有匹配边，然后将 P 的所有非匹配边添加到 M 中。
3. 然后我们必须返回 M。

在下面的图中，我们已经实现了上述内容。

Hopcroft-Karp 算法的实现

在实现此算法之前，我们必须注意以下几点。

• 首先，我们必须找到增广路径。
• 找到增广路径后，我们需要将增广路径添加到现有匹配中。这里，添加路径意味着我们必须使此路径上的先前匹配边变为非匹配边，并使先前非匹配边变为匹配边。

广度优先搜索背后的主要思想是找到增广路径。由于 BFS 只能逐层遍历，因此它可以将图分成匹配边和非匹配边的层。然后，我们必须添加一个虚拟顶点 NIL，它用于连接左侧的所有顶点和右侧的所有顶点。借助下面的一些数组，我们可以找到增广路径。我们必须将到 NIL 的距离初始化为无限。如果我们从一个虚拟顶点开始，并使用不同顶点的交替路径返回到它，那么肯定存在增广路径。

所需的数组如下

• pairU[]

此数组的大小为 m+1。这里，m 是二分图左侧顶点的数量。借助此数组，我们可以存储 u 在右侧的对（如果 u 已匹配），如果未匹配，则为 NIL。

• pairV[]

此数组的大小为 n+1。这里，n 表示二分图右侧顶点的数量。借助此数组，我们可以存储 v 在左侧的对（如果 v 已匹配），否则为 NIL。

• dist[]

此数组的大小为 m+1。这里，m 表示二分图左侧顶点的数量。如果 u 不匹配且 INF（无限），那么我们必须将 dist[] 初始化为 0。此外，我们必须将 NIL 的 dist[] 初始化为 INF。

找到增广路径后，我们必须借助 DFS（深度优先搜索）将增广路径添加到当前匹配中。

让我们借助以下程序来理解该算法的实现。

C++ 14 中的实现

代码

输出

说明

在上面的代码中，我们使用 C++ 实现了 Hopcroft-Karp 算法来查找最大匹配。

时间复杂度

这里，该算法的时间复杂度为 O(V x E)，其中 E 是边的数量，V 是顶点的数量。

空间复杂度

这里，该算法的空间复杂度为 O(V)。