Overview
Hopcroft-Karp layers unmatched vertices with BFS, then uses DFS to find a maximal set of vertex-disjoint shortest augmenting paths.
CoreSource checked
Hopcroft-Karp
Finds maximum bipartite matching by augmenting many shortest paths per phase.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Graph Traversal
- Difficulty
- Advanced
- Family
- Bipartite Matching
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 3
- Formulas
- 1
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
bipartite graphaugmenting pathlayered searchmatching
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(E sqrt(V))
Average
O(E sqrt(V))
Worst
O(E sqrt(V))
Space
O(V + E)
When to Use
- Use when analyzing graph structure needs bipartite graph.
- Use when the input matches the assumptions behind bipartite Matching.
When Not to Use
- Avoid when the graph is so large that it needs streaming or external-memory handling.
- Avoid when a simpler algorithm gives the required result with less setup.
What It Does
- Finds maximum bipartite matching by augmenting many shortest paths per phase
- Uses bipartite graph and augmenting path to guide the work.
- Produces visited nodes.
Use Cases
- Analyzing graph structure
- Finding connectivity patterns
- Preparing graph-derived orderings
Inputs
- Graph
- Start nodes or query nodes
- Traversal state
Outputs
- Visited nodes
- Derived graph relationships
Key Formulas (1)
Matching augmentation
M = M xor paths
M = M xor pathsFlips matched and unmatched edges along all selected augmenting paths.
Pseudocode
- 1.Prepare the inputs and state needed for Hopcroft-Karp.
- 2.Apply the bipartite graph step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return visited nodes.
Canonical Example
- Input
- Hopcroft-Karp with a minimal inspectable input
- Output
- Visited nodes
- Explanation
- Hopcroft-Karp applies bipartite graph to produce visited nodes.
Implementation Notes
- Keep visitation state and edge classification state separate.
- Keep the bipartite graph step separate enough to test independently.
Common Pitfalls
- Mixing directed and undirected edge assumptions can produce incorrect graph relationships.
- Forgetting to check edge cases can make Hopcroft-Karp look correct on only ideal inputs.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationHighlight active nodes, discovered edges, and the graph structure produced by each step.
Step 1 of 4: Prepare the inputs and state needed for Hopcroft-Karp.
graph-traversal-mechanismNotes
Hopcroft-Karp should be used with the assumptions and tradeoffs of bipartite Matching in mind.
Sources (3)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Hopcroft-Karp's algorithm family, complexity framing, and standard implementation concepts.
Open sourceMatching Theory
BookReference for Hopcroft-Karp's graph matching model and augmenting-path or blossom-style concepts.
Hopcroft-Karp Bipartite Matching
PaperOriginal reference for finding maximum bipartite matchings by phases of shortest augmenting paths.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageHopcroft-Karp uses BFS layers to find groups of augmenting paths.
Conceptual neighborDinic's Algorithm
Both accelerate augmenting-path search with layered structure.
Related Algorithms
Tags
GraphMatchingBreadth First SearchDepth First Search