Part 4.7：二分图匹配——月老的红线与匈牙利算法

引言：月老的难题

想象一下，月老手上有两份名单，一份是男生，一份是女生。名单之间有一些连线，表示某位男生和某位女生互相有好感。月老的目标是尽可能多地撮合情侣，但规则是每个人只能有一位伴侣。

这个问题就是经典的二分图最大匹配 (Maximum Bipartite Matching) 问题。它旨在为两组独立的资源找到尽可能多的配对。

核心概念

什么是二分图？

二分图 (Bipartite Graph) 是一种特殊的图，它的所有顶点可以被分成两个互不相交的集合 U 和 V，使得图中的每一条边都连接着一个 U 中的顶点和一个 V 中的顶点。换句话说，同一个集合内部的顶点之间没有边。

判定方法：一个图是二分图，当且仅当它不包含奇数长度的环。我们可以用 BFS 或 DFS 进行染色来判断一个图是否是二分图。

什么是匹配？

  • **匹配 (Matching)**：图的一个边集，其中任意两条边都没有公共顶点。
  • **最大匹配 (Maximum Matching)**：在一个图中，包含边数最多的匹配。
  • **完美匹配 (Perfect Matching)**：如果一个匹配覆盖了图中的所有顶点，那么它就是一个完美匹配。显然，完美匹配一定是最大匹配。

匈牙利算法：寻找增广路的艺术

求解二分图最大匹配最经典的算法是**匈牙利算法 (Hungarian Algorithm)。它基于一个非常重要的概念——增广路 (Augmenting Path)**。

增广路

一条增广路是指在图中满足以下条件的一条路径：

  1. 它是一条简单路径（不重复经过顶点）。
  2. 它的起点和终点都是未匹配的顶点。
  3. 路径上的边是非匹配边和匹配边交替出现的。

**关键洞察 (Berge’s Lemma)**：一个匹配是最大匹配，当且仅当图中不存在增广路。

这个定理告诉我们，如果我们能找到一条增广路，我们就可以通过翻转这条路径上边的匹配状态（非匹配边变匹配，匹配边变非匹配），使得匹配边的数量加一。匈牙利算法的核心就是不断地寻找增广路，直到再也找不到为止。

算法步骤

匈牙利算法的实现通常使用 DFS 来寻找增广路。

  1. 初始化一个 match 数组，match[v] 存储与 V 集合中顶点 v 匹配的 U 集合中的顶点。
  2. 遍历 U 集合中的每一个顶点 u：
    a. 为 u 寻找增广路。我们使用一个 visited 数组来标记在单次 DFS 搜索中 V 集合中的顶点是否被访问过。
    b. 调用 dfs(u, visited, match)。
  3. 在 dfs(u, visited, match) 函数中：
    a. 遍历 u 的所有邻居 v（v 在 V 集合中）。
    b. 如果 v 在本次 DFS 中未被访问：
    i. 标记 v 为已访问。
    ii. 如果 v 是一个未匹配点，或者我们可以为 v 当前的匹配点 match[v] 找到一条新的增广路（递归调用 dfs(match[v], ...)），那么我们就找到了一条从 u 开始的增广路。
    iii. 更新匹配：match[v] = u，并返回 True。
    c. 如果遍历完所有邻居都无法找到增广路，返回 False。
  4. 统计 match 数组中有效的匹配数量，即为最大匹配数。

Python 实现

from collections import defaultdict

def hungarian_dfs(u, graph, match, visited):
    """为顶点 u 寻找增广路"""
    for v in graph[u]:
        if not visited[v]:
            visited[v] = True
            # 如果 v 未被匹配，或者 v 的匹配对象可以找到新的匹配
            if v not in match or hungarian_dfs(match[v], graph, match, visited):
                match[v] = u
                return True
    return False

def maximum_bipartite_matching(graph, u_nodes, v_nodes):
    """
    匈牙利算法求解二分图最大匹配
    graph: 邻接表，只包含从 U 到 V 的边
    u_nodes: U 集合的节点列表
    v_nodes: V 集合的节点列表
    返回: 最大匹配数和匹配对
    """
    match = {}  # 存储 V -> U 的匹配关系
    max_matching = 0
    
    for u in u_nodes:
        # 每次为新的 u 寻找增广路时，都要重置 visited 数组
        visited = {v: False for v in v_nodes}
        if hungarian_dfs(u, graph, match, visited):
            max_matching += 1
            
    # 整理匹配对 (U, V)
    matching_pairs = [(v, u) for u, v in match.items()]
    return max_matching, matching_pairs

# --- 案例测试 ---
# U 集合: 男生, V 集合: 女生
u_nodes = ['M1', 'M2', 'M3', 'M4']
v_nodes = ['F1', 'F2', 'F3', 'F4']

# 表示好感关系 (U -> V)
graph = {
    'M1': ['F1', 'F2'],
    'M2': ['F1'],
    'M3': ['F2', 'F3'],
    'M4': ['F4']
}

max_count, pairs = maximum_bipartite_matching(graph, u_nodes, v_nodes)

print(f"最大匹配数: {max_count}")
print(f"匹配结果: {sorted(pairs)}")

# 输出:
# 最大匹配数: 4
# 匹配结果: [('F1', 'M2'), ('F2', 'M1'), ('F3', 'M3'), ('F4', 'M4')]

复杂度分析

  • 时间复杂度: O(V * E)，其中 V 是顶点总数，E 是边数。外层循环遍历 U 中的每个顶点（最多 V 次），内层 DFS 最多访问所有边一次（E 次）。
  • 空间复杂度: O(V + E)，用于存储图和 match、visited 数组。

经典应用

  1. 任务分配：有 N 个工人和 M 个任务，每个工人只能做某些特定的任务。如何分配使得尽可能多的任务被完成？
  2. 棋盘覆盖：在一个 N x M 的棋盘上，用 1 x 2 的骨牌覆盖，最多能放多少个？（这是一个经典的二分图匹配问题，将棋盘黑白染色即可）。
  3. 在线广告：将广告位和广告商作为二分图的两部分，找到最优的广告投放匹配方案。

总结

二分图匹配是图论中一个非常经典且实用的问题，它完美地模拟了现实世界中两组资源之间的最优配对问题。匈牙利算法通过巧妙地寻找和翻转增广路，为我们提供了一种优雅而高效的解决方案。

本文核心要点

✅ 二分图：顶点可以分为两个内部无边的集合 U 和 V。
✅ 最大匹配：图中边数最多的、边与边之间没有公共顶点的边集。
✅ 增广路：一条从未匹配点开始，结束于未匹配点，且匹配边与非匹配边交替出现的路径。
✅ 匈牙利算法：不断寻找增广路来增加匹配数，直到找不到为止。时间复杂度 O(VE)。

掌握了二分图匹配，你就拥有了解决各种资源分配和优化问题的强大工具。在下一篇文章，也是图论系列的最后一篇中，我们将进入一个更高级的领域——网络流，看看如何解决管道、交通等流量优化问题。