|
Instead of finding just a single augmenting path, the algorithm finds a maximal set of shortest paths in each iteration <ref>{{cite web|author=Norbert Blum|title=A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in Nonbipartite Graphs|url=http://citeseer.ist.psu.edu/258961.html|date=1999}}</ref>. As a result only <math>O(\sqrt{V})</math> iterations are needed.
== Definition ==
Consider a graph G(V,E). The following definitions are relative to a matching M in G.
* A BFS is run from free U vertices. This BFS stops at layer ''k'' where one or more free V vertices are reached. Collect ''all'' free V vertices at layer ''k'' and put them in the set F. A vertex ''v'' is put in F iff <math> v\in V</math> and ''v'' ends a shortest augmenting path.
* Find a maximal set of ''vertex disjoint'' augmenting paths of length ''k''. This is set is computed by DFS from F (computed by BFS) to free U vertices. Every one of this paths is used to enlarge M.
''Pseudo Code''
for all <math>q\in U \cup V</math>
q.matching= null;
end for
while (true)
// Find all potential beginnings of shortest augmenting paths
B := empty;
for all u:U s.t. (u.matching = null)
insert u in B;
end for
// Find all endings of shortest augmenting paths
F := Find_Augmenting_Path_Endings(B);
if (F is empty)
M:= empty;
for all u:U s.t. (u.matching ≠ null)
insert (u, u.matching) in M; // insert edge
end for
return M;
end if
Augment_Paths(F);
end while
// Perform BFS starting with vertices of B.
// '''Return''': a list of free vertices which potentially
// end the shortest vertex-disjoint augmenting paths.
// '''Side effect''': For any vertex v.layer has the index of
// the BFS layer to reach this vertex (or -1)
// '''B''': potential beginning of augmenting paths
Find_Augmenting_Path_Endings(B):
Q := B;
// F: The set of free endings (the other side of augmenting paths)
F := empty;
for all <math>q\in U \cup V</math>
q.layer:=-1;
end for
// The potential beginnings of augmenting paths are at layer 0.
for all b:B
b.layer:=0;
end for
while (Q is not empty)
Q' := empty;
for all q: Q
for all (q,p):E s.t. (p.layer = -1)
p.layer:= q.layer+1;
if (p.matching = null)
insert p in F; // Collect the free vertex, continue BFS
else
insert p in Q';
end if
end for
end for
if (F is not empty)
return F; // Free vertices found, stop at this layer.
end if
Q:= empty;
for all q:Q'
// By construction, q matched.
p:= q.matching;
p.layer:= q.layer+1;
insert p in Q;
end for
end while
return empty;
Augment_Paths(F):
for all <math>q\in U \cup V</math>
q.visited= false;
end for
for all q:F
P:=Get_Augmenting_Path(q);
// Make sure q ends a ''vertex-disjoint'' augmenting path
if (P is not empty)
// Perform <math> M := M\oplus P </math>
for all (t,u):P
// Make (t,u) match all edges starting from the last layer
t.matching := u;
u.matching := t;
end for
end if
end for
// DFS from p, avoiding previously visited vertices.
// Start at the last layer of BFS, and go backwards
// to layer 0.
// '''Return''': List of edges on augmenting path. Returns only edges from
// even to odd layers.
// '''p''': Vertex at the end of a non-matching edge (an odd layer)
Get_Augmenting_Path(p):
if (p.visited OR p.layer = 0)
return empty;
end if
p.visited:= true;
// Consider only edges going one layer backwards.
for all (q,p):E s.t. (p.layer-1=q.layer AND NOT q.matching.visited)
// q is at an even layer
if (q.layer = 0)
// q is free vertex on the first layer
return ((q, p));
end if
// Note that q.matching must be defined, and point to
// the previous layer. This is due to BFS traversal order.
P= Get_Augmenting_Path(q.matching);
if (P not empty)
// Append (q, p) to the path found so far.
return (P, (q, p));
end if
end for
// Could not find a vertex-disjoint augmenting path ending with p.
return empty;
== References ==
<references/>
{{comp-sci-stub}}
[[Category:Graph algorithms]]
| 