找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法:二分图最大匹配

admin 2019-10-10 07:18 97人围观 C++相关

# Find maximum bipartite matching (mBPM) for an undirected bipartite graph (BPG)
# ref: https://www.geeksforgeeks.org/maximum-bipartite-matching/
class Graph():
def __init__(self):
self.edges = {}
self.paired = {}
self.visited = {}
def add_edge(self,v,u):
edges = self.edges
edges.setdefault(v,[])
edges[v].append(u)
edges.setdefault(u,[])
edges[u].append(v)
def traverse(self,v):
edges = self.edges
paired = self.paired
visited = self.visited
for j in range(len(edges[v])):
u = edges[v][j]
if visited[u] == False:
visited[u] = True
if paired[u] == None or self.traverse(paired[u]):
paired[u] = v
paired[v] = u
return True
return False
def mBPM(self,edges):
edges = self.edges
paired = self.paired
visited = self.visited
flag = set()
total_pair = []
for v in edges:
paired[v] = None
visited[v] = False
for v in edges:
if paired[v] == None:
self.traverse(v)
for v in edges:
if paired[v] and v not in flag:
flag.add(paired[v])
total_pair.append((v,paired[v]))
return total_pair
# graph = [[1,4],[1,5],[2,5],[2,6],[3,4]]
graph = [[1,2],[1,3],[2,1],[2,4],[4,3],[6,6],[3,3],[4,4]]
G = Graph()
for e in graph:
G.add_edge(e[0],e[1])
print(G.mBPM(G.edges))


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:我的时光穿梭机,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......