The idea: pair workers with jobs
A bipartite graph has two sides, here workers A–E and jobs 1–5, and every edge joins a worker to a job the worker can do. A matching is a set of edges with no shared vertex: each worker gets at most one job and each job at most one worker. A maximum matching has as many edges as possible; if every vertex is matched it is a perfect matching.
Greedy pairing gets stuck: once A takes job 1, a worker who can only do job 1 is out of luck. The fix is to let matched workers move. That idea, the augmenting path, drives every algorithm on this page.
Augmenting paths
An augmenting path starts at a free worker, ends at a free job, and alternates edges that are not in the matching with edges that are. It has one more unmatched edge than matched edges, so flipping it (matched ↔ unmatched) grows the matching by one. Berge's theorem: a matching is maximum exactly when no augmenting path is left.
Kuhn's algorithm: one DFS per worker
Take the workers one by one. A depth-first search tries the worker's jobs in order. A free job ends the search. A taken job asks its owner to move: the search continues from the owner, along the owner's other jobs. A job tried once in this search is marked seen and never tried again, so each search costs O(E) and the whole algorithm O(V·E).
On graph G1, workers A to D grab jobs 1 to 4 directly. Worker E only knows jobs 1 and 3, both taken, so the search pushes A from 1 to 2, B from 2 to 3, C from 3 to 4, and D from 4 to 5: the augmenting path E–1–A–2–B–3–C–4–D–5 has 9 edges and 10 vertices, and one flip moves four workers at once. (Demo: Kuhn on G1)
Hopcroft-Karp: many shortest paths per phase
Hopcroft-Karp works in phases. A BFS from all free workers at once labels each vertex with its distance d along alternating paths and stops at the first layer that contains a free job. A DFS then collects a maximal set of vertex-disjoint shortest augmenting paths, moving only from layer d to d+1, and all of them are flipped together. After each phase the shortest augmenting path is strictly longer, which limits the number of phases to about 2√V and the running time to O(E·√V).
On G3, phase 1 matches A–1, C–3 and E–5 (paths of 1 edge). Phase 2 finds two 3-edge paths, B–1–A–2 and D–3–C–4, that share no vertex, and flips both in one go. (Demo: Hopcroft-Karp on G3)
| algorithm | finds per round | time |
|---|---|---|
| Kuhn (DFS per worker) | one augmenting path | O(V·E) |
| Hopcroft-Karp | all disjoint shortest paths | O(E·√V) |
| max flow (Ford-Fulkerson) | one path in the flow network | O(V·E) with unit capacities |
| Hungarian (assignment) | paths on the zeros, then adjust | O(n³) |
When no perfect matching exists: König and Hall
How do we know a matching of 4 is the best? Collect the vertices Z that a free worker can reach by alternating paths. The workers outside Z plus the jobs inside Z form a vertex cover: every edge touches one of them. It has exactly as many vertices as the matching has edges, and every matching edge needs its own cover vertex, so no matching can be bigger (König's theorem: in a bipartite graph, maximum matching = minimum vertex cover).
The workers inside Z also break Hall's condition, which says every set of k workers must know at least k jobs. On G2, workers A and B both know only job 1, so one of them stays free. The page marks the cover in red. (Demo: G2 has no perfect matching)
Assignment with costs: the Hungarian algorithm
Now every worker can do every job, at a cost, and we want the perfect matching with the smallest total cost. The Hungarian algorithm (Kuhn 1955, after König and Egerváry) works on the cost matrix:
- Row reduction: subtract each row's minimum. Every assignment uses one cell per row, so every total drops by the same amount and the best assignment does not change.
- Column reduction: the same for columns. Now every row and column has a zero.
- Match on the zeros: the zeros form a bipartite graph (rows to columns). Find a maximum matching with augmenting paths. If it is perfect, those zeros are an optimal assignment.
- Cover and adjust: otherwise König gives as many lines (rows and columns) as the matching size that cover every zero. Let d be the smallest uncovered value. Subtract d from every uncovered cell and add d to every cell covered twice. A new zero appears, matched zeros stay zero, and no value goes negative. Go back to step 3.
On C1 the reductions already leave four independent zeros, total 13. (Demo: Hungarian C1) On C2 rows A and D both want column 4; three lines cover the zeros, d = 2 creates zeros at A3 and D2, and the path D–2–C–3 finishes the assignment A→4, B→1, C→3, D→2 with total 1 + 2 + 7 + 3 = 13. (Demo: Hungarian C2) C3 needs two adjust rounds and ends at total 8. (Demo: Hungarian C3)
Why it is optimal: the subtracted amounts add up to a lower bound on every assignment's cost (the dual "potentials" of each row and column), and the final assignment uses only zero cells, so it meets that bound.
How to read the animation
- Green nodes and thick green edges are matched; thick blue edges are the path being tried.
- seen next to a job: this search already tried it. d=: the Hopcroft-Karp BFS layer. cover in red: a König cover vertex.
- In the matrix, zeros are light blue, assigned zeros green, the current minimum orange, and cover lines red.
Bipartite matching is a special case of maximum flow: add a source joined to every worker and a sink joined from every job, all capacities 1. See Maximum Flow (Ford-Fulkerson / Edmonds-Karp); its augmenting paths in the residual graph are exactly the alternating paths here. The searches themselves are depth-first search (Kuhn) and breadth-first search (the Hopcroft-Karp layers).
What the page leaves out
Graphs have at most 5 vertices per side and cost matrices are 4×4, so everything fits on the canvas. The page leaves out weighted matching in general (non-bipartite) graphs (Edmonds' blossom algorithm), rectangular or maximisation cost matrices (pad with dummy rows, or negate the costs), the O(n³) version of the Hungarian algorithm with explicit row and column potentials, the auction algorithm, and online or stable matching (Gale-Shapley), which has preferences instead of costs.