Minimum Cut
The vertices still reachable in the final residual graph are S. The saturated edges leaving S sum to the max flow.
Maximum Flow: Min cut of the same network
BFS finds the shortest augmenting path 0 > 1 > 3 > 5, residual capacities 10, 5, 7. The bottleneck is 5.
Cost
- Space
- O(V + E)
Before this
Taught by the same lesson
Maximum Flow covers these too, in the same run.