Course contentsShow
← Computer Science
Lesson 1047 of 2,87224. Minimum Spanning Trees and Network FlowFree lesson

Maximum Bipartite Matching Algorithm

Apply Ford-Fulkerson or similar algorithms to find maximum cardinality matchings in bipartite graphs.

Maximum Bipartite Matching Algorithm

What you'll learn: How to use network flow algorithms to find the largest possible matching in a bipartite graph.

The Core Idea

A bipartite graph has two distinct sets of vertices, where edges only connect vertices from different sets (think: jobs and applicants, students and courses). A matching is a set of edges with no shared vertices—each vertex is paired at most once. The maximum matching finds the largest such set.

Here's the beautiful insight: maximum bipartite matching is actually a maximum flow problem in disguise!

Converting Bipartite Matching to Max Flow

Transform your bipartite graph into a flow network:

  1. Add a source vertex connected to all vertices in the left set (capacity 1 each)
  2. Add a sink vertex connected from all vertices in the right set (capacity 1 each)
  3. Direct all original edges from left to right (capacity 1 each)
  4. Run Ford-Fulkerson (or Edmonds-Karp, Dinic's, etc.)

The maximum flow value equals the maximum matching size! Why? Each unit of flow represents one matched pair. The capacity-1 constraints ensure no vertex is used twice—exactly what matching requires.

Real-World Analogy

Imagine assigning jobs to applicants. Each applicant can do certain jobs, but each person gets only one job, and each job goes to only one person. Model this as a flow network where "one unit of flow" = "one assignment." The max flow finds the maximum number of successful assignments.

Extracting the Matching

After running max flow, examine edges between the left and right sets: any edge with flow = 1 is in your matching.

Key Takeaway: Maximum bipartite matching reduces perfectly to maximum flow—model it as a network with unit capacities, run any max flow algorithm, and the flow value gives you the matching size.