二分图的最大匹配：匈牙利算法（Hungarian Algorithm）

一、问题描述

二分图（Bipartite Graph）是一种特殊的图，其顶点集合可以分为两个互不相交的子集 \(U\) 和 \(V\)，并且图中的每条边都连接一个 \(U\) 中的顶点和一个 \(V\) 中的顶点。
匹配（Matching）是二分图中一组边的集合，其中任意两条边都不共享同一个顶点。
最大匹配（Maximum Matching）是包含边数最多的匹配。
匈牙利算法是一种用于在二分图中寻找最大匹配的经典算法，其时间复杂度为 \(O(VE)\)，其中 \(V\) 是顶点数，\(E\) 是边数。

二、基本概念

1. 匹配边与非匹配边
   在匹配 \(M\) 中的边称为匹配边，否则为非匹配边。
2. 交替路径（Alternating Path）
   一条路径中，边在匹配边和非匹配边之间交替出现。
3. 增广路径（Augmenting Path）
   一条起点和终点都是未匹配顶点的交替路径。
   关键性质：如果将增广路径上的匹配状态取反（匹配边变非匹配，非匹配边变匹配），则匹配的边数增加 1。

三、匈牙利算法核心思想

核心：不断寻找增广路径，然后通过“取反”操作扩大匹配，直到找不到增广路径为止。此时得到的匹配就是最大匹配。

四、算法步骤（从空匹配开始）

假设二分图的两个顶点集为 \(U\)（左侧）和 \(V\)（右侧）。

步骤 1：初始化

• 设置匹配 \(M\) 为空集。

步骤 2：为每个 \(u \in U\) 尝试寻找增广路径

• 对每个左侧顶点 \(u\)：
  1. 使用深度优先搜索（DFS）或广度优先搜索（BFS）寻找从 \(u\) 开始的增广路径。
  2. 如果找到增广路径，则进行“取反”操作，将 \(u\) 加入匹配。
  3. 如果找不到，则 \(u\) 无法匹配（但仍保留之前的匹配）。

步骤 3：搜索增广路径的细节

• 维护一个数组 match[v] 记录右侧顶点 \(v\) 当前匹配的左侧顶点（若无匹配则为 -1）。
• 在搜索过程中，维护一个 visited 数组标记右侧顶点是否已在本次搜索中被访问。
• DFS 过程（从左侧顶点 u 开始）：
  1. 遍历所有与 u 相邻的右侧顶点 v。
  2. 如果 v 未被访问过：
     • 标记 v 为已访问。
     • 如果 v 未匹配（match[v] == -1），或者从 match[v]（即当前与 v 匹配的左侧顶点）出发能找到增广路径（递归调用），则：
       • 将 u 与 v 匹配（设置 match[v] = u）。
       • 返回 true（找到增广路径）。
  3. 如果所有相邻顶点都无法找到增广路径，返回 false。

五、举例说明

考虑二分图：

• \(U = \{A, B, C\}\)，\(V = \{D, E, F\}\)。
• 边：A-D, A-E, B-E, B-F, C-E。

第 1 轮：为 A 找匹配

• 从 A 开始，尝试匹配 D（D 未匹配）。
  匹配结果：A-D。
  match[D] = A。

第 2 轮：为 B 找匹配

• 从 B 开始，尝试匹配 E（E 未匹配）。
  匹配结果：B-E。
  match[E] = B。

第 3 轮：为 C 找匹配

• 从 C 开始：
  • 尝试匹配 E（E 已匹配 B）。
  • 从 E 的当前匹配顶点 B 出发，尝试重新为 B 找匹配（递归）：
    • B 的其他邻接点 F 未匹配，因此 B 可改为匹配 F。
  • 递归成功后，C 可以匹配 E。
• 路径：C（未匹配）→ E（匹配 B）→ B（改为匹配 F）→ F（未匹配）。
  取反后：C-E 变为匹配边，B-F 变为匹配边，B-E 变为非匹配边。
• 最终匹配：A-D, B-F, C-E。
  匹配数 = 3，达到最大匹配。

六、代码框架（DFS 实现）

def hungarian(graph, n_left, n_right):
    match = [-1] * n_right  # 右侧顶点匹配的左侧顶点
    result = 0
    
    def dfs(u, visited):
        for v in graph[u]:  # 遍历 u 的所有邻接点 v
            if not visited[v]:
                visited[v] = True
                # 如果 v 未匹配，或能为 v 的当前匹配找到新匹配
                if match[v] == -1 or dfs(match[v], visited):
                    match[v] = u
                    return True
        return False
    
    for u in range(n_left):
        visited = [False] * n_right
        if dfs(u, visited):
            result += 1
    return result

七、时间复杂度与优化

• 基本实现：每个左侧顶点执行一次 DFS，每次 DFS 最坏遍历所有边 \(E\)，总复杂度 \(O(VE)\)。
• 优化：使用 BFS 实现多路增广（Hopcroft–Karp 算法），可将复杂度降至 \(O(\sqrt{V}E)\)。

八、应用场景

1. 任务分配：将工人分配给任务，每人只适合部分任务。
2. 婚姻匹配：稳定婚姻问题的变体。
3. 网络流：二分图最大匹配可转化为最大流问题（添加源点和汇点）。
4. 资源调度：如服务器与虚拟机匹配。

九、总结

匈牙利算法的精髓在于通过增广路径逐步扩展匹配。其核心操作是 DFS 搜索与回溯，通过“临时拆开已匹配边”为当前顶点腾出位置。算法简洁高效，是二分图匹配问题的经典解法。