Introduction

The Hopcroft–Karp algorithm finds a maximum matching in a bipartite graph more efficiently than repeatedly searching for one augmenting path at a time. Its key idea is to use a breadth-first search to find the shortest augmenting-path layers and then a depth-first search to augment along many such paths in one phase.

Problem Setup

In a bipartite graph, vertices are split into two disjoint sets, often called U and V, and every edge goes from one side to the other. A matching is a set of edges with no shared endpoints. A maximum matching is the largest such set.

Hopcroft–Karp runs in O(E * sqrt(V)), which makes it a standard choice for large bipartite matching problems.

Data Representation in Python

A common Python representation is an adjacency list from left-side vertices to right-side vertices.

1graph = {
2    1: ["a", "b"],
3    2: ["a"],
4    3: ["b", "c"]
5}

The algorithm tracks which left nodes are matched to which right nodes and vice versa.

Python Implementation

Here is a compact implementation.

1from collections import deque
2
3
4def hopcroft_karp(graph):
5    U = list(graph.keys())
6    pair_u = {u: None for u in U}
7    pair_v = {}
8    dist = {}
9
10    for neighbors in graph.values():
11        for v in neighbors:
12            pair_v.setdefault(v, None)
13
14    def bfs():
15        queue = deque()
16        for u in U:
17            if pair_u[u] is None:
18                dist[u] = 0
19                queue.append(u)
20            else:
21                dist[u] = float("inf")
22
23        found = False
24        while queue:
25            u = queue.popleft()
26            for v in graph[u]:
27                matched_u = pair_v[v]
28                if matched_u is None:
29                    found = True
30                elif dist[matched_u] == float("inf"):
31                    dist[matched_u] = dist[u] + 1
32                    queue.append(matched_u)
33        return found
34
35    def dfs(u):
36        for v in graph[u]:
37            matched_u = pair_v[v]
38            if matched_u is None or (
39                dist[matched_u] == dist[u] + 1 and dfs(matched_u)
40            ):
41                pair_u[u] = v
42                pair_v[v] = u
43                return True
44
45        dist[u] = float("inf")
46        return False
47
48    matching = 0
49    while bfs():
50        for u in U:
51            if pair_u[u] is None and dfs(u):
52                matching += 1
53
54    return matching, pair_u
55
56
57graph = {
58    1: ["a", "b"],
59    2: ["a"],
60    3: ["b", "c"]
61}
62
63size, pairs = hopcroft_karp(graph)
64print(size)
65print(pairs)

Why BFS and DFS Both Matter

The BFS phase builds distance layers from unmatched left-side vertices. That identifies the shortest augmenting paths. The DFS phase then walks only through edges consistent with those layers, allowing multiple shortest augmenting paths to be applied in one round.

That batching behavior is why Hopcroft–Karp is faster than a naive “find one augmenting path, update, repeat” approach.

Reading the Output

The pair_u mapping tells you which right-side vertex each left-side vertex is matched to. Any entry with None means that vertex is unmatched in the final maximum matching.

Typical Use Cases

Hopcroft–Karp appears in problems such as:

• assigning workers to jobs
• matching students to projects
• pairing requests to resources
• solving scheduling and allocation problems on bipartite graphs

Whenever the problem structure is bipartite, this algorithm is worth considering.

Common Pitfalls

A common mistake is trying to apply Hopcroft–Karp to a general non-bipartite graph. It is specifically for bipartite matching. Another is mixing left-side and right-side identifiers in the same mapping without keeping the roles clear. Developers also often implement the DFS without respecting BFS layer distances, which breaks the algorithm’s efficiency advantage and can even break correctness.

Summary

• Hopcroft–Karp computes maximum matching in bipartite graphs.
• It combines BFS layering with DFS augmentation.
• The runtime is O(E * sqrt(V)), which is much better than simpler augmenting-path approaches on large graphs.
• Keep left-side and right-side match maps explicit in the implementation.
• Use it only when the graph is genuinely bipartite.