algorithm - 作为无向无权图的输入给定的两个任意顶点之间的最小割

Question

我有一个无向加权图，我需要找到分隔两组顶点的最小割。我可以修改我的设置，以减少找到分隔两个给定顶点的最小切割的问题。我想补充一点，权重是正数和分数。

Stoer-Wagner 算法除了将指定节点保留在切口的不同侧之外，什么都做，我很好奇是否有任何方法可以修改 SW 来做到这一点。

谢谢你。

Answer 1

不确定 Stoer-Wagner，但解决此问题的另一种典型方法是使用 MaxFlow。

您将一组节点链接到源，将另一组节点链接到具有无限容量的目标。每隔一条边的权重应该为 1，然后在结果图中执行 MaxFlow。

完成后，标记剩余网络中仍可从源访问的所有节点（上次路径查找运行时访问的节点）。原始图中标记和未标记节点之间的任何边都是最小割的一部分。