我有一个无向加权图，我需要找到分隔两组顶点的最小割集。我可以修改我的设置，以便将问题减少到找到分隔两个给定顶点的最小割集。我想补充一下，权重是正数和小数。
stoer-wagner算法除了在切割的不同边上保留指定的节点外，什么都做，我很好奇是否有任何方法可以修改sw来做到这一点。
谢谢您。
最佳答案
不确定Stoer Wagner，但是解决这个问题的另一个关键方法是使用MaxFlow。
将一组节点链接到源节点，另一组链接到容量无限的目标节点。每隔一条边的权重应为1，然后在结果图中执行MaxFlow。
完成后，标记剩余网络中仍可以从源访问的所有节点（上次路径查找运行时访问的节点）。在原始图中有标记和无标记节点之间的任何边都是最小割集的一部分。