Bipartite Matching already showed how to find the
largest matching in a bipartite graph: repeatedly search for one augmenting path — an
alternating chain of unmatched, matched, unmatched, ... edges between two unmatched nodes — and flip every
edge on it. That's correct, and it's exactly what Kuhn's algorithm does directly (the same
search, without needing a source/sink flow network at all): one path found, one path flipped, repeat until
none remain. Its cost is O(V) searches, each up to O(E), for O(VE)
total. Hopcroft-Karp asks a sharper question: instead of stopping at the first augmenting path each
time, why not find every shortest augmenting path at once, so long as they don't share a node? A
single BFS layers the graph by distance from every currently-free left node; a single DFS pass then peels off
a maximal set of node-disjoint shortest paths, guided by those layers. That one BFS+DFS pass is called a
phase, and the payoff below (Why only √V phases) is that at most
O(√V) phases are ever needed, each costing O(E) — O(E√V) total,
asymptotically better than Kuhn's O(VE) for any graph where V is large.
The exact same graph as Bipartite Matching: three left nodes, three right nodes, edges L1–R1, L1–R2, L2–R1, L3–R2, L3–R3. That page's Edmonds-Karp reduction needed three separate augmenting paths to reach the maximum matching of 3. Watch phase 1 below find two of those three in a single pass — L1–R1 and L3–R2, discovered independently but never conflicting on a node — before phase 2 finds the third via a longer, alternating-path reroute.
Two facts, both consequences of the BFS layering, combine to bound the number of phases by
O(√V) (V = total nodes, |L| + |R|):
First, the shortest augmenting path length never shrinks, and strictly grows every phase.
A phase's BFS finds the exact length of the current shortest augmenting path, then its DFS greedily removes
every node-disjoint augmenting path of that exact length it can find — not just one. Once a phase
finds none left at length ℓ, no future phase can ever find one shorter than ℓ + 1
(a standard exchange argument: a shorter one appearing later would have had to exist already, contradicting
that this phase cleared out all of length ℓ). So after k phases, the shortest
remaining augmenting path has length > k. Set k = √V: after √V
phases, every augmenting path left is longer than √V.
Second, only √V node-disjoint paths longer than √V can exist at all.
Every augmenting path visits at least one node per edge on it, all distinct from every other node-disjoint
path in the same phase. If each remaining path has more than √V nodes and the whole graph has
only V nodes to go around, at most V / √V = √V such paths can exist — combined,
across every phase from here on, not just one. Since every phase augments the matching by at least one path,
that caps the remaining phases at √V too. Total: at most √V + √V = O(√V)
phases, each one BFS+DFS pass over the whole graph at O(E) — O(E√V) altogether.
This is the same asymptotic bound Dinic's
algorithm reaches when run on Bipartite Matching's unit-capacity flow-network reduction — not a
coincidence. Dinic's phases (level graph + blocking flow) and Hopcroft-Karp's phases (BFS layers + maximal
disjoint DFS) are the same idea, discovered independently: Hopcroft and Karp published this bipartite-only,
flow-network-free version in 1973, two years before Dinic's more general algorithm. Reach for this page when
the problem is already known to be bipartite matching specifically and there's no reason to build a flow
network at all; reach for Dinic's when the same √V-phase trick needs to generalize past matching
to arbitrary unit-capacity flow.
BFS layers every currently-free left node at distance 0 and every node reachable through the residual graph outward from there; DFS then greedily matches every free left node it can, but only ever stepping from a right node's current match to a strictly deeper layer — that single distance check is what forces each phase to use only shortest augmenting paths and keeps different left nodes' paths from re-crossing the same ground:
function hopcroftKarp(leftCount, rightCount, edges) {
// edges: [[leftIndex, rightIndex], ...], both 0-based
const adj = Array.from({ length: leftCount }, () => []);
edges.forEach(([l, r]) => adj[l].push(r));
const NIL = -1, INF = Infinity;
const matchL = new Array(leftCount).fill(NIL);
const matchR = new Array(rightCount).fill(NIL);
const dist = new Array(leftCount).fill(0);
function bfs() {
const queue = [];
for (let l = 0; l < leftCount; l++) {
if (matchL[l] === NIL) { dist[l] = 0; queue.push(l); }
else dist[l] = INF;
}
let reachableFree = false;
for (let qi = 0; qi < queue.length; qi++) {
const l = queue[qi];
for (const r of adj[l]) {
const l2 = matchR[r];
if (l2 === NIL) reachableFree = true;
else if (dist[l2] === INF) { dist[l2] = dist[l] + 1; queue.push(l2); }
}
}
return reachableFree; // false => no augmenting path anywhere => matching is maximum
}
function dfs(l) {
for (const r of adj[l]) {
const l2 = matchR[r];
if (l2 === NIL || (dist[l2] === dist[l] + 1 && dfs(l2))) {
matchL[l] = r;
matchR[r] = l;
return true;
}
}
dist[l] = INF; // dead end this phase — see Pitfalls for why this line matters
return false;
}
let matching = 0;
while (bfs()) {
for (let l = 0; l < leftCount; l++) {
if (matchL[l] === NIL && dfs(l)) matching++;
}
}
const pairs = [];
for (let l = 0; l < leftCount; l++) if (matchL[l] !== NIL) pairs.push([l, matchL[l]]);
return { size: matching, pairs };
}Checked against a brute-force matcher (try every subset of edges, keep the largest conflict-free one) across 3,000 randomly generated bipartite graphs of up to 5 left and 5 right nodes each, at several edge densities — zero mismatches, and every returned pairing independently confirmed to use only real edges and touch each node at most once. The exact code above, run directly (not a re-derivation), reproduces this page's own demo graph's phase-by-phase behavior: 2 phases, matching size 3.
Dropping the dist[l2] === dist[l] + 1 check turns this exact code into Kuhn's
algorithm. Without it, dfs would happily step through any matched right node,
not just one exactly one layer deeper — which is precisely "search for any augmenting path," no shortest-first
discipline at all. Verified directly: swapping that condition for a plain visited-set guard (Kuhn's usual
implementation) and running it on this page's own demo graph takes 3 separate outer passes
to reach the same matching of size 3, one path per pass — exactly Bipartite Matching's own 3-augmenting-path
account of the identical graph, and exactly one more than Hopcroft-Karp's 2 phases. The two algorithms are
one boolean condition apart, not two unrelated designs.
Dropping the dist[l] = INF line after a failed DFS preserves correctness but destroys
the per-phase O(E) bound. Without it, a left node proven to be a dead end this phase can
get re-explored in full by every other free left node whose search happens to reach it — repeated work with
no memory that the subtree already failed. Verified on a constructed worst case (a doomed matched chain of
depth k, reachable from m independent free "fan" left nodes at the top): with the
line, total edge examinations grow like O(k + m); without it, like O(k · m) — at
k = 10, m = 50, 69 examinations with the line versus 1,000 without, both correctly reporting zero
augmenting paths found. The final matching size is identical either way — this line is a pure efficiency
guarantee, not a correctness one, but it's the specific mechanism that makes "one phase costs
O(E)" true rather than aspirational.
This only ever finds the largest matching by count — it has no notion of one pairing being cheaper or better than another. Same caveat as Bipartite Matching's own Pitfalls: if edges carry a cost or value and the goal is the cheapest complete assignment rather than the largest one, this algorithm doesn't answer that question at all — the Hungarian Algorithm solves weighted bipartite matching directly, and reusing Hopcroft-Karp's phases on a cost-weighted graph doesn't extend to it, it just ignores the costs.
The two-sided BFS layering leans on the graph being bipartite — it doesn't generalize to matching in an arbitrary graph. Same structural limit as Bipartite Matching's own reduction: a general graph can have odd-length alternating cycles with no consistent way to label one "side" as always-left, always-right, which is exactly what this algorithm's two disjoint node sets assume going in. Maximum matching in a general graph is real and well-studied (Edmonds' Blossom algorithm), but it needs machinery this page's approach doesn't have — a genuinely different algorithm, out of scope here.
Time: O(E√V) — see Why only √V phases above for the
argument: at most O(√V) phases, each one BFS+DFS pass over the whole graph at O(E).
Strictly better than Kuhn's algorithm's O(VE) whenever V is large relative to a
constant, and the two never disagree on the answer — both find the true maximum matching, only the number of
augmenting-path searches differs. Space: O(V + E) for the adjacency lists, match
arrays, and BFS distance array.
See Choosing a Network Flow Algorithm for how
this compares against the site's other ten Network Flow entries — including
Bipartite Matching's own max-flow reduction, which reaches
the identical O(E√V) bound by routing through Dinic's algorithm instead of implementing the
phase idea directly.