Python实现最大匹配算法-匈牙利算法 中遇到的问题

Question

首先给大家看一下自己用的代码：

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输出的却只有两个，自己觉得也应该是四个，不知道为啥会有这种矛盾，处理别的数据有时候没问题，有时候也会有矛盾
希望可以得到大家的帮助！

Answer 1

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。
这种情况如果不是正常就要调整下代码逻辑。