Hopcroft–Karp Bipartite Matching

John Hopcroft & Richard Karp, 1973

The 1973 Hopcroft–Karp algorithm keeps a matching of a bipartite graph and repeatedly discovers a maximal set of shortest augmenting paths. A layered breadth-first search from all unmatched left vertices builds the directed auxiliary network, and depth-first search inside each layer extracts vertex-disjoint augmentations. Coral traces the schematic augmenting walk in this exhibit while teal marks current matches and gold highlights the alternating BFS frontier.