Python匈牙利算法：求解二分图最大匹配边数（含代码及详细解析）

以下是使用Python实现的解决该问题的代码，采用匈牙利算法来求解二分图的最大匹配： ```python # 匈牙利算法核心函数，用于尝试为左部点u找到匹配 def find(u, vis, match): # 遍历与左部点u相连的所有右部点 for v in graph[u]: # 如果右部点v未被访问过 if not vis[v]: # 标记右部点v为已访问 vis[v] = True # 如果右部点v还没有匹配，或者可以为其原来的匹配点找到新的匹配 if match[v] == -1 or find(match[v], vis, match): # 更新匹配关系 match[v] = u return True return False # 读取输入 n, m, e = map(int, input().split()) # 初始化图的邻接表 graph = [[] for _ in range(n + 1)] # 存储右部点的匹配信息 match = [-1] * (m + 1) # 构建图的邻接表 for _ in range(e): u, v = map(int, input().split()) graph[u].append(v) # 最大匹配的边数 res = 0 # 遍历左部点 for i in range(1, n + 1): # 标记右部点是否被访问过 vis = [False] * (m + 1) # 如果能为左部点i找到匹配 if find(i, vis, match): res += 1 # 输出最大匹配的边数 print(res) ``` 代码解释： 1. `find`函数：该函数使用递归的方式尝试为左部点`u`找到匹配。它遍历与`u`相连的所有右部点`v`，如果`v`未被访问过，标记其为已访问，然后检查`v`是否还没有匹配，或者可以为其原来的匹配点找到新的匹配。如果满足条件，则更新匹配关系并返回`True`，否则返回`False`。 2. 读取输入：读取左部点的个数`n`、右部点的个数`m`和边数`e`，并构建图的邻接表。 3. 初始化匹配信息：使用`match`数组来存储右部点的匹配信息，初始值为`-1`表示未匹配。 4. 构建图的邻接表：根据输入的边信息，将边添加到邻接表中。 5. 求解最大匹配：遍历左部点，对于每个左部点，调用`find`函数尝试为其找到匹配。如果能找到匹配，则最大匹配的边数加1。 6. 输出结果：输出最大匹配的边数。 复杂度分析： - 时间复杂度：$O(n * e)$，其中`n`是左部点的个数，`e`是边数。 - 空间复杂度：$O(n + m + e)$，主要用于存储图的邻接表和匹配信息。 ######[AI问答 | 715点数解答 | 2025-12-12 18:44:19]