如何使用Edmonds-Karp算法获得割集？

Question

我使用在Edmonds-Karp算法维基页面上找到的伪代码实现了Edmonds-Karp算法：http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

它工作得很好，但是算法输出的是最大流量值(最小切割值)，我需要这个切割包含的边的列表

我试着改变算法，但没有成功，你们能帮上忙吗？

谢谢

Answer 1

如果你已经有了流，那么计算残差图。然后从源进行深度优先搜索(或者广度优先搜索，我认为这无关紧要)，计算切割(S)的一半的顶点。剩下的顶点在切割的另一半，T。

这会给你你的分成(S，T)。如果你特别想要S和T之间的边，你可以遍历所有的边，选择连接S和T的边(尽管可能有一种更好的方法来完成最后一部分)。

Answer 2

如果你已经知道最大流，那么最小割集是(S，T)，其中S是残差网络中从源可达的顶点集，T是互补集。连接来自S的顶点和来自T的顶点的边属于切割。

Answer 3

这里有一些提示，可以帮助澄清如何在未来为任何人做到这一点。

1. 要找到S个顶点，请从源顶点执行BFS (或DFS)搜索，仅跟随其中剩余一定流量容量的边。(换句话说，非饱和边)。根据定义，这些顶点不能在mincut中。要查找T个顶点，
2. 将从接收器顶点执行BFS (或DFS)搜索，仅连接到尚未添加到S集合的顶点。这些可能会有残余流，也可能是完全饱和的，这并不重要。因为您是从接收器执行BFS，所以如果图是有向的，则需要确保沿着边指向的相反方向进行操作。注意:重要的是在你的T集中只包含可以从水槽到达的顶点，否则你最终会在你的最小切割中包含不属于那里的边。(这让我困惑了很长一段时间。)
3. 一旦你有了这两组顶点，你就可以遍历图的所有边。任何在S中有源节点，在T中有目标节点的人都是min-cut的一部分。但是，需要注意的是，这只是许多可能的最小削减之一。在一个图中找到所有可能的S-T最小割集需要更多的时间。

希望这篇文章能帮助任何想要弄清楚这一点的网民！祝好运!