匈牙利算法求二分图的最大匹配数

匈牙利算法是一种用于求解二分图最大匹配问题的经典算法。它的基本思想是通过不断增广增加匹配的边数，直到无法再增广为止。下面是匈牙利算法求解二分图最大匹配数的步骤：

1. 初始化一个空的匹配M。
2. 对于二分图中的每个顶点v，如果v没有被匹配，则从v开始进行增广路径的搜索。
3. 在增广路径的搜索中，从顶点v开始，依次遍历与v相邻的未匹配的顶点u。
4. 如果u没有被访问过，则将u标记为已访问，并尝试将u与v匹配。
5. 如果u已经被访问过，且u已经在当前增广路径中，则说明找到了一个增广路径，需要进行路径的反向操作，即将路径上的所有边的匹配状态进行反转。
6. 重复步骤3-5，直到无法再找到增广路径为止。
7. 返回匹配M的边数，即为二分图的最大匹配数。

下面是一个使用Python实现的匈牙利算法的示例代码：

def hungarian_algorithm(graph):
    def dfs(v):
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                if match[u] == -1 or dfs(match[u]):
                    match[u] = v
                    return True
        return False

    match = [-1] * len(graph)
    count = 0
    for v in range(len(graph)):
        visited = [False] * len(graph)
        if dfs(v):
            count += 1
    return count

# 示例二分图的邻接表表示
graph = {
    0: [3],
    1: [3],
    2: [4],
    3: [0, 1, 4],
    4: [2, 3]
}

max_matching = hungarian_algorithm(graph)
print("二分图的最大匹配数为:", max_matching)