一般图的最大匹配算法python代码

一般图的最大匹配算法可以使用Hopcroft-Karp算法来实现，以下是使用Python实现的代码：

from collections import deque

class HopcroftKarp:
    def __init__(self, graph):
        self.graph = graph
        self.left = set(graph.keys())
        self.right = set()
        self.pair = {}
        self.dist = {}
        self.unmatched = set()

    def bfs(self):
        queue = deque()
        for v in self.left:
            if v not in self.pair:
                self.dist[v] = 0
                queue.append(v)
            else:
                self.dist[v] = float('inf')
        self.dist[None] = float('inf')
        while queue:
            v = queue.popleft()
            if self.dist[v] < self.dist[None]:
                for u in self.graph[v]:
                    if self.dist.get(self.pair[u], float('inf')) == float('inf'):
                        self.dist[self.pair[u]] = self.dist[v] + 1
                        queue.append(self.pair[u])
        return self.dist[None] != float('inf')

    def dfs(self, v):
        if v is not None:
            for u in self.graph[v]:
                if self.dist[self.pair[u]] == self.dist[v] + 1:
                    if self.dfs(self.pair[u]):
                        self.pair[u] = v
                        self.pair[v] = u
                        return True
            self.dist[v] = float('inf')
            return False
        return True

    def match(self):
        while self.bfs():
            for v in self.left:
                if v not in self.pair:
                    if self.dfs(v):
                        self.unmatched.add(v)
        return self.pair

其中，graph是一个字典，表示图的邻接表。例如，对于如下图：

1---2
|\ /|
| X |
|/ \|
3---4

邻接表可以表示为：

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}

使用方法如下：

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 4],
    4: [2, 3]
}
hk = HopcroftKarp(graph)
matching = hk.match()
print(matching)  # {1: 2, 2: 1, 3: 4, 4: 3}

输出结果是一个字典，表示匹配结果。例如，{1: 2, 2: 1, 3: 4, 4: 3}表示1和2匹配，3和4匹配。