I attached the code and screenshot of the output
Read section 10.3 of the text book.
DESCRIPTION: A graph is said to be bipartite if all its vertices can be
partitioned into two disjoint subsets X and Y so that every edge connects
a vertex in X with a vertex in Y.
Before calling MaximumBipartiteMatching(G)
printGraph(G)
//Finds a maximum matching in a bipartite graph by a BFS-like traversal
//Input: A bipartite graph G = Adjacenty Matrix
//Output: A maximum-cardinality matching M (array of (V,U) edges in the
input graph
MaximumBipartiteMatching(G)
initialize set M of edges with some valid matching (e.g., the empty set)
initialize queue Q with all the free vertices in V (in any order)
while not Empty(Q) do
printQueue(Q)
w←Front(Q); Dequeue(Q)
if w is an element of V
for every vertex u adjacent to w do
if u is free
//augment
M ←M ∪ (w, u)
v←w
while v is labeled do
u←vertex indicated by v’s label; M ←M − (v, u)
v←vertex indicated by u’s label; M ←M ∪ (v, u)
remove all vertex labels
reinitialize Q with all free vertices in V
break //exit the for loop
else //u is matched
if (w, u) is not an element of M and u is unlabeled
label u with w
Enqueue(Q, u)
else //w is and element of U (and matched)
label the mate v of w with w
Enqueue(Q, v)
printM(M)
return M //current matching is maximum
0 comments