最大匹配算法python代码

以下是基于匈牙利算法的最大匹配算法的Python代码：

def max_matching(graph):
    """
    Find the maximum matching in a bipartite graph using the Hungarian algorithm.
    The graph is represented as an adjacency list, where the keys are the vertices on one side
    of the bipartition and the values are lists of vertices on the other side of the bipartition that
    are connected to the key vertex.
    """
    # Initialize the matching to be empty
    matching = {}
    for u in graph.keys():
        matching[u] = None

    # Find the augmenting path using DFS
    def dfs(u, visited):
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                if matching[v] is None or dfs(matching[v], visited):
                    matching[v] = u
                    return True
        return False

    # Find the maximum matching by iterating through all vertices in the first partition
    for u in graph.keys():
        dfs(u, set())

    # Count the number of edges in the matching
    num_edges = sum(1 for u in graph.keys() if matching[u] is not None)

    return matching, num_edges

其中，`graph` 是一个字典，键为第一部分的顶点，值为与该顶点相连的第二部分的顶点列表。函数返回一个元组，第一个元素是匹配，第二个元素是匹配的边数。