Published by Dimitris Kougioumtzis · Updated
Build layers of shortest alternating paths, then augment a maximal set of those paths. Find a maximum matching in an unweighted bipartite graph.
BFS groups shortest alternating augmenting paths. Current-arc DFS finds a maximal collection of these paths in each phase, switching matched and unmatched edges along each successful path.
When to use Hopcroft-Karp bipartite matching
Maximum-cardinality assignment in unweighted bipartite graphs, such as eligibility-based task allocation.
Choosing an alternative
Stable marriage optimizes stability with preferences, not cardinality in a sparse eligibility graph. General maximum flow can model bipartite matching but does not exploit the same specialized phase structure.
Worked example: input and state changes
Example input
4 | 0,0;0,1;1,0;2,1;2,2;3,2;3,3
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: All vertices start unmatched.
State at this checkpoint
{ "values": [ "free", "free", "free", "free", "free", "free", "free", "free" ], "active": [], "kind": "graph", "bipartite": true, "partition": 4, "nodeLabels": [ "L0", "L1", "L2", "L3", "R0", "R1", "R2", "R3" ], "chosen": [], "visited": [], "partners": [ -1, -1, -1, -1 ], "result": 0 }Step 2: Augment an alternating path; matching size 1.
State at this checkpoint
{ "values": [ "R0", "free", "free", "free", "L0", "free", "free", "free" ], "active": [ 0, 4 ], "kind": "graph", "bipartite": true, "partition": 4, "nodeLabels": [ "L0", "L1", "L2", "L3", "R0", "R1", "R2", "R3" ], "chosen": [ 0 ], "visited": [ 0, 4 ], "partners": [ 0, -1, -1, -1 ], "result": 1 }Step 4: Augment an alternating path; matching size 3.
State at this checkpoint
{ "values": [ "R0", "free", "R1", "R2", "L0", "L2", "L3", "free" ], "active": [ 3, 6 ], "kind": "graph", "bipartite": true, "partition": 4, "nodeLabels": [ "L0", "L1", "L2", "L3", "R0", "R1", "R2", "R3" ], "chosen": [ 0, 3, 5 ], "visited": [ 0, 4, 2, 5, 3, 6 ], "partners": [ 0, -1, 1, 2 ], "result": 3 }Step 6: Augment an alternating path; matching size 4.
State at this checkpoint
{ "values": [ "R1", "R0", "R2", "R3", "L1", "L0", "L2", "L3" ], "active": [ 1, 4, 0, 5, 2, 6, 3, 7 ], "kind": "graph", "bipartite": true, "partition": 4, "nodeLabels": [ "L0", "L1", "L2", "L3", "R0", "R1", "R2", "R3" ], "chosen": [ 1, 2, 4, 6 ], "visited": [ 0, 5, 1, 4, 2, 6, 3, 7 ], "partners": [ 1, 0, 2, 3 ], "result": 4 }Step 8: Maximum matching size = 4.
State at this checkpoint
{ "values": [ "R1", "R0", "R2", "R3", "L1", "L0", "L2", "L3" ], "active": [], "kind": "graph", "bipartite": true, "partition": 4, "nodeLabels": [ "L0", "L1", "L2", "L3", "R0", "R1", "R2", "R3" ], "chosen": [ 1, 2, 4, 6 ], "visited": [ 0, 5, 1, 4, 2, 6, 3, 7 ], "partners": [ 1, 0, 2, 3 ], "result": 4 }
Expected final state
Maximum matching size = 4.
Complexity and input bounds
Family: Graphs. Time complexity: O(V^2 * sqrt(V)).
Implementation detail: The UI uses equal partitions with one to four vertices per side; isolated vertices allow smaller unequal partitions to be padded. Dense scanning gives O(V^2 * sqrt(V)) time rather than the adjacency-list O((V+E) * sqrt(V)) bound. Downloads return matching size and write left-to-right partners, with -1 for unmatched vertices.
Space complexity: O(V^2) auxiliary space for dense adjacency plus O(V) partner, layer, queue and DFS state; recorded frames use additional space.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Size per side (1..4) | left,right edge pairs separated by semicolons; indices 0..size-1; at most 16 edges. Empty edge list is allowed.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
A maximal matching need not be maximum. Distinguish the two sides even when both use indices 0..n-1. Duplicate edges do not create additional matching capacity.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | // Equal-sized bipartitions: size 1..4, 0..16 edges; from/to contain left/right indices 0..size-1. Duplicate edges are harmless. Returns maximum matching size; writes size left-to-right partners (-1 when unmatched). Output capacity at least size. Dense adjacency scans take O(V^2 * sqrt(V)) time and O(V^2) auxiliary space; adjacency-list Hopcroft-Karp takes O((V+E) * sqrt(V)). Different maximum matchings may exist. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(from, to, edges, size, output) { let adjacency = Array(256).fill(0); let left = Array(256).fill(0); let right = Array(256).fill(0); let level = Array(256).fill(0); let next = Array(256).fill(0); let queue = Array(256).fill(0); let stack = Array(256).fill(0); let selected = Array(256).fill(0); let result = 0; let head = 0; let tail = 0; let shortest = 0; let u = 0; let v = 0; let old = 0; let depth = 0; for (let i = 0; i < size; i++) { left[i] = -1; right[i] = -1; } for (let i = 0; i < edges; i++) { adjacency[from[i] * size + to[i]] = 1; } while (1 == 1) { head = 0; tail = 0; shortest = 1000000; for (u = 0; u < size; u++) { level[u] = 1000000; next[u] = 0; if (left[u] < 0) { level[u] = 0; queue[tail++] = u; } } while (head < tail) { u = queue[head++]; if (level[u] >= shortest) { continue; } for (v = 0; v < size; v++) { if (adjacency[u * size + v] != 0) { old = right[v]; if (old < 0) { shortest = level[u] + 1; } else if (level[old] == 1000000) { level[old] = level[u] + 1; queue[tail++] = old; } } } } if (shortest == 1000000) { break; } for (let root = 0; root < size; root++) { if (left[root] >= 0) { continue; } depth = 1; stack[0] = root; while (depth > 0) { u = stack[depth - 1]; v = next[u]; while (v < size && (adjacency[u * size + v] == 0 || (right[v] < 0 && level[u] + 1 != shortest) || (right[v] >= 0 && level[right[v]] != level[u] + 1))) { v++; } next[u] = v + 1; if (v == size) { level[u] = 1000000; depth--; continue; } selected[depth - 1] = v; if (right[v] < 0) { for (let i = depth - 1; i >= 0; i--) { left[stack[i]] = selected[i]; right[selected[i]] = stack[i]; } result++; break; } stack[depth++] = right[v]; } } } for (u = 0; u < size; u++) { output[u] = left[u]; } return result; } |
Source
Primary research source for the method. The playground uses a bounded dense-matrix teaching implementation; its guide states the resulting complexity separately from sparse adjacency-list variants.
- An n^(5/2) Algorithm for Maximum Matchings in Bipartite Graphs
John E. Hopcroft; Richard M. Karp (1973). Original research paper.