algorithm - 为无向未加权图实现推送重新标记算法 s-t 最小切割边

Question

我正在寻找一个很好的解决方案来在无向和无权图中找到 s-t 最小割边。我想使用 push-relabel 算法。

但我不确定如何实现它以在无向和未加权图上找到最小割。在每对顶点之间有两条反向边，并在所有边上赋予相同的权重，并应用 push-relabel 算法？我可以用那种方式得到最小切割吗？

我在下图上试过了。顶点上的 a(m,n) 表示 e(a)=m,h(a)=n。每条边的容量都设置为1。

显然，最小割是边 (c,t)。但是从最后一张图片，我怎么知道(c，t)是最小切割边缘？还是我计算错了。

有人可以在这里指出我的错误吗？欢迎指教，谢谢!

Answer 1

找到节点高度之间的间隙，然后通过 cap 找到最小切割边缘的边缘。