匈牙利算法python代码

匈牙利算法是图论中解决二分图最大匹配问题的经典算法之一，其具有时间复杂度为 O(V*E) 的优秀性能表现。在Python中，我们可以采用深度优先搜索（DFS）以及递归的方式实现匈牙利算法，具体代码如下：

def hungarian(graph):
    match = [-1] * len(graph)
    def dfs(u):
        for v in range(len(graph[0])):
            if graph[u][v] and not seen[v]:
                seen[v] = True
                if match[v] == -1 or dfs(match[v]):
                    match[v] = u
                    return True
        return False
    for u in range(len(graph)):
        seen = [False] * len(graph[0])
        dfs(u)
    return match

首先，我们初始化一个长度为二分图大小的空匹配列表。然后，我们定义一个递归的深度优先搜索函数 `dfs`，该函数根据图中每个未匹配点的情况不断匹配。在搜索时，我们从一侧顶点出发，遍历该顶点所连的所有另一侧顶点。对于每一个未被搜索的顶点，我们将其状态修改为已被搜索，并判断其是否被匹配。当搜索到一个未被匹配的顶点时，我们将其所对应的匹配位置修改为当前顶点，返回True即可。如果没有未匹配的顶点，则返回False。最后，在主函数中，将每个顶点都遍历一遍，进行匹配，并返回匹配列表即可。

总之，通过以上Python代码的实现，我们可以简单高效地解决二分图最大匹配问题。