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

Question

我使用在Edmonds-Karp算法维基页面找到的伪代码实现了该算法：http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm。它运行得很好，但是算法的输出只是最大流值(最小割值)，我需要这个割包含的边的列表。

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

谢谢。

- ciochPep

Answer 1

如果您已拥有流程，则计算剩余图。然后从源点开始进行深度优先搜索（或广度优先搜索，我认为这没有关系），以计算切割的一半（S）中的顶点。其余的顶点在您的另一半切割中，即T。

这将给您提供切割（S,T）。如果您特别想要S和T之间的边，可以遍历所有边，选择连接S和T的边。（虽然可能有更优雅的方法来完成最后一部分。）

- Rob Lachlan

---

你能解释一下 F nXn 矩阵中数字的含义吗？我应该如何准确地使用它们？ - ciochPep

@ciochPep：矩阵F给出了图中每条边上的流量，以实现最大流量 - 实际上，Edmonds Karp算法旨在计算这一点。这也使得计算剩余图变得容易：它只是矩阵C和矩阵F之差。 - Rob Lachlan

Answer 2

这里有一些提示，可以帮助任何人在未来搞清楚如何进行以下操作：

1. 为了找到S顶点，请从源顶点开始进行BFS（或DFS）搜索，仅跟随某些剩余流量容量的边。 （换句话说，非饱和边）。 这些定义上不能在最小割中。

2. 要找到T顶点，请从汇点顶点开始执行BFS（或DFS）搜索，只连接尚未添加到S集合中的顶点。 它们可以具有剩余流量，也可能完全饱和，这并不重要。 因为您正在从汇点执行BFS，所以如果图形是定向的，则需要确保按相反方向沿着边指向传递。 注意：仅在T集合中包括可以从汇点到达的顶点很重要，否则您将在最小割中包含不属于那里的边缘。 （这是让我困扰了很长时间的原因。）

3. 一旦您拥有这两组顶点，就可以迭代整个图的所有边。 任何具有在S中的源节点和在T中的目标节点的边缘都是最小割的一部分。 但是要注意，这只是许多可能的最小割之一。 在图中找到所有可能的S-T最小割需要更多时间。

希望这有助于任何未来尝试弄清楚这个问题的人们！祝你好运！

- Patrick M

Answer 3

如果你已经知道了最大流量，那么最小割是（S，T），其中S是从源节点在残余网络中可到达的顶点集，而T是补集。连接S中的一个顶点和T中的一个顶点的边属于割。

- adamax

---

我只知道最小割值，但不知道集合。 - ciochPep

@ciochPep 你说你实现了Edmonds-Karp算法？它可以找到流量和值。 - adamax

你能解释一下 F nXn 矩阵中数字的含义吗？我应该如何准确地使用它们？ - ciochPep

@ciochPep F[i,j] 是从 i 到 j 的边上的流量。在实际算法中，它可能被表示为边的列表，而不是矩阵。 - adamax