[2] The algorithm was discovered by John Hopcroft and Richard Karp (1973) and independently by Alexander Karzanov (1973).

[3] As in previous methods for matching such as the Hungarian algorithm and the work of Edmonds (1965), the Hopcroft–Karp algorithm repeatedly increases the size of a partial matching by finding augmenting paths.

Finding an augmenting path allows us to increment the size of the partial matching, by simply toggling the edges of the augmenting path (putting in the partial matching those that were not, and vice versa).

Simpler algorithms for bipartite matching, such as the Ford–Fulkerson algorithm‚ find one augmenting path per iteration: the Hopcroft-Karp algorithm instead finds a maximal set of shortest augmenting paths, so as to ensure that only

can be achieved to find maximum-cardinality matchings in arbitrary graphs, with the more complicated algorithm of Micali and Vazirani.

An augmenting path could consist of only two vertices (both free) and single unmatched edge between them.

Thus, by finding augmenting paths, an algorithm may increase the size of the matching.

must form a collection of disjoint cycles, of paths with an equal number of matched and unmatched edges in

Now, the cycles and the paths with equal numbers of matched and unmatched vertices do not contribute to the difference in size between

If no augmenting path can be found, an algorithm may safely terminate, since in this case

The algorithm terminates when no more augmenting paths are found in the breadth first search part of one of the phases.

phases of the algorithm are complete, the shortest remaining augmenting path has at least

However, the symmetric difference of the eventual optimal matching and of the partial matching M found by the initial phases forms a collection of vertex-disjoint augmenting paths and alternating cycles.

In many instances, however, the time taken by the algorithm may be even faster than this worst case analysis indicates.

For instance, in the average case for sparse bipartite random graphs, Bast et al. (2006) (improving a previous result of Motwani 1994) showed that with high probability all non-optimal matchings have augmenting paths of logarithmic length.

) a more recent algorithm by Alt et al. (1991) achieves a slightly better time bound,

Several authors have performed experimental comparisons of bipartite matching algorithms.

Their results in general tend to show that the Hopcroft–Karp method is not as good in practice as it is in theory: it is outperformed both by simpler breadth-first and depth-first strategies for finding augmenting paths, and by push-relabel techniques.

[7] The same idea of finding a maximal set of shortest augmenting paths works also for finding maximum cardinality matchings in non-bipartite graphs, and for the same reasons the algorithms based on this idea take

However, for non-bipartite graphs, the task of finding the augmenting paths within each phase is more difficult.

Building on the work of several slower predecessors, Micali & Vazirani (1980) showed how to implement a phase in linear time, resulting in a non-bipartite matching algorithm with the same time bound as the Hopcroft–Karp algorithm for bipartite graphs.

The Micali–Vazirani technique is complex, and its authors did not provide full proofs of their results; subsequently, a "clear exposition" was published by Peterson & Loui (1988) and alternative methods were described by other authors.

If we reach an unmatched vertex of V, then we end at vDummy and the search for paths in the BFS terminate.

This guarantees that the paths considered in the BFS are of minimal length to connect unmatched vertices of U to unmatched vertices of V while always going back from V to U on edges that are currently part of the matching.

In particular, the special NIL vertex, which corresponds to vDummy, then gets assigned a finite distance, so the BFS function returns true iff some path has been found.

If BFS returns true, then we can go ahead and update the pairing for vertices on the minimal-length paths found from U to V: we do so using a depth-first search (DFS).

So we can explore with the DFS, making sure that the paths that we follow correspond to the distances computed in the BFS.

Note that the code ensures that all augmenting paths that we consider are vertex disjoint.

This is thanks to the following lines: When we were not able to find any shortest augmenting path from a vertex u, then the DFS marks vertex u by setting Dist[u] to infinity, so that these vertices are not visited again.

One last observation is that we actually don't need uDummy: its role is simply to put all unmatched vertices of U in the queue when we start the BFS.