匈牙利算法 python

匈牙利算法是一种解决二分图最大匹配问题的算法，它的时间复杂度为 O(n^3)。下面是一个简单的 Python 实现：

def hungarian_algorithm(graph):
    n = len(graph)
    match = [-1] * n
    for i in range(n):
        visited = [False] * n
        if dfs(graph, i, visited, match):
            continue
        for j in range(n):
            visited = [False] * n
            if dfs(graph, i, visited, match):
                break
    return match

def dfs(graph, i, visited, match):
    for j in range(len(graph[i])):
        if not visited[j] and graph[i][j]:
            visited[j] = True
            if match[j] == -1 or dfs(graph, match[j], visited, match):
                match[j] = i
                return True
    return False

其中，`graph` 是一个邻接矩阵，表示二分图的连接情况。如果 `graph[i][j]` 为 1，则表示左边第 `i` 个节点和右边第 `j` 个节点之间有一条边。