匈牙利算法python实现
时间: 2024-04-27 18:17:00 浏览: 13
匈牙利算法是一种解决二分图最大匹配问题的经典算法。下面是匈牙利算法的Python实现:
```python
def hungarian(graph):
# 初始化匹配结果和标记数组
match = {}
for u in graph.keys():
match[u] = None
visited = {}
# 定义DFS函数
def dfs(u):
for v in graph[u]:
if not visited.get(v, False):
visited[v] = True
if match[v] is None or dfs(match[v]):
match[v] = u
return True
return False
# 遍历所有顶点,进行匹配
for u in graph.keys():
visited.clear()
dfs(u)
# 返回匹配结果
return match
# 示例图的邻接表表示
graph = {
'A': ['a', 'b'],
'B': ['a'],
'C': ['b', 'c'],
'D': ['c']
}
# 调用匈牙利算法求解最大匹配
matching = hungarian(graph)
print(matching)
```
上述代码中,我们首先定义了一个`hungarian`函数来实现匈牙利算法。在该函数中,我们使用DFS来寻找增广路径,并通过`match`字典来记录匹配结果。最后,我们调用`hungarian`函数并传入示例图的邻接表表示,得到最大匹配的结果。