编辑“︁二分图匹配”︁（章节）

== 二分图匹配的算法 ==

=== 匈牙利算法 ===
'''匈牙利算法'''（Hungarian Algorithm）是求解二分图最大匹配的经典算法，其时间复杂度为 <math>O(VE)</math>，其中 <math>V</math> 是顶点数，<math>E</math> 是边数。

==== 算法步骤 ====
1. 初始化匹配为空。
2. 对于每个未匹配的顶点 <math>u \in U</math>，尝试通过增广路径找到匹配。
3. 增广路径是指从 <math>u</math> 出发，交替经过未匹配边和匹配边，最终到达一个未匹配的顶点 <math>v \in V</math>。
4. 如果找到增广路径，则反转路径上的边的匹配状态（未匹配的边变为匹配，匹配的边变为未匹配），从而增加匹配数。

==== 代码示例 ====
以下是用 Python 实现的匈牙利算法：

<syntaxhighlight lang="python">
def bpm(u, match_to, visited, graph):
    for v in range(len(graph[0])):
        if graph[u][v] and not visited[v]:
            visited[v] = True
            if match_to[v] == -1 or bpm(match_to[v], match_to, visited, graph):
                match_to[v] = u
                return True
    return False

def max_bipartite_matching(graph):
    num_u = len(graph)
    num_v = len(graph[0])
    match_to = [-1] * num_v
    result = 0

    for u in range(num_u):
        visited = [False] * num_v
        if bpm(u, match_to, visited, graph):
            result += 1
    return result

# 示例输入：二分图的邻接矩阵表示
graph = [
    [1, 1, 0],
    [0, 1, 1],
    [1, 0, 0]
]
print("最大匹配数:", max_bipartite_matching(graph))  # 输出: 3
</syntaxhighlight>

==== 输入输出说明 ====
- 输入：邻接矩阵 <code>graph</code>，其中 <code>graph[u][v] = 1</code> 表示 <math>u \in U</math> 和 <math>v \in V</math> 之间有边。
- 输出：最大匹配数。对于示例，最大匹配数为 3。

=== Hopcroft-Karp 算法 ===
'''Hopcroft-Karp 算法'''是一种更高效的算法，时间复杂度为 <math>O(\sqrt{V}E)</math>，适用于大规模二分图。