Hopcroft–Karp algorithm: Difference between revisions

Revision as of 21:20, 16 May 2022

Revision as of 03:02, 17 October 2022

Line 30:

* A [[breadth-first search]] partitions the vertices of the graph into layers. The free vertices in <math>U</math> are used as the starting vertices of this search and form the first layer of the partitioning. At the first level of the search, there are only unmatched edges, since the free vertices in <math>U</math> are by definition not adjacent to any matched edges. At subsequent levels of the search, the traversed edges are required to alternate between matched and unmatched. That is, when searching for successors from a vertex in <math>U</math>, only unmatched edges may be traversed, while from a vertex in <math>V</math> only matched edges may be traversed. The search terminates at the first layer <math>k</math> where one or more free vertices in <math>V</math> are reached.

* All free vertices in <math>V</math> at layer <math>k</math> are collected into a set <math>F</math>. That is, a vertex <math>v</math> is put into <math>F</math> if and only if it ends a shortest augmenting path.

* The algorithm finds a maximal set of ''vertex disjoint'' augmenting paths of length <math>k</math>. (''Maximal'' means that no more such paths can be added. This is different from finding the ''maximum'' number of such paths, which would be harder to do. Fortunately, it is sufficient here to find a maximal set of paths.) This set may be computed by [[depth -first search]] (DFS) from <math>F</math> to the free vertices in <math>U</math>, using the breadth first layering to guide the search: the DFS is only allowed to follow edges that lead to an unused vertex in the previous layer, and paths in the DFS tree must alternate between matched and unmatched edges. Once an augmenting path is found that involves one of the vertices in <math>F</math>, the DFS is continued from the next starting vertex. Any vertex encountered during the DFS can immediately be marked as used, since if there is no path from it to <math>U</math> at the current point in the DFS, then that vertex can't be used to reach <math>U</math> at any other point in the DFS. This ensures <math>O(|E|)</math> running time for the DFS. It is also possible to work in the other direction, from free vertices in <math>U</math> to those in <math>V</math>, which is the variant used in the pseudocode.

* Every one of the paths found in this way is used to enlarge <math>M</math>.

Line 36:

==Analysis==

Each phase consists of a single breadth first search and a single depth -first search. Thus, a single phase may be implemented in <math>O(|E|)</math> time.

Therefore, the first <math>\sqrt{|V|}</math> phases, in a graph with <math>|V|</math> vertices and <math>|E|</math> edges, take time <math>O(|E|\sqrt{|V|})</math>.