Bipartite Matching
Unit-capacity network from a source through left and right to a sink; each augmenting path is an alternating path.
Decision · step 2 of 8Maximum Flow: Bipartite matching by augmenting paths
Augmenting path L1 > R1: L1 is free and so is R1, a direct match.
What you will see
Two columns of vertices; an augmenting path flips matched and unmatched edges.
Cost
| Best | O(E) |
|---|---|
| Average | O(V * E) |
| Worst | O(V * E) |
| Space | O(V + E) |
Hopcroft-Karp achieves O(E sqrt(V)).
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.