最大二分匹配的 Hopcroft-Karp 算法
字数 2077 2025-11-04 11:59:17

最大二分匹配的 Hopcroft-Karp 算法

题目描述
给定一个二分图 \(G = (U \cup V, E)\)，其中 \(U\) 和 \(V\) 是两个不相交的顶点集合，\(E\) 是连接 \(U\) 和 \(V\) 的边集。目标是找到该二分图的最大匹配，即选择尽可能多的边，使得任意两条边没有公共顶点。Hopcroft-Kop 算法通过多阶段广度优先搜索（BFS）和深度优先搜索（DFS）来高效求解该问题，时间复杂度为 \(O(\sqrt{|V|} \cdot |E|)\)，优于传统的匈牙利算法。

解题步骤详解

1. 基本概念与初始化

  • 匹配 \(M\)：是边集 \(E\) 的子集，且 \(M\) 中任意两条边不共享顶点。若边 \((u, v) \in M\)，则称 \(u\) 和 \(v\) 是已匹配的。
  • 增广路径：从一个未匹配顶点出发，交替经过不在 \(M\) 中的边（未匹配边）和在 \(M\) 中的边（匹配边），最终到达另一个未匹配顶点的路径。增广路径的边数总是奇数，且首尾边均为未匹配边。
  • 关键性质：若存在增广路径，则可通过翻转路径上边的匹配状态（未匹配边变为匹配边，匹配边变为未匹配边）使匹配大小增加 1。
  • 初始化：匹配 \(M\) 为空集。

2. 算法框架
算法分为多个阶段，每个阶段包含以下步骤：

  1. 多源 BFS 构建层次图：从所有未匹配的 \(U\) 顶点出发，进行 BFS，标记顶点到起点的距离（层次），目的是找到最短的增广路径。
  2. 多路 DFS 寻找增广路径：基于层次图，从所有未匹配的 \(U\) 顶点并行进行 DFS，寻找并应用增广路径。
  3. 若找到至少一条增广路径，则更新匹配并进入下一阶段；否则算法终止。

3. 步骤 1：多源 BFS 构建层次图

  • 初始化队列，将所有未匹配的 \(U\) 顶点加入队列，层次标记为 0。
  • BFS 遍历规则：
    • 从 \(U\) 中的顶点 \(u\) 出发，沿未匹配边访问 \(V\) 中的邻居 \(v\)（需满足 \(v\) 未被访问），层次为 \(u\) 的层次 +1。
    • 从 \(V\) 中的顶点 \(v\) 出发，仅沿匹配边访问其匹配的 \(u\)（若存在），层次为 \(v\) 的层次 +1。
  • 目的：构建一个层次图，其中每条路径交替经过未匹配边和匹配边，且路径长度递增。

4. 步骤 2：多路 DFS 寻找增广路径

  • 从每个未匹配的 \(U\) 顶点出发，按照层次图的约束进行 DFS：
    • 从 \(u \in U\) 到 \(v \in V\) 时，只能走未匹配边，且 \(v\) 的层次必须比 \(u\) 大 1。
    • 从 \(v \in V\) 到 \(u \in U\) 时，只能走匹配边（即必须走回 \(v\) 的匹配顶点），且 \(u\) 的层次比 \(v\) 大 1。
  • 若 DFS 到达一个未匹配的 \(V\) 顶点，则找到一条增广路径。立即翻转路径上边的匹配状态，并标记该路径为已使用（本阶段不再重复使用这些顶点）。

5. 迭代与终止

  • 每个阶段结束后，匹配大小增加（找到的增广路径数量）。
  • 当某阶段未找到任何增广路径时，说明当前匹配已是最大匹配，算法终止。
  • 时间复杂度分析：由于最多有 \(O(\sqrt{|V|})\) 个阶段（由理论保证），每个阶段的 BFS 和 DFS 总时间为 \(O(|E|)\)，故总复杂度为 \(O(\sqrt{|V|} \cdot |E|)\)。

示例说明
考虑二分图：
\(U = \{u1, u2, u3\}, V = \{v1, v2, v3\}\)
边集 \(E = \{(u1,v1), (u1,v2), (u2,v2), (u2,v3), (u3,v1)\}\)

  1. 初始化：\(M = \emptyset\)。
  2. 第一阶段 BFS：从未匹配的 \(u1, u2, u3\) 出发，层次图包含所有边（因初始无匹配）。
  3. 第一阶段 DFS：从 \(u1\) 找到增广路径 \(u1 \to v1\)，匹配 \(M = \{(u1,v1)\}\)；从 \(u2\) 找到路径 \(u2 \to v2\)，匹配更新为 \(\{(u1,v1), (u2,v2)\}\)；从 \(u3\) 找到路径 \(u3 \to v1\) 但 \(v1\) 已匹配，回溯后尝试 \(u3 \to v1 \to u1 \to v2 \to u2 \to v3\)，最终翻转得到 \(M = \{(u1,v2), (u2,v3), (u3,v1)\}\)。
  4. 终止：无更多增广路径，最大匹配大小为 3。

通过分层搜索和并行增广，Hopcroft-Karp 算法高效地避免了重复计算，适用于大规模二分图。

最大二分匹配的 Hopcroft-Karp 算法 题目描述 给定一个二分图 \( G = (U \cup V, E) \)，其中 \( U \) 和 \( V \) 是两个不相交的顶点集合，\( E \) 是连接 \( U \) 和 \( V \) 的边集。目标是找到该二分图的 最大匹配 ，即选择尽可能多的边，使得任意两条边没有公共顶点。Hopcroft-Kop 算法通过多阶段广度优先搜索（BFS）和深度优先搜索（DFS）来高效求解该问题，时间复杂度为 \( O(\sqrt{|V|} \cdot |E|) \)，优于传统的匈牙利算法。 解题步骤详解 1. 基本概念与初始化 匹配 \( M \)：是边集 \( E \) 的子集，且 \( M \) 中任意两条边不共享顶点。若边 \( (u, v) \in M \)，则称 \( u \) 和 \( v \) 是 已匹配 的。 增广路径 ：从一个未匹配顶点出发，交替经过不在 \( M \) 中的边（未匹配边）和在 \( M \) 中的边（匹配边），最终到达另一个未匹配顶点的路径。增广路径的边数总是奇数，且首尾边均为未匹配边。 关键性质 ：若存在增广路径，则可通过翻转路径上边的匹配状态（未匹配边变为匹配边，匹配边变为未匹配边）使匹配大小增加 1。 初始化：匹配 \( M \) 为空集。 2. 算法框架 算法分为多个阶段，每个阶段包含以下步骤： 多源 BFS 构建层次图 ：从所有未匹配的 \( U \) 顶点出发，进行 BFS，标记顶点到起点的距离（层次），目的是找到最短的增广路径。 多路 DFS 寻找增广路径 ：基于层次图，从所有未匹配的 \( U \) 顶点并行进行 DFS，寻找并应用增广路径。 若找到至少一条增广路径，则更新匹配并进入下一阶段；否则算法终止。 3. 步骤 1：多源 BFS 构建层次图 初始化队列，将所有未匹配的 \( U \) 顶点加入队列，层次标记为 0。 BFS 遍历规则： 从 \( U \) 中的顶点 \( u \) 出发，沿未匹配边访问 \( V \) 中的邻居 \( v \)（需满足 \( v \) 未被访问），层次为 \( u \) 的层次 +1。 从 \( V \) 中的顶点 \( v \) 出发，仅沿匹配边访问其匹配的 \( u \)（若存在），层次为 \( v \) 的层次 +1。 目的：构建一个层次图，其中每条路径交替经过未匹配边和匹配边，且路径长度递增。 4. 步骤 2：多路 DFS 寻找增广路径 从每个未匹配的 \( U \) 顶点出发，按照层次图的约束进行 DFS： 从 \( u \in U \) 到 \( v \in V \) 时，只能走未匹配边，且 \( v \) 的层次必须比 \( u \) 大 1。 从 \( v \in V \) 到 \( u \in U \) 时，只能走匹配边（即必须走回 \( v \) 的匹配顶点），且 \( u \) 的层次比 \( v \) 大 1。 若 DFS 到达一个未匹配的 \( V \) 顶点，则找到一条增广路径。立即翻转路径上边的匹配状态，并标记该路径为已使用（本阶段不再重复使用这些顶点）。 5. 迭代与终止 每个阶段结束后，匹配大小增加（找到的增广路径数量）。 当某阶段未找到任何增广路径时，说明当前匹配已是最大匹配，算法终止。 时间复杂度分析 ：由于最多有 \( O(\sqrt{|V|}) \) 个阶段（由理论保证），每个阶段的 BFS 和 DFS 总时间为 \( O(|E|) \)，故总复杂度为 \( O(\sqrt{|V|} \cdot |E|) \)。 示例说明 考虑二分图： \( U = \{u1, u2, u3\}, V = \{v1, v2, v3\} \) 边集 \( E = \{(u1,v1), (u1,v2), (u2,v2), (u2,v3), (u3,v1)\} \) 初始化 ：\( M = \emptyset \)。 第一阶段 BFS ：从未匹配的 \( u1, u2, u3 \) 出发，层次图包含所有边（因初始无匹配）。 第一阶段 DFS ：从 \( u1 \) 找到增广路径 \( u1 \to v1 \)，匹配 \( M = \{(u1,v1)\} \)；从 \( u2 \) 找到路径 \( u2 \to v2 \)，匹配更新为 \( \{(u1,v1), (u2,v2)\} \)；从 \( u3 \) 找到路径 \( u3 \to v1 \) 但 \( v1 \) 已匹配，回溯后尝试 \( u3 \to v1 \to u1 \to v2 \to u2 \to v3 \)，最终翻转得到 \( M = \{(u1,v2), (u2,v3), (u3,v1)\} \)。 终止 ：无更多增广路径，最大匹配大小为 3。 通过分层搜索和并行增广，Hopcroft-Karp 算法高效地避免了重复计算，适用于大规模二分图。