Maximum Bipartite Matching (Hopcroft-Karp)

Maximum Bipartite Matching asks: given applicants and jobs (or any two groups), pair up as many as possible with no conflicts. The naive augmenting-path method works, but Hopcroft-Karp is the fast classic — it pushes the matching with whole layers of shortest paths at once.

The slow way first

The textbook method is the augmenting-path algorithm (Hungarian / Kuhn): for each free left vertex, run a single DFS that tries to find an alternating path to a free job, flipping edges if it succeeds. Repeat until no vertex can be augmented. Each DFS costs O(E), and you run one per left vertex, so it is O(V · E).

The question to ask: can we find many augmenting paths in one sweep instead of one at a time? If we first compute the shortest augmenting-path length with a BFS, then push augmentations only along paths of that length, we make much faster progress.

The idea: BFS layers, then DFS augments

Each phase does two things. First, a BFS starts from all currently free left vertices and assigns layers along alternating edges (unmatched out of the left, matched out of the right). This finds the shortest distance to any free job. Second, a DFS augments along these layered shortest paths, flipping matched and unmatched edges. Repeat phases until a BFS finds no free-to-free path at all.

The key insight: an alternating path flips ownership when reversed. If a path runs free-left → job → its-current-applicant → another-job → ... → free-job, flipping every edge gives one more matched pair while keeping all the others valid.

Walk through it

Step through the animation. Phase 1 layers all three free left vertices and DFS grabs the two easy paths L1-R1 and L3-R2, leaving L2 stuck (its only job R1 is taken). Phase 2 runs BFS from L2 and DFS finds the longer alternating path L2 → R1 → L1 → R2 → L3 → R3, flips it, and now everyone is matched. The matching label climbs 0 → 1 → 2 → 3.

Pseudocode

matching = 0
repeat (one phase each loop):
    run BFS from every FREE left vertex along alternating edges
    if BFS reached no free right vertex:
        stop                       # no augmenting path -> done
    for each free left vertex u:
        if DFS(u) finds an augmenting path along the BFS layers:
            flip its edges
            matching = matching + 1
return matching

The Python solution

def hopcroft_karp(adj, n_left):
    match_l = [-1] * n_left          # left -> right
    match_r = {}                     # right -> left
    matching = 0
    while True:                      # one phase per loop
        # BFS: layer free left vertices, find shortest paths
        if not bfs(adj, match_l, match_r):
            break
        for u in range(n_left):      # DFS augment from each free left
            if match_l[u] == -1:
                if dfs(u, adj, match_l, match_r):
                    matching += 1    # path augmented, matching grew
    return matching

• match_l and match_r store the current pairing in both directions, so an edge is matched iff both ends agree.
• The while True loop is one phase per iteration.
• bfs(...) layers the free left vertices and returns False when no free right vertex is reachable — that is the stop condition.
• The inner for loop runs a dfs(...) augmentation from each free left vertex, all along the layers BFS just built.
• Every successful DFS flips one alternating path and bumps matching by one.

Complexity

The win comes from a theorem: there are only O(sqrt(V)) phases, and each phase is one BFS plus DFS over all edges, O(E). That gives the famous O(E · sqrt(V)) bound, much faster than O(V · E) on dense bipartite graphs.

When this pattern shows up

Practice