Minimum Cut
The vertices still reachable in the final residual graph are S; the saturated edges leaving S sum to the max flow.
Decision · step 2 of 11Maximum 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.
What you will see
After max flow, vertices reachable in the residual graph are one side; crossing edges are the cut.
Cost
| Space | O(V + E) |
|---|
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input.
Screen readers: Edges announce capacity, flow and residual; each step announces the augmenting path and bottleneck.
Reduced motion: Flow labels update with a crossfade; the augmenting path is emphasized statically.
Before this
Taught by the same lesson
Maximum Flow covers these too, in the same run.