我正在尝试实现Edmonds-Karp在C++中以获得最大流量，我写的略有不同:我没有遍历残差图中的所有边，而是使用邻接表仅遍历了原始图中存在的边。在用最小流量更新残差图时，我没有更新任何后边。有趣的是，当我运行我的代码时，它给出了正确的结果。所以我去了Wikipedia'sexample，它专门显示了如何使用后缘。当我将这张图输入我的代码时，我再次得到了正确的答案。我还检查了合成流矩阵，它与维基百科的相同。有人可以解释为什么我们必须添加和更新后缘，并可能举例说明它们的重要性吗？Here是我编写的代码(已更新以包括后缘): 最佳答案

我使用在Edmonds–Karp算法维基页面中找到的伪代码实现了Edmonds–Karp算法:http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm效果很好，但算法输出的是最大流值(最小切割值)，我需要这个切割包含的边列表我尝试更改算法，但没有成功，你们能帮忙吗？谢谢 最佳答案 如果您已经有了流，则计算残差图。然后从源进行深度优先搜索(或广度优先搜索，我认为这不重要)，以计算切割(S)的一半中的顶点。剩余的顶点位于切割的另一半T。这为您提供了切分(S,T)。如果您特别想