2012-03-07 119 views
0

任何人都可以给我一个想法找到最小切的图(V,E,c,s,t,f)其中f [v] [w]是最大流量和c [v] [w]是容量?算法找到最小削减给定的最大流量

+0

Google?这里有很多东西,你到底有什么问题? – 2012-03-07 11:44:49

+0

可能的重复[如何使用最大流算法找到图上的最小切点?](http://stackoverflow.com/questions/4482986/how-can-i-find-the-minimum-cut-on -a-graph-using-a-maximum-flow-algorithm) – 2012-03-07 11:59:18

+1

这是一个真正的问题。那些关闭它的人不理解最大流最小割定理。 – wcochran 2012-11-16 22:55:00

回答

4

从源节点运行BFS或DFS。你不能走到右边的边缘,坐在最小的切口上。当遍历边时,你必须检查是否c[v][w] > f[v][w]。您可以到达的节点位于最小切割的左侧,其他节点位于右侧。

+0

您可以查看更多详情[here](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ctl=1331121392192&ved=0CC4QFjAA&url=http%3A%2F%2Fciteseerx.ist。 psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D6F1324E4CAF290676E3605F39901D1A4%3Fdoi%3D10.1.1.85.7307%26rep%3Drep1%26type%3DPDF&EI = tkxXT7v-EsrJrAeZwLXzCw&USG = AFQjCNHlUpzr2bHRgY9ecDnxpKDyRgp9Pw&SIG2 = 6P1qlsU54JAjBmMVScfd7Q) – 2012-03-07 11:58:52

+0

http://ezekiel.vancouver.wsu.edu/~ cs223/lectures/graphs/maxflow/maxflow.pdf – wcochran 2012-11-16 23:57:22

+0

注意:如果您不想自己实现算法。我会建议你不要,除非你只是想学习,然后使用JGraphT库。问题解决完美 - MaxFlow和MinCut都通过完美优雅的API交付给您。 – 99Sono 2017-11-29 01:23:05