Python实现匈牙利算法

匈牙利算法（又称为二分图最大匹配算法）是解决二分图最大匹配问题的经典算法。下面是 Python 实现匈牙利算法的示例代码：

class Hungary:
    def __init__(self, graph):
        self.graph = graph
        self.m = len(graph)
        self.n = len(graph[0])
        self.match = [-1] * self.n
    
    def find(self, u, seen, match):
        for v in range(self.n):
            if self.graph[u][v] and not seen[v]:
                seen[v] = True
                if match[v] == -1 or self.find(match[v], seen, match):
                    match[v] = u
                    return True
        return False
    
    def max_matching(self):
        result = 0
        for i in range(self.m):
            seen = [False] * self.n
            if self.find(i, seen, self.match):
                result += 1
        return result

其中，`graph` 是一个二维列表，表示二分图的邻接矩阵。`match` 是一个一维列表，用于记录匹配情况。`find` 函数使用递归实现 DFS 搜索，寻找增广路。`max_matching` 函数则遍历所有左侧节点，使用 `find` 函数搜索增广路并更新匹配情况，最终返回最大匹配数。

使用示例：

graph = [
    [1, 1, 0, 0],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [0, 0, 1, 0],
]
hungary = Hungary(graph)
print(hungary.max_matching()) # 输出 3

该示例中，二分图为：

1 -- 2
|    |
3 -- 4

其中，匹配情况为 1-2、2-3、3-4，最大匹配数为 3。