查找扩充路径(最大匹配)

Question

我必须在Python中实现一个find_augmenting_path(n，边，匹配(的函数，如果没有扩充路径，则返回None，或者以顶点列表的形式返回这样的路径。

边缘是边缘的列表，例如：[(1,2(， (2,3(...] n 是顶点数 匹配是有效的匹配(边缘列表(

从昨天开始，我一直在寻找如何做到这一点，但我找不到解决方案。

我已经编写了一个函数来找出是否存在增强路径。 我现在必须编写如何找到此路径的代码。

如果有人有想法，请告诉我。 我需要你的帮助

非常感谢

Answer 1

您可以使用networkx模块：

import networkx as nx
l = [(12,9), (1,2), (2,5), (4,7), (5,3), (4,9), (9,4), (1,2), (3,9), (8,5), (5,5), (1,9), (5,12)]
G = nx.DiGraph(l)
paths = nx.all_simple_paths(G, 1, 9)
for path in map(nx.utils.pairwise, paths):
print(list(path))

输出：

[(1, 2), (2, 5), (5, 3), (3, 9)]
[(1, 2), (2, 5), (5, 12), (12, 9)]
[(1, 9)]

该程序使用networkx来查找从1开始到9结束的所有可能路径，并且这些数字是可变的。