hopcraft算法实现

Hopcroft-Karp算法是解决二分图最大匹配问题的一种高效算法，时间复杂度为O(E*sqrt(V))，其中E为边数，V为点数。

以下是Hopcroft-Karp算法的实现：

# -*- coding: utf-8 -*-
"""
Created on Thu Jul 22 16:31:19 2021

Hopcroft-Karp算法实现二分图最大匹配

"""

from collections import deque

class BipartiteGraph():
    def __init__(self, adj_list):
        self.adj_list = adj_list
        self.left = set(adj_list.keys())
        self.right = set()
        for v_list in adj_list.values():
            self.right |= set(v_list)
        self.match = {}
        self.dist = {}

    def BFS(self):
        queue = deque()
        for v in self.left:
            if self.match[v] is None:
                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.adj_list[v]:
                    if self.dist[self.match[u]] == float('inf'):
                        self.dist[self.match[u]] = self.dist[v] + 1
                        queue.append(self.match[u])
        return self.dist[None] != float('inf')

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

    def max_matching(self):
        for v in self.left:
            self.match[v] = None
        for u in self.right:
            self.match[u] = None
        matching = 0
        while self.BFS():
            for v in self.left:
                if self.match[v] is None:
                    if self.DFS(v):
                        matching += 1
        return matching

# 测试代码
if __name__ == '__main__':
    adj_list = {1: [4],
                2: [4, 5],
                3: [5],
                4: [1, 2],
                5: [2, 3]}
    graph = BipartiteGraph(adj_list)
    print(graph.max_matching())

输入的参数adj_list是一个字典，表示二分图的邻接表。例如，对于二分图{(1,4),(2,4),(2,5),(3,5)}，邻接表为{1:[4], 2:[4,5], 3:[5], 4:[1,2], 5:[2,3]}。

输出为最大匹配数，对于上述例子，输出为3。