Skip to main content

Bipartite Matching

Learn Bipartite Matching (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.

Bipartite Matching A graph is bipartite when its vertices split into two sets, left and right , with edges only between the sets (workers and jobs, students and projects). A matching is a set of edges with no shared vertex , so each worker gets at most one job. Kuhn's algorithm finds a maximum matching: for each left vertex, search for an augmenting path that either takes a free right vertex or re-assigns the vertex that holds it. Cost: O(V·E) .

More lessons in Graphs