查找边缘不相交的路径（不是数字，路径）

Question

给定一个有向图，我们可以使用 edmonds-karp 或 ford-fulkerson 算法在有向图中找到边不相交路径的最大数量。

假设G中有k条边不相交的路径，如何在多项式时间内找到实际路径？我最好的选择是 BFS，一旦找到路径，将这些边标记为已使用。

非常感谢！

Answer 1

可以使用流分解。它是这样的：

1. 让我们运行从起始节点开始深度优先搜索并忽略具有零流或负流的边。

2. 一旦到达终端节点，从起始节点到终端节点的路径上的所有边的流中减去一个并打印它们（它们形成一条路径）。

3. 只要终端节点可达，就继续这样做。

每个 运行 使用多项式时间量并从图中找到并删除一条路径。不相交路径的数量显然是多项式的，因此该算法具有多项式时间复杂度。

你也可以使用广度优先搜索（你仍然需要忽略非正流的边缘）。