二分图最大匹配：深入理解匈牙利算法

引言

图论是计算机科学和离散数学中的一个核心分支，它研究由节点（顶点）和连接节点的边构成的“图”结构。在众多图论问题中，“匹配”问题是一个既基础又具有广泛应用价值的经典问题。特别地，“二分图的最大匹配”问题在现实世界中有着丰富的应用场景，例如任务分配、人员调度、在线广告推荐、社交网络分析等。解决这一问题的经典算法之一便是匈牙利算法（Hungarian Algorithm），它以其直观的思路和相对高效的实现而闻名。本文将深入探讨二分图、匹配相关的核心概念，并详细剖析匈牙利算法的原理、实现、复杂度及其应用。

一、核心概念解析

在深入匈牙利算法之前，我们必须首先理解几个关键概念。

1. 二分图 (Bipartite Graph)

一个图 G = (V, E) 如果其顶点集 V 可以被划分为两个 互不相交 的子集 X 和 Y（即 X ∩ Y = ∅ 且 X ∪ Y = V），并且图中的 每一条边 (u, v) ∈ E 的两个端点分别属于这两个不同的子集（即 u ∈ X, v ∈ Y 或 u ∈ Y, v ∈ X），那么这个图就被称为 二分图。X 和 Y 通常被称为二分图的左部和右部。

简单来说，二分图的特点是“内部无边”，即同一个子集内的顶点之间没有边直接相连。判断一个图是否为二分图的常用方法是染色法：尝试用两种颜色（如黑白）对图的顶点进行染色，要求每条边的两个端点颜色不同。如果能够成功染色，则该图是二分图；否则不是。

2. 匹配 (Matching)

在图 G = (V, E) 中，一个匹配 M 是边集 E 的一个子集（M ⊆ E），满足 M 中 任意两条边都没有公共顶点。换句话说，匹配中的每条边都是相互独立的，每个顶点最多只与匹配中的一条边相关联。

匹配边 (Matched Edge)：属于匹配 M 的边。
匹配点 (Matched Vertex)：与匹配中的某条边相关联的顶点。
未匹配点 (Unmatched Vertex / Free Vertex)：不与匹配中任何边相关联的顶点。
匹配数 (Size of Matching)：匹配 M 中边的数量，记作 |M|。

3. 最大匹配 (Maximum Cardinality Matching)

对于给定的图 G，其所有可能的匹配中，包含 边数最多 的那个匹配称为 最大匹配。最大匹配可能不唯一，但其包含的边数（即最大匹配数）是唯一的。

4. 完美匹配 (Perfect Matching)

如果在一个匹配 M 中，图 G 的 所有顶点 都是匹配点，那么这个匹配 M 就被称为 完美匹配。显然，完美匹配一定是最大匹配。但最大匹配不一定是完美匹配（例如，当图的顶点数为奇数时，或者在二分图中 |X| ≠ |Y| 时，就不可能存在完美匹配）。对于二分图 G = (X ∪ Y, E)，存在完美匹配的必要条件是 |X| = |Y|。

5. 交替路 (Alternating Path)

相对于一个给定的匹配 M，图 G 中的一条路径 P 如果其包含的边在 M 中和不在 M 中 交替出现，则称 P 为一条 交替路。

6. 增广路 (Augmenting Path)

一条 增广路 P 是指满足以下条件的 交替路：
* 路径的起点和终点都是 未匹配点。

增广路之所以重要，是因为它揭示了改进当前匹配的可能性。

7. Berge 定理 (Berge’s Theorem)

这是匹配理论中的一个基石性定理，它指出：
一个匹配 M 是图 G 的最大匹配，当且仅当 G 中不存在相对于 M 的增广路。

这个定理告诉我们：
* 如果能找到一条增广路，那么当前的匹配就不是最大匹配。
* 如果找不到任何增广路，那么当前的匹配就已经是最大匹配了。

如何通过增广路改进匹配？
假设找到了一条增广路 P。由于 P 的起点和终点都是未匹配点，且路径上的边在匹配 M 内外是交替出现的，那么 P 中的非匹配边一定比匹配边多一条。我们可以对这条增广路 P 进行 取反操作（Symmetric Difference）：将 P 上原属于 M 的边从 M 中移除，并将 P 上原不属于 M 的边加入到 M 中。记新的匹配为 M'，则 M' = M ⊕ E(P) = (M \ E(P)) ∪ (E(P) \ M)，其中 E(P) 是路径 P 的边集。
由于增广路 P 的非匹配边比匹配边多一条，这个取反操作会使得新匹配 M' 的边数比原匹配 M 的边数 恰好增加 1 (|M'| = |M| + 1)。

因此，寻找最大匹配的过程，本质上就是不断寻找增广路并进行取反操作，直到无法再找到任何增广路为止。匈牙利算法正是基于这一核心思想。

二、匈牙利算法原理

匈牙利算法是一种用于求解 二分图最大匹配 的经典算法。其核心思想就是不断地寻找增广路来扩大当前匹配的规模。通常，我们使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现增广路的查找。这里我们重点介绍基于 DFS 的实现方式。

算法流程 (基于 DFS):

初始化:
- 从一个空匹配 M = ∅ 开始。
- 初始化一个 match 数组（或类似数据结构），match[y] 存储右部顶点 y 当前匹配的左部顶点。如果 y 未匹配，则 match[y] 为一个特殊值（如 -1 或 nullptr）。
- 最大匹配数 count = 0。
迭代查找增广路:
- 遍历二分图左部 X 中的每一个顶点 u。
- 对于当前的 u，尝试为其寻找一条增广路：
  - 启动 DFS: 从 u 出发，进行一次深度优先搜索。在每次 DFS 搜索开始前，需要清空用于标记访问状态的 visited 数组（这个数组的作用是防止在单次 DFS 过程中形成环路，确保路径的有效性）。
  - DFS 过程 (函数 dfs(u)):
    - 遍历 u 的所有邻居 v（v 属于右部 Y）。
    - 如果 v 在 本次 DFS 中尚未被访问 (visited[v] == false):
      - 标记 v 为已访问 (visited[v] = true)。
      - 检查 v 的状态:
        
        Case 1: v 是未匹配点 (match[v] == -1)。
        
        这表明我们找到了一条从 u 开始，到 v 结束的增广路（长度可能为 1，如果 u 本身也未匹配）。
        
        更新匹配: 设置 match[v] = u。
        
        返回成功: dfs(u) 返回 true，表示找到了增广路。
        
        Case 2: v 已经被匹配 (match[v] = u')，其中 u' 是 v 当前匹配的左部顶点。
        
        这意味着 (u', v) 是一条匹配边。为了寻找从 u 出发的增广路，我们需要尝试让 u' 去匹配其他的右部顶点，从而“腾出” v 给 u。
        
        递归尝试: 递归调用 dfs(match[v])，即尝试为 u' 寻找一条新的增广路。
        
        如果 dfs(match[v]) 返回 true（表示成功为 u' 找到了新的匹配，从而 v 可以被释放）：
        
        更新匹配: 将 v 的匹配对象改为 u，即 match[v] = u。
        
        返回成功: dfs(u) 返回 true。
    - 如果遍历完 u 的所有邻居 v，都无法找到一条从 u 出发并最终以未匹配点结束的增广路径（无论是直接找到未匹配的 v，还是通过递归让已匹配的 v 的原配对 u' 找到新对象），则 dfs(u) 返回 false。
- 处理 DFS 结果: 如果 dfs(u) 返回 true，说明成功为 u 找到（或通过调整已有匹配）了一条增广路，使得匹配规模增加。将最大匹配数 count 加 1。
终止: 当遍历完左部 X 的所有顶点后，算法结束。此时的 count 即为二分图的最大匹配数，match 数组记录了最大匹配的具体方案。

理解关键点:

visited 数组的作用: visited 数组确保在一次从某个左部顶点 u 出发的 DFS 过程中，每个右部顶点 v 最多被访问一次。这防止了在寻找增广路时陷入死循环，并保证了找到的路径是简单路径（无重复顶点）。每次为新的左部顶点 u 启动 DFS 时，必须重置 visited 数组，因为上一次的访问记录与本次寻找增广路无关。
递归的含义: dfs(match[v]) 的递归调用，形象地描述了“NTR”过程：u 看上了 v，但 v 已经有配对 u' 了。于是 u 让 u' 去尝试找别人 (dfs(u'))，如果 u' 成功找到了新的配对，那么 v 就空出来了，可以和 u 配对。这个过程可能形成一条链式的“让位”操作，这正是增广路取反操作的体现。

三、匈牙利算法实现细节与复杂度

数据结构:

图的表示: 通常使用邻接表存储二分图，graph[u] 存储与左部顶点 u 相连的所有右部顶点列表。
匹配记录: match 数组，大小为右部顶点数量 |Y|。match[v] 存储与右部顶点 v 匹配的左部顶点的索引（或指针），未匹配则为 -1。
访问标记: visited 数组，大小为右部顶点数量 |Y|，布尔类型。在每次主循环调用 DFS 前清空。

伪代码 (DFS 实现):

“`pseudocode
function HungarianAlgorithm(graph, X_nodes, Y_nodes):
match = array of size |Y_nodes|, initialized to -1
count = 0

for each u in X_nodes:
visited = array of size |Y_nodes|, initialized to false
if dfs(u, graph, match, visited):
count = count + 1

return count, match

function dfs(u, graph, match, visited):
for each v in graph[u]: // v is a neighbor of u in Y
if not visited[v]:
visited[v] = true
// Case 1: v is unmatched OR
// Case 2: v’s current match (match[v]) can find a new match
if match[v] == -1 or dfs(match[v], graph, match, visited):
// Found an augmenting path ending at v
match[v] = u
return true // Indicate success

// No augmenting path found starting from u via unvisited neighbors
return false
“`

时间复杂度:

外层循环遍历左部 X 中的每个顶点，共 |X| 次。
每次调用 dfs(u)，在最坏情况下，DFS 可能会访问图中的所有顶点和边。一次 DFS 的时间复杂度约为 O(E)，其中 E 是图的边数。
因此，匈牙利算法（基于 DFS 实现）的总时间复杂度为 O(|X| * E)。如果使用邻接矩阵表示图，则复杂度为 O(|X| * |V|^2)，其中 V 是总顶点数 (|X| + |Y|)。在稀疏图中，邻接表 O(|X| * E) 通常优于邻接矩阵。

空间复杂度:

需要存储图（邻接表为 O(V+E)），match 数组 (O(|Y|))，visited 数组 (O(|Y|))，以及 DFS 的递归调用栈（最坏 O(V)）。
因此，空间复杂度主要由图的存储和辅助数组决定，通常为 O(V + E)。

优化：Hopcroft-Karp 算法

虽然匈牙利算法（特指基于单次 DFS/BFS 找一条增广路的方法）已经很实用，但存在一个更快的算法——Hopcroft-Karp 算法。该算法利用 BFS 同时寻找多条互相不相交的最短增广路，并在一次迭代中将它们全部用于增广。其时间复杂度可以达到 O(E * sqrt(V))，在理论上更优，尤其对于稠密图。但在实践中，对于规模不特别巨大的稀疏图，简单的匈牙利算法（DFS 实现）由于常数因子较小且易于实现，仍然非常常用。

四、匈牙利算法的应用实例

二分图最大匹配的应用非常广泛，以下是一些典型例子：

任务分配问题:
- 有一组工人 X 和一组任务 Y。
- 如果工人 i 能够完成任务 j，则在 i 和 j 之间连一条边。
- 目标是分配尽可能多的任务，使得每个工人最多做一个任务，每个任务最多被一个工人做。这就是一个标准的二分图最大匹配问题。
课程/时间表安排:
- 有一组课程 X 和一组时间段 Y。
- 如果课程 i 可以在时间段 j 开设（没有冲突），则连边。
- 目标是安排尽可能多的课程，使得每个时间段最多安排一门课，每门课最多被安排一次。
棋盘覆盖问题:
- 在一个（可能有洞的）棋盘上，能否用 1×2 的多米诺骨牌完全覆盖？
- 将棋盘黑白染色，构成二分图的两个顶点集 X (黑格) 和 Y (白格)。
- 相邻的格子之间连边。
- 问题转化为：该二分图是否存在完美匹配？如果最大匹配数等于格子总数的一半，则可以覆盖。
在线广告匹配:
- 有广告位 X 和广告商 Y。
- 如果广告商 j 的广告适合投放在广告位 i，则连边。
- 目标是在满足各种限制条件下（如预算、展示次数），最大化匹配的广告展示。虽然实际问题更复杂（可能是带权匹配或更复杂的约束），但二分图匹配是其基础模型。
稳定婚姻问题 (Gale-Shapley 算法相关):
- 虽然稳定婚姻问题有其特定算法，但其场景（男性集合 X 和女性集合 Y 之间的配对）与二分图匹配密切相关。
最小顶点覆盖 (Konig 定理):
- 在 二分图 中，最大匹配数等于最小顶点覆盖数。顶点覆盖是指一个顶点子集，使得图中每条边至少有一个端点在该子集中。最小顶点覆盖是寻找规模最小的这样的子集。匈牙利算法求出的最大匹配数直接给出了最小顶点覆盖的大小。

五、总结

二分图最大匹配问题是图论中的一个核心问题，而匈牙利算法提供了一种直观且有效的解决方案。该算法基于 Berge 定理，通过迭代地寻找并利用增广路来逐步增加匹配的大小，直至无法找到任何增广路，此时得到的匹配即为最大匹配。基于深度优先搜索（DFS）的实现方式简洁明了，易于理解和编码，时间复杂度为 O(|X| * E)。

深入理解匈牙利算法，不仅需要掌握二分图、匹配、交替路、增广路等基本概念，还需要清晰地把握 DFS 在寻找增广路过程中的递归逻辑和 visited 数组的关键作用。虽然存在理论上更快的 Hopcroft-Karp 算法，但匈牙利算法因其实现简单和在实践中的良好表现，仍然是学习和解决二分图匹配问题的基石。掌握它，能够为解决现实世界中大量的资源分配、调度和配对问题提供有力的工具。