我有一个无向加权图，我需要找到分隔两组顶点的最小割。我可以修改我的设置，以便将问题减少到找到分隔两个给定顶点的最小切割。我想补充一点，权重是正数和小数。
Stoer–Wagner 算法除了将指定节点保留在切割的不同侧外，什么都做，我很好奇是否有任何修改 SW 的方法来做到这一点。
谢谢。
最佳答案
不确定 Stoer-Wagner，但解决此问题的另一种典型方法是使用 MaxFlow。
您将一组节点链接到源，另一组节点连接到具有无限容量的目的地。每隔一条边的权重应为 1，然后在结果图中执行 MaxFlow。
当你完成后，标记所有仍然可以从残差网络中的源访问的节点(在最后一次路径查找运行中访问过的节点)。原始图中标记节点和未标记节点之间的任何边都是最小割的一部分。
关于algorithm - 作为无向未加权图的输入给出的两个任意顶点之间的最小割，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36324864/