Maximum bipartite matching
Picture
Workers A,B can do jobs X,Y. Each worker and job may appear in at most one chosen pair.
Predict
Why may an existing match need to move?
Walk through the small example
To open a job for another vertex. An alternating path can increase matching size by flipping chosen and unchosen edges.
Mental model and complete Python solution
An augmenting path is a chain of trades. Every matched participant along it gets a replacement, while the two free endpoints create one net additional pair.
What the function promises: Return a mapping from right vertices to matched left vertices. left_graph[u] lists eligible right labels 0..right_count−1.
def maximum_matching(left_graph, right_count):
matched_right = [-1] * right_count
def augment(left, seen):
for right in left_graph[left]:
if right in seen: continue
seen.add(right)
if matched_right[right] == -1 or augment(matched_right[right], seen):
matched_right[right] = left
return True
return False
for left in range(len(left_graph)):
augment(left, set())
return {right: left for right, left in enumerate(matched_right) if left != -1}
matching = maximum_matching([[0,1],[0]], 2)
assert len(matching) == 2 and set(matching.values()) == {0,1}
assert maximum_matching([[],[0]], 1) == {0:1}Work and storage: O(L·E) time for this DFS augmenting version and O(L+R) recursion/visited space.
When to recognize it: An alternating path can increase matching size by flipping chosen and unchosen edges.
Check before applying it: Greedily taking the first free neighbor can miss a larger matching.
Change one rule
The graph is large and sparse.
See what changes
Use Hopcroft–Karp to find many shortest augmenting paths per phase in O(E√V).
Connect
Bipartite graphs: alternate two colors: The graph’s two sides define eligible pairs.
Maximum flow: reroute through residual edges: Matching is unit-capacity flow from source through both sides.