AlgoScope

Bipartite Matching

Unit-capacity network from a source through left and right to a sink. Each augmenting path is an alternating path.

Network flow, algorithm, advanced
Augmenting path L1 to R1.sL1L2L3R1R2R3t
Augmenting path L1 to R1.sL1L2L3R1R2R3t

Maximum Flow: Bipartite matching by augmenting paths

Decision, step 2 of 8

Augmenting path L1 > R1: L1 is free and so is R1, a direct match.

How maximum flow works

Cost

Best
O(E)
Average
O(V * E)
Worst
O(V * E)
Space
O(V + E)

Hopcroft-Karp achieves O(E sqrt(V)).

Taught by the same lesson

Maximum Flow covers these too, in the same run.