匈牙利算法python代码
时间: 2023-07-06 07:06:07 浏览: 41
下面是一个简单的匈牙利算法的Python实现:
```python
# 二分图最大匹配,返回最大匹配数
def hungarian_algorithm(graph):
n = len(graph)
match = [-1] * n # 存储匹配信息,match[i]表示右侧第i个点匹配的左侧点编号
vis = [False] * n # 记录每个点是否被访问过
def dfs(u):
for v in range(n):
if graph[u][v] and not vis[v]:
vis[v] = True
if match[v] == -1 or dfs(match[v]):
match[v] = u
return True
return False
res = 0
for u in range(n):
vis = [False] * n
if dfs(u):
res += 1
return res
```
其中,`graph`是一个二维数组,表示二分图的邻接矩阵,`graph[i][j]`表示左侧第i个点和右侧第j个点是否有连边。函数返回最大匹配数。
相关问题
匈牙利算法代码python
下面是一个基于Python的匈牙利算法实现的代码示例:
```python
def max_match(graph):
# 初始化匹配状态
match = {}
for u in graph.keys():
match[u] = None
for v in graph.keys():
# 如果该顶点还没有匹配,则从该顶点开始查找增广路
if match[v] is None:
# 初始化标记数组和搜索队列
visited = {}
queue = []
for u in graph.keys():
visited[u] = False
queue.append(v)
visited[v] = True
# 使用广度优先搜索查找增广路
found = False
while len(queue) > 0:
u = queue.pop(0)
for w in graph[u]:
if not visited[w]:
visited[w] = True
if match[w] is None:
# 找到增广路,更新匹配状态
match[w] = u
match[u] = w
found = True
break
else:
# 将已匹配的顶点加入搜索队列
queue.append(match[w])
if found:
break
# 返回最大匹配数
count = 0
for u in graph.keys():
if match[u] is not None:
count += 1
return count
```
其中,`graph`是一个字典,表示二分图中每个顶点的邻接表。例如,若二分图中有顶点`u`和`v`,它们之间有一条边,则`graph`应该包含如下的键值对:
```
graph = {
'u': ['v'],
'v': ['u']
}
```
该算法的时间复杂度为$O(mn)$,其中$m$和$n$分别为二分图中的顶点数和边数。
匈牙利算法python实现
匈牙利算法是一种解决二分图最大匹配问题的经典算法。下面是匈牙利算法的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`函数并传入示例图的邻接表表示,得到最大匹配的结果。