寻找最大二分匹配的匈牙利算法

题目描述

给定一个二分图，其顶点集分为左部（L）和右部（R），以及连接左右两部顶点的边集（E）。匹配是一个边的子集，其中任意两条边都不共享公共顶点。最大二分匹配是指包含边数最多的匹配。你的任务是设计算法，在给定的二分图中找出一个最大匹配。

解题过程

我们将循序渐进地学习解决此问题的匈牙利算法（也称为Kuhn-Munkres算法在无权情况下的简化版，或增广路算法）。

核心思想：该算法采用迭代的方式，从左部顶点出发，尝试为每一个左部顶点在右部找到一个匹配对象。关键在于，当一个左部顶点无法直接找到未被匹配的右部顶点时，它会尝试“调整”现有的匹配，为新的顶点腾出位置，这个过程称为寻找“增广路径”。

步骤1：基本定义与准备工作

1. 输入表示：二分图通常用邻接表 adj[u] 表示，其中 u 是左部顶点（假设编号为0到nL-1），adj[u] 是u可以连接的右部顶点列表（右部顶点编号为0到nR-1）。
2. 关键数据结构：
   • matchR[r]：一个数组，记录当前与右部顶点 r 匹配的左部顶点编号。如果 r 未被匹配，则值设为-1。
   • vis[r]：一个布尔数组，在单轮匹配尝试中，标记右部顶点 r 是否被访问过，防止无限递归。

步骤2：算法的核心——dfs函数（寻找增广路）

这个深度优先搜索函数是整个算法的心脏。它的任务是：尝试为指定的左部顶点 u 找到一个匹配（或调整匹配以容纳它）。

函数定义： dfs(u)
输入： 左部顶点 u
输出： 布尔值，表示是否为 u 成功找到（或调整出）一个匹配

过程：
1.  对于 u 的每一个邻接顶点 r（在 adj[u] 中）：
    a. 如果 vis[r] 为真，跳过（这个右顶点在本轮尝试中已经被考虑过了）。
    b. 标记 vis[r] 为真。

    c. 检查右顶点 r 的当前状态：
       情况A：如果 matchR[r] == -1（即 r 未被匹配）。
           * 那么直接将 u 与 r 匹配。
           * 设置 matchR[r] = u。
           * 返回 true（成功找到匹配）。

       情况B：如果 matchR[r] != -1（即 r 已与某个左顶点 x 匹配）。
           * 我们尝试“请求”已匹配的左顶点 x（即 matchR[r]）**让出** r。
           * 递归调用 dfs(matchR[r])，看看 x 能否找到另一个右顶点来匹配。
           * 如果 dfs(matchR[r]) 返回 true（意味着 x 成功找到了新的匹配）：
               * 那么 r 就被“释放”出来了。
               * 将 u 与 r 匹配。
               * 设置 matchR[r] = u。
               * 返回 true。
           * 否则（dfs(matchR[r]) 返回 false）：
               * 意味着 x 无法找到替代的匹配，因此我们不能拆散 (x, r) 这对匹配。本轮尝试中，顶点 r 对 u 来说是不可用的。

2.  如果遍历完 u 的所有邻接顶点 r 后，都没有返回 true，说明无法为 u 找到或调整出匹配。
3.  返回 false。

重要理解：dfs 函数不仅是在找空位，更是在寻找一条从u到某个未匹配右顶点的交替路径。这条路径的边是未匹配-匹配-未匹配-...-未匹配交替出现的。找到后，将路径上所有边的匹配状态取反（未匹配变匹配，匹配变未匹配），匹配总数就增加了1。这个“取反”操作，正是通过上面递归调用中的“重新匹配”步骤巧妙完成的。

步骤3：主函数流程

有了核心的 dfs 函数，主算法就非常清晰了：

1.  初始化 matchR 数组，所有元素设为 -1。初始化最大匹配数 result = 0。
2.  对于每一个左部顶点 u (从 0 到 nL-1)：
    a. 在开始为 u 寻找匹配前，清空 vis 数组（标记本轮未访问任何右顶点）。
    b. 调用 dfs(u)。
    c. 如果 dfs(u) 返回 true，说明我们成功为 u 安排了一个匹配（无论是直接找到还是通过调整），那么最大匹配数 result 就加 1。
3.  循环结束后，matchR 数组就存储了一个最大匹配的结果，result 就是最大匹配的大小。

步骤4：复杂度与实例演示

• 时间复杂度：最坏情况下为 O(V * E)，其中 V 是左部顶点数，E 是总边数。因为每个左部顶点都要尝试一次dfs，而dfs可能会遍历所有边。
• 空间复杂度：O(V + E)，用于存储图、匹配数组和访问标记。

举例说明：
考虑一个简单的二分图：
左部: A(0), B(1)
右部: C(0), D(1)
边: A-C, A-D, B-C

1. 从A开始，dfs(A)：尝试邻接点C，C未匹配，匹配(A, C)。matchR[C]=A。
2. 处理B，dfs(B)：先清空vis。
   • 尝试邻接点C，C已匹配于A。标记vis[C]。
     • 递归调用dfs(A)，为A寻找新匹配。
     • dfs(A)中，尝试邻接点C（但vis[C]已标记，跳过）。尝试邻接点D，D未匹配，于是匹配(A, D)。matchR[D]=A，返回true。
   • 递归dfs(A)成功，意味着C被释放。于是匹配(B, C)。matchR[C]=B，返回true。
3. 最终匹配：(A, D), (B, C)。最大匹配数为2。

总结：匈牙利算法通过为每个左部顶点系统地寻找增广路径，逐步扩大匹配，最终在无法找到更多增广路径时，就得到了最大匹配。其核心操作dfs完美地实现了寻找和“翻转”增广路径的过程，思想经典而巧妙。