首先给大家看一下自己用的代码：
import copy
class DFS_hungarian_tree():
def __init__(self, nx, ny, edge):
self.nx, self.ny = nx, ny # bipartite graph
self.edge = edge # adjacent matrix
self.vertex_num = len(self.nx) + len(self.ny)
self.cx, self.cy = {}, {}
for key in nx:
self.cx.update({key:0}) # 0->free other->matched
for key in ny:
self.cy.update({key:0}) # 0->free other->matched
self.visited = copy.deepcopy(self.cy) # 0->unvisited 1->visited
self.M=[] # matching map
def max_match(self):
aug_num = 0 # augment num
for i in self.nx:
if self.cx[i] == 0: # if free
for key in self.ny: # restore default value
self.visited[key] = 0
aug_num += self.path(i)
return aug_num
def path(self, u):
for v in self.ny:
if self.edge[u][v] and (not self.visited[v]): # edge exist & unvisited
self.visited[v] = 1 # prevent repeat visit
if self.cy[v] == 0: # if free
self.cx[u] = v
self.cy[v] = u
self.M.append((u,v)) # restore line
return 1
else: # if matched
self.M.remove((self.cy[v], v)) # remove conflict path
if self.path(self.cy[v]): # draw another line if have another path
self.cx[u] = v
self.cy[v] = u
self.M.append((u, v))
return 1
return 0
if __name__ == '__main__':
nx = ['A', 'B', 'C', 'D', 'E']
ny = ['F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']
edge = {'A': {'F': 1, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 1, 'L': 0, 'M': 0, 'N': 0, 'O': 0},
'B': {'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 0, 'L': 0, 'M': 0, 'N': 0, 'O': 0},
'C': {'F': 1, 'G': 1, 'H': 0, 'I': 1, 'J': 1, 'K': 0, 'L': 0, 'M': 1, 'N': 1, 'O': 0},
'D': {'F': 0, 'G': 0, 'H': 0, 'I': 0, 'J': 0, 'K': 1, 'L': 0, 'M': 0, 'N': 0, 'O': 0},
'E': {'F': 0, 'G': 1, 'H': 1, 'I': 1, 'J': 0, 'K': 1, 'L': 1, 'M': 1, 'N': 0, 'O': 1}}
Hungrian = DFS_hungarian_tree(nx, ny, edge)
print('ouput:')
print('Hungrian.max_match', end = '->')
print(Hungrian.max_match())
print('Hungrian.M', end = '->')
print(Hungrian.M)
输出结果：
C:\Users\Administrator\AppData\Local\Programs\Python\Python36\python.exe C:/Users/Administrator/Desktop/xyl.py
ouput:
Hungrian.max_match->4
Hungrian.M->[('C', 'I'), ('E', 'G')]
进程已结束，退出代码 0
问题来了：
Hungrian.max_match输出结果为4，也就是说应该有4个匹配结果，可是Hungrian.M输出的却只有两个，自己觉得也应该是四个，不知道为啥会有这种矛盾，处理别的数据有时候没问题，有时候也会有矛盾
希望可以得到大家的帮助！
def path()方法中:
self.M.remove((self.cy[v], v)) # remove conflict path
if self.path(self.cy[v]): # draw another line if have another path
self.cx[u] = v
self.cy[v] = u
self.M.append((u, v))
return 1
有可能只执行了 self.M.remove((self.cy[v], v)) 从M列表中移除元素之后没有再执行 self.M.append((u, v))再添加，
这种情况如果正常， 则应该return -1。
这种情况如果不是正常就要调整下代码逻辑。