Content deleted Content added
→Algorithm: greater grammatical consistency |
→Algorithm: dfs also requires the paths to alternate |
||
Line 25:
* A [[breadth first search]] partitions the vertices of the graph into layers. The free vertices in ''U'' are used as the starting vertices of this search, and form the first layer of the partition. At the first level of the search, only unmatched edges may be traversed (since ''U'' is not adjacent to any matched edges); at subsequent levels of the search, restrict the traversed edges so that they alternate between unmatched and matched. Terminate the search at the first layer ''k'' where one or more free vertices in ''V'' are reached.
* All free vertices in ''V'' at layer ''k'' are collected into a set ''F''. That is, a vertex ''v'' is put into F if and only if it ends a shortest augmenting path.
* The algorithm finds a maximal set of ''vertex disjoint'' augmenting paths of length ''k''. This set may be computed by [[depth first search]] from ''F'' to the free vertices in ''U'', using the breadth first layering to guide the search: the depth first search is only allowed to follow edges that lead to an unused vertex in the previous layer, and paths in the depth first search tree must alternate between unmatched and matched edges. Once an augmenting path is found that involves one of the vertices in ''F'', the depth first search is continued from the next starting vertex.
* Every one of the paths found in this way is used to enlarge ''M''.
| |||