## Class HopcroftKarp

• Object
• edu.princeton.cs.algs4.HopcroftKarp

• ```public class HopcroftKarp
extends Object```
The `HopcroftKarp` class represents a data type for computing a maximum (cardinality) matching and a minimum (cardinality) vertex cover in a bipartite graph. A bipartite graph in a graph whose vertices can be partitioned into two disjoint sets such that every edge has one endpoint in either set. A matching in a graph is a subset of its edges with no common vertices. A maximum matching is a matching with the maximum number of edges. A perfect matching is a matching which matches all vertices in the graph. A vertex cover in a graph is a subset of its vertices such that every edge is incident to at least one vertex. A minimum vertex cover is a vertex cover with the minimum number of vertices. By Konig's theorem, in any bipartite graph, the maximum number of edges in matching equals the minimum number of vertices in a vertex cover. The maximum matching problem in nonbipartite graphs is also important, but all known algorithms for this more general problem are substantially more complicated.

This implementation uses the Hopcroft-Karp algorithm. The order of growth of the running time in the worst case is (E + V) sqrt(V), where E is the number of edges and V is the number of vertices in the graph. It uses extra space (not including the graph) proportional to V.

See also `BipartiteMatching`, which solves the problem in O(E V) time using the alternating path algorithm and BipartiteMatchingToMaxflow, which solves the problem in O(E V) time via a reduction to the maxflow problem.

For additional documentation, see Section 6.5 Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
Constructor Description
`HopcroftKarp​(Graph G)`
Determines a maximum matching (and a minimum vertex cover) in a bipartite graph.
• ### Method Summary

All Methods
Modifier and Type Method Description
`boolean` `inMinVertexCover​(int v)`
Returns true if the specified vertex is in the minimum vertex cover computed by the algorithm.
`boolean` `isMatched​(int v)`
Returns true if the specified vertex is matched in the maximum matching computed by the algorithm.
`boolean` `isPerfect()`
Returns true if the graph contains a perfect matching.
`static void` `main​(String[] args)`
Unit tests the `HopcroftKarp` data type.
`int` `mate​(int v)`
Returns the vertex to which the specified vertex is matched in the maximum matching computed by the algorithm.
`int` `size()`
Returns the number of edges in any maximum matching.
• ### Methods inherited from class java.lang.Object

`clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### HopcroftKarp

`public HopcroftKarp​(Graph G)`
Determines a maximum matching (and a minimum vertex cover) in a bipartite graph.
Parameters:
`G` - the bipartite graph
Throws:
`IllegalArgumentException` - if `G` is not bipartite
• ### Method Detail

• #### mate

`public int mate​(int v)`
Returns the vertex to which the specified vertex is matched in the maximum matching computed by the algorithm.
Parameters:
`v` - the vertex
Returns:
the vertex to which vertex `v` is matched in the maximum matching; `-1` if the vertex is not matched
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### isMatched

`public boolean isMatched​(int v)`
Returns true if the specified vertex is matched in the maximum matching computed by the algorithm.
Parameters:
`v` - the vertex
Returns:
`true` if vertex `v` is matched in maximum matching; `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### size

`public int size()`
Returns the number of edges in any maximum matching.
Returns:
the number of edges in any maximum matching
• #### isPerfect

`public boolean isPerfect()`
Returns true if the graph contains a perfect matching. That is, the number of edges in a maximum matching is equal to one half of the number of vertices in the graph (so that every vertex is matched).
Returns:
`true` if the graph contains a perfect matching; `false` otherwise
• #### inMinVertexCover

`public boolean inMinVertexCover​(int v)`
Returns true if the specified vertex is in the minimum vertex cover computed by the algorithm.
Parameters:
`v` - the vertex
Returns:
`true` if vertex `v` is in the minimum vertex cover; `false` otherwise
Throws:
`IllegalArgumentException` - unless `0 <= v < V`
• #### main

`public static void main​(String[] args)`
Unit tests the `HopcroftKarp` data type. Takes three command-line arguments `V1`, `V2`, and `E`; creates a random bipartite graph with `V1` + `V2` vertices and `E` edges; computes a maximum matching and minimum vertex cover; and prints the results.
Parameters:
`args` - the command-line arguments