第49课二分图匹配

学习目标

通过本课的学习，你将能够：

理解二分图匹配的定义与核心概念。
掌握匈牙利算法（Hungarian Algorithm）的基本原理与实现。
应用深度优先搜索（DFS）寻找增广路径。
计算一个二分图的最大匹配数。
区分最大匹配与完美匹配。

核心概念

什么是二分图匹配？

想象一下，在一个大学社团招新日，左边站着一群学生（集合U），右边摆着一排不同的社团（集合V）。每个学生只对其中几个社团感兴趣，我们用一条条线连接起来。二分图匹配要解决的核心问题是：在满足“每个学生最多加入一个社团，每个社团最多招一个新生”的前提下，最多能安排多少对学生成功配对？

这个场景抽象出来就是二分图：图中的顶点可以分成两个不相交的集合（U和V），所有的边都连接着U中的一个点和V中的一个点，集合内部没有边。

在这样一个图里，匹配（Matching）就是一组边的集合，其中任意两条边都没有公共顶点。换句话说，每个点最多只能被选中一次。

最大匹配：包含边数最多的匹配。 完美匹配：图中每个顶点都属于匹配中的某条边（即匹配数等于较小集合的大小）。

关键武器：增广路径与匈牙利算法

如何找到最大匹配？匈牙利算法提供了一个优雅的思路，它的核心是寻找增广路径。

想象你已经有了一个匹配（比如，已经安排了5对学生）。现在你想看看能不能多安排一对。增广路径是一条从未匹配的U中顶点出发，最终到达未匹配的V中顶点的路径。这条路径非常特别，它“边”的类型交替出现：

非匹配边（不在当前匹配中）。
匹配边（在当前匹配中）。
再非匹配边，再匹配边…… ……这样交替前进。

关键作用：找到一条增广路径，就相当于找到了一种“调整”当前匹配的方案，使得匹配数增加1。具体操作是：将路径上的所有边状态反转——原来匹配的边变成不匹配，原来不匹配的边变成匹配。因为路径的起点和终点都是未匹配点，反转后这两个点就会被纳入匹配，而中间的点只是“换了搭档”，匹配总数净增1。

匈牙利算法就是不断寻找增广路径，直到找不到为止。此时的匹配就是最大匹配。我们通常使用深度优先搜索（DFS）来寻找增广路径。

代码示例

以下代码实现了使用匈牙利算法求解二分图最大匹配。我们使用邻接矩阵 graph 存储二分图，其中 graph[i][j] 为1表示集合U的第i个点与集合V的第j个点有边。

def hungarian_algorithm(graph, u_size, v_size):
    """
    匈牙利算法求解二分图最大匹配
    :param graph: 二维列表，邻接矩阵。graph[i][j]=1表示U_i与V_j相连
    :param u_size: 集合U的大小
    :param v_size: 集合V的大小
    :return: 最大匹配数， 以及V中每个点的匹配对象（match_v数组）
    """
    # match_v[j] = i 表示集合V中的第j个点当前匹配了集合U中的第i个点
    # 初始化为-1，表示未匹配
    match_v = [-1] * v_size
    
    # 记录在本轮DFS中，V集合中的点是否已被访问过（防止重复搜索）
    visited = [False] * v_size

    # 尝试为U中的每个点u寻找匹配
    def dfs(u):
        # 遍历V中的所有点v
        for v in range(v_size):
            # 如果u和v有边，并且v在本轮DFS中未被访问过
            if graph[u][v] and not visited[v]:
                visited[v] = True # 标记为已访问
                # 如果v未匹配，或者v已匹配，但v的当前伴侣（match_v[v]）可以找到新的伴侣（递归寻找增广路径）
                if match_v[v] == -1 or dfs(match_v[v]):
                    match_v[v] = u # 将v匹配给u
                    return True # 找到增广路径，匹配成功
        # 尝试了所有v都无法为u找到匹配
        return False

    result = 0 # 最大匹配数
    # 遍历U中的每个点
    for u in range(u_size):
        # 每次DFS前，重置visited数组
        visited = [False] * v_size
        # 如果为当前点u找到了增广路径，则最大匹配数加1
        if dfs(u):
            result += 1
    
    return result, match_v

# 测试代码
if __name__ == "__main__":
    # 示例图：U有3个点，V有4个点
    # U0 连接 V0, V1
    # U1 连接 V0, V2
    # U2 连接 V1, V3
    graph = [
        [1, 1, 0, 0],  # U0
        [1, 0, 1, 0],  # U1
        [0, 1, 0, 1]   # U2
    ]
    u_size = 3
    v_size = 4

    max_match, match_info = hungarian_algorithm(graph, u_size, v_size)
    print(f"最大匹配数为: {max_match}")
    print("匹配关系（V中每个点的匹配对象）:")
    for j, i in enumerate(match_info):
        if i != -1:
            print(f"  V{j} <---> U{i}")
        else:
            print(f"  V{j} 未匹配")

输出结果：

最大匹配数为: 3
匹配关系（V中每个点的匹配对象）:
  V0 <---> U1
  V1 <---> U0
  V2 <---> U1
  V3 <---> U2

实践练习

练习1：判断匹配

给定一个包含4个U点和4个V点的二分图，边集为：(U0, V1), (U0, V2), (U1, V0), (U2, V1), (U3, V3)。请问集合 {(U0, V2), (U1, V0), (U2, V1), (U3, V3)} 是这个二分图的一个匹配吗？是完美匹配吗？为什么？

练习2：寻找增广路径

在练习1的图中，假设当前匹配为 {(U0, V2), (U1, V0)}。请指出一条从未匹配点U2出发的增广路径，并说明进行路径反转后，新的匹配是什么？

练习3：算法计算

根据以下二分图（U={U0, U1, U2}, V={V0, V1, V2}）的邻接矩阵，手动模拟或运行代码计算最大匹配数。

[[1, 0, 1],
 [0, 1, 1],
 [1, 1, 0]]

常见错误

混淆二分图与匹配：认为任意一个二分图都有匹配。实际上，匹配是边的子集，一个没有边的二分图，其最大匹配为0。
误解完美匹配：认为最大匹配一定是完美匹配。只有当匹配数等于min(|U|, |V|)时才是完美匹配。如果图结构不满足（例如一个点孤立无边），就无法达成完美匹配。
匈牙利算法实现错误：
- 未重置visited数组：在为每个U点调用DFS前，必须清空visited数组。否则，之前搜索中被访问过的V点可能被错误地跳过，导致找不到本应存在的增广路径。
- 递归逻辑错误：dfs函数中，当发现一个已匹配的V点时，正确逻辑是尝试为它的原匹配对象寻找新匹配（dfs(match_v[v])），而不是为自己找。初学者容易写成直接尝试匹配当前V点，这会导致错误。
- 邻接矩阵存储方向混淆：确保graph[i][j]的定义一致，通常表示U[i]到V[j]的边。

小结

本课我们学习了图论中一个经典而优美的问题——二分图匹配。

核心概念：将点分为两组的图叫二分图。匹配是边的互不相交子集。最大匹配是边数最多的匹配。
核心算法：匈牙利算法通过不断寻找增广路径来增加匹配数。增广路径是从一个未匹配U点出发，到未匹配V点结束的、匹配边与非匹配边交替出现的路径。
算法实现：使用深度优先搜索（DFS）为每个U点尝试寻找匹配。关键在于理解dfs(u)函数的递归逻辑：尝试所有相邻的V点，如果V点未匹配则成功匹配；如果已匹配，则递归地尝试为V点的原伴侣寻找新匹配。
时间复杂度：上述实现的时间复杂度约为 O(U * E)，其中U是集合U的大小，E是边的数量。

掌握二分图匹配是学习更复杂网络流算法（如最大流）的重要基础。理解了增广路径的思想，你就握住了解决许多匹配与分配类问题的钥匙。

练习编辑器

rust

第49课 二分图匹配