Hopcroft–Karp algorithm: Difference between revisions

Revision as of 07:17, 11 October 2008

Revision as of 05:52, 12 October 2008

Line 120:

// DFS from p, avoiding previously visited vertices.

// Start at the last layer of BFS, and go backwards

// to layer 0.

// p: Is 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;

if (p.layer = 0) // layer 0 has free vertices.

return (p);

end if

// Consider only edges going one layer backwards.

for all (q,p):E such thats.t. (p.layer+1=q.layer)

// q is at an even layer

P= Get_Augmenting_Path(q);

if (q.layer = 0)

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)

return// Append (q, Pp); // Prepend q to the path found so far.

return (P, q, p);

end if

end for