在给定最大流量的情况下找到最小割口的算法 [英] Algorithm to find min cut given max flow

问题描述

谁能给我一个关于在图[V，E，c，s，t，f]中找到最小割的算法的想法，其中f [v] [w]是最大流量而c [v] [w ]是容量吗?

Can anyone give me an idea about the algorithm to find min cut in a graph (V,E,c,s,t,f) where f[v][w] is max flow and c[v][w] is capacity?

推荐答案

从源节点运行BFS或DFS.不能向右移动的边位于最小切割上.遍历边沿时，必须检查是否为c[v][w] > f[v][w].您可以到达的节点位于最小切割的左侧，其他节点位于右侧.

Run a BFS or DFS from the source node. The edges where you cannot go to the right, sits on the min cut. When traversing edges you have to check if c[v][w] > f[v][w]. The nodes you could reach lie on the left side of the min cut and other nodes are on the right side.

这篇关于在给定最大流量的情况下找到最小割口的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！