Content deleted Content added
No edit summary |
|||
Line 1:
== Introduction ==
Line 23 ⟶ 22:
The Basic concept that the algorithm relies on is that if we have a matching N of size n, and P is the augmenting path relative to N, then the matching NΔP would have a size of n+1. Thus, since there would be no matching greater in size than the maximum matching, the maximum matching would not have an augmenting path.
Lets name the two sets in which G can be partitioned as U and V. The matching from U to V at any time is represented as the set M.
We also maintain a queue(last in first out datastructure) Q in our pseudo code.
''Pseudo Code''
Initialization:
M = null;
Start :
for u:U
for v:V such that (u,v) belongs to E
if v is not in M
{ add (u,v) to M
break; }
end for
end for
for all u:U not in M
if flag_inserted != true
{ insert u in Q
u.flag_inserted = true; }
end for
== References ==
| |||