Hopcroft-Karp bipartite matching: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

Hopcroft-Karp bipartite matching example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. 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
    }
  2. 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
    }
  3. 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
    }
  4. 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
    }
  5. 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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 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.