Graph Theory37 sections · 1633 units
Open in Course

Finding the Min-Cut

Run BFS on final residual g...

After computing max flow, the residual graph reveals the min-cut. Run a BFS or DFS from the source on the residual graph. Let SS be the set of reachable nodes. Let TT be the remaining nodes. The edges from SS to TT form the min-cut.

These edges are saturated (flow equals capacity), so they have zero residual capacity. This gives you both the max flow value and the actual edges that form the bottleneck.