给定G = (V,E)中的两个顶点u和v和一个正整数k，描述一个算法来判断是否存在从u到v的k条边不相交的路径。如果判断问题的答案是肯定的，描述如何计算一组 k 边不相交的路径。
解决方案: 运行从 u 到 v 的最大流(给图 G 中的所有边赋予 1 的权重，以便一条边只能是从 u 到 v 的一条路径的一部分)并得到流量的值(value)。如果流量的值为 k，那么我们对决策问题的答案是肯定的。
现在为了找到所有这样的路径，通过从 u 执行 BFS 找到最小切割，因此我将进行顶点划分，它将顶点分成 2 组，在最小切割的每一侧。
然后我是否需要再次执行从 u 到 v 的 DFS 以查找所有只有这些顶点的路径，这些顶点位于我从最小切割得到的两个分区集中。
或者还有其他更清洁的方法吗？得到所有的 k 边不相交路径。
最佳答案
一旦有了流程，您就可以按照流程提取边缘不相交的路径。
起始节点将有 k 条流沿着 k 条边离开 u。
对于这些边中的每一个，您都可以继续沿流出流的方向移动以提取路径，直到到达 v。您需要做的就是标记您已经使用过的边以避免重复边。
对离开 u 的 k 个流量单元中的每一个重复以提取所有 k 个路径。
伪代码
repeat k times:
set x to start node
set path to []
while x is not equal to end node:
find a edge from x which has flow>0, let y be the vertex at the far end
decrease flow from x->y by 1 unit
append y to path
set x equal to y
print path
关于algorithm - 有向图中的 K 边不相交路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36899632/