我使用在 Edmonds–Karp 算法 wiki 页面中找到的伪代码实现了 Edmonds–Karp 算法：http ://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm
它工作得很好，但算法输出是最大流量值（最小切割值），我需要这个切割包含的边列表
我试图改变算法，但没有成功，你们能帮忙吗？
谢谢
问问题
4976 次
3 回答
4
如果您已经有流量，则计算残差图。然后从源头进行深度优先搜索（或广度优先搜索，我认为这并不重要），以计算切割一半（S）中的顶点。剩余的顶点在切割的另一半，T。
这给了你你的削减（S，T）。如果您特别想要 S 和 T 之间的边缘，则可以遍历所有边缘，选择连接 S 和 T 的边缘。（尽管最后一部分可能有一种更优雅的方式。）
于 2011-03-21T17:04:31.420 回答
2
如果你已经知道最大流，那么最小割就是(S, T)，其中S是残差网络中从源点可达的顶点集，T是互补集。连接来自 S 的顶点和来自 T 的顶点的边属于割。
于 2011-03-21T16:48:00.107 回答
2
这里有一些提示可以帮助阐明将来如何为任何人执行此操作。
要找到 S 个顶点，请从源顶点执行 BFS（或 DFS）搜索，仅跟踪剩余一些流动容量的边。（换句话说，非饱和边缘）。根据定义，这些不能在 mincut 中。
要找到 T 个顶点，请从汇顶点执行 BFS（或 DFS）搜索，仅连接到尚未添加到 S 集合的顶点。这些可能有剩余流量，或者可能完全饱和，没关系。因为您是从接收器执行 BFS，所以如果图形是定向的，您需要确保遵循边缘指向的相反方向。注意：重要的是只包括可以从T 集合中的接收器到达的顶点，否则您最终会在最小切割中包含不属于那里的边。（这是让我很长时间的事情。）
一旦你有了这两组顶点，你就可以遍历图的所有边。在 S 中具有源节点并且在 T 中具有目标节点的任何人都是您的最小切割的一部分。不过，重要的是要注意，这只是许多可能的最小削减之一。在图中找到所有可能的 ST 最小切割需要更多时间。
希望这可以帮助任何试图解决这个问题的未来互联网人！祝你好运！
于 2012-07-31T23:01:32.390 回答