问无向无权图推重算法s-t最小切边的实现
EN

Stack Overflow用户

提问于 2016-03-25 08:06:50

回答 1查看 903关注 0票数 3

我正在寻找一个很好的解决方案，在无向和无权图中找到s-t -min-切边。我想使用推挽算法。

但是我不知道如何实现它来找到无向和无权图上的最小割集。在每对顶点之间有两条相反的边，并在所有边上赋予相同的权重，并应用推挽算法？我能那样做吗？

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

很明显，最小切割是边(c，t).但是从最后一张图中，我怎么知道(c，t)是最小切边？还是我计算错了。

有人能指出我的错误吗？欢迎提出建议，谢谢！

回答已采纳

发布于 2016-03-31 04:46:32

找出节点高度之间的间隙，然后通过盖子找出边缘是最小切边.

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/36216258

复制

相似问题

问无向无权图推重算法s-t最小切边的实现EN