匈牙利算法代码用python写出来

匈牙利算法是一种求解二分图最大匹配的算法。以下是使用 Python 实现匈牙利算法的代码：

# 定义一个函数来实现匈牙利算法
def hungarian_algorithm(graph):
    # 初始化左部顶点和右部顶点的匹配情况为空
    l_match = {l: None for l in graph.keys()}
    r_match = {r: None for r in set(v for values in graph.values() for v in values)}

    # 定义一个函数来搜索增广路径
    def dfs(l):
        # 遍历左部顶点可到达的所有右部顶点
        for r in graph[l]:
            # 如果当前右部顶点还没有被匹配，或者可以尝试修改当前匹配
            if r_match[r] is None or dfs(r_match[r]):
                # 则更新匹配情况
                l_match[l] = r
                r_match[r] = l
                return True
        return False

    # 遍历所有的左部顶点，尝试寻找增广路径
    for l in graph.keys():
        if l_match[l] is None:
            dfs(l)

    # 返回左部顶点和右部顶点的匹配情况
    return l_match, r_match

其中，`graph` 是一个字典，用于存储二分图的邻接表信息，例如：

graph = {
    'a': ['x', 'y'],
    'b': ['y', 'z'],
    'c': ['y']
}

表示左部顶点 `a` 可以与右部顶点 `x` 和 `y` 相连，左部顶点 `b` 可以与右部顶点 `y` 和 `z` 相连，左部顶点 `c` 可以与右部顶点 `y` 相连。在上面的代码中，我们使用了深度优先搜索来查找增广路径，直到无法找到新的增广路径为止。最后，返回左部顶点和右部顶点的匹配情况。