c++ - 为什么在 Edmonds-Karp 最大流量中必须考虑后缘？

Question

我正在尝试实现 Edmonds-Karp在 C++ 中以获得最大流量，我写的略有不同:

1. 我没有遍历残差图中的所有边，而是使用邻接表仅遍历了原始图中存在的边。
2. 在用最小流量更新残差图时，我没有更新任何后边。

有趣的是，当我运行我的代码时，它给出了正确的结果。所以我去了Wikipedia's example ，它专门显示了如何使用后缘。当我将这张图输入我的代码时，我再次得到了正确的答案。我还检查了合成流矩阵，它与维基百科的相同。

有人可以解释为什么我们必须添加和更新后缘，并可能举例说明它们的重要性吗？

Here是我编写的代码(已更新以包括后缘):

Answer 1

考虑下面的流网络

假设第一个流是s → u → v → t。 (如果你反对 Edmonds-Karp 的 BFS 永远不会选择这个，那么在 s 和 v 之间以及 u 和 t)。

如果不逆流u → v，是不可能得到最优流20的。