Open In App

Maximum Bipartite Matching

Last Updated : 01 Jun, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

A matching in a Bipartite Graph is a set of the edges chosen in such a way that no two edges share an endpoint. A maximum matching is a matching of maximum size (maximum number of edges). In a maximum matching, if any edge is added to it, it is no longer a matching. There can be more than one maximum matchings for a given Bipartite Graph. 

Why do we care? 
There are many real world problems that can be formed as Bipartite Matching. For example, consider the following problem:

There are M job applicants and N jobs. Each applicant has a subset of jobs that he/she is interested in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Find an assignment of jobs to applicants in such that as many applicants as possible get jobs.”

maximum_matching1

We strongly recommend to read the following post first. “Ford-Fulkerson Algorithm for Maximum Flow Problem”
Maximum Bipartite Matching and Max Flow Problem :

Maximum Bipartite Matching (MBP) problem can be solved by converting it into a flow network (See this video to know how did we arrive this conclusion). Following are the steps.
 

maximum_matching2

1) Build a Flow Network : There must be a source and sink in a flow network. So we add a source and add edges from source to all applicants. Similarly, add edges from all jobs to sink. The capacity of every edge is marked as 1 unit.

 

maximum_matching2

2) Find the maximum flow: We use Ford-Fulkerson algorithm to find the maximum flow in the flow network built in step 1. The maximum flow is actually the MBP we are looking for.

How to implement the above approach? 

Let us first define input and output forms. Input is in the form of Edmonds matrix which is a 2D array ‘bpGraph[M][N]’ with M rows (for M job applicants) and N columns (for N jobs). The value bpGraph[i][j] is 1 if i’th applicant is interested in j’th job, otherwise 0. 

Output is number maximum number of people that can get jobs. 

A simple way to implement this is to create a matrix that represents adjacency matrix representation of a directed graph with M+N+2 vertices. Call the fordFulkerson() for the matrix. This implementation requires O((M+N)*(M+N)) extra space. 

Extra space can be reduced and code can be simplified using the fact that the graph is bipartite and capacity of every edge is either 0 or 1. The idea is to use DFS traversal to find a job for an applicant (similar to augmenting path in Ford-Fulkerson). We call bpm() for every applicant, bpm() is the DFS based function that tries all possibilities to assign a job to the applicant.

In bpm(), we one by one try all jobs that an applicant ‘u’ is interested in until we find a job, or all jobs are tried without luck. For every job we try, we do following. 

If a job is not assigned to anybody, we simply assign it to the applicant and return true. If a job is assigned to somebody else say x, then we recursively check whether x can be assigned some other job. To make sure that x doesn’t get the same job again, we mark the job ‘v’ as seen before we make recursive call for x. If x can get other job, we change the applicant for job ‘v’ and return true. We use an array maxR[0..N-1] that stores the applicants assigned to different jobs.

If bmp() returns true, then it means that there is an augmenting path in flow network and 1 unit of flow is added to the result in maxBPM(). 

Recommended Practice

Implementation:

C++




// A C++ program to find maximal
// Bipartite matching.
#include <iostream>
#include <string.h>
using namespace std;
 
// M is number of applicants
// and N is number of jobs
#define M 6
#define N 6
 
// A DFS based recursive function
// that returns true if a matching
// for vertex u is possible
bool bpm(bool bpGraph[M][N], int u,
         bool seen[], int matchR[])
{
    // Try every job one by one
    for (int v = 0; v < N; v++)
    {
        // If applicant u is interested in
        // job v and v is not visited
        if (bpGraph[u][v] && !seen[v])
        {
            // Mark v as visited
            seen[v] = true;
 
            // If job 'v' is not assigned to an
            // applicant OR previously assigned
            // applicant for job v (which is matchR[v])
            // has an alternate job available.
            // Since v is marked as visited in
            // the above line, matchR[v] in the following
            // recursive call will not get job 'v' again
            if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
                                     seen, matchR))
            {
                matchR[v] = u;
                return true;
            }
        }
    }
    return false;
}
 
// Returns maximum number
// of matching from M to N
int maxBPM(bool bpGraph[M][N])
{
    // An array to keep track of the
    // applicants assigned to jobs.
    // The value of matchR[i] is the
    // applicant number assigned to job i,
    // the value -1 indicates nobody is
    // assigned.
    int matchR[N];
 
    // Initially all jobs are available
    memset(matchR, -1, sizeof(matchR));
 
    // Count of jobs assigned to applicants
    int result = 0;
    for (int u = 0; u < M; u++)
    {
        // Mark all jobs as not seen
        // for next applicant.
        bool seen[N];
        memset(seen, 0, sizeof(seen));
 
        // Find if the applicant 'u' can get a job
        if (bpm(bpGraph, u, seen, matchR))
            result++;
    }
    return result;
}
 
// Driver Code
int main()
{
    // Let us create a bpGraph
    // shown in the above example
    bool bpGraph[M][N] = {{0, 1, 1, 0, 0, 0},
                          {1, 0, 0, 1, 0, 0},
                          {0, 0, 1, 0, 0, 0},
                          {0, 0, 1, 1, 0, 0},
                          {0, 0, 0, 0, 0, 0},
                          {0, 0, 0, 0, 0, 1}};
 
    cout << "Maximum number of applicants that can get job is "
         << maxBPM(bpGraph);
 
    return 0;
}


Java




// A Java program to find maximal
// Bipartite matching.
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
    // M is number of applicants
    // and N is number of jobs
    static final int M = 6;
    static final int N = 6;
 
    // A DFS based recursive function that
    // returns true if a matching for
    // vertex u is possible
    boolean bpm(boolean bpGraph[][], int u,
                boolean seen[], int matchR[])
    {
        // Try every job one by one
        for (int v = 0; v < N; v++)
        {
            // If applicant u is interested
            // in job v and v is not visited
            if (bpGraph[u][v] && !seen[v])
            {
                 
                // Mark v as visited
                seen[v] = true;
 
                // If job 'v' is not assigned to
                // an applicant OR previously
                // assigned applicant for job v (which
                // is matchR[v]) has an alternate job available.
                // Since v is marked as visited in the
                // above line, matchR[v] in the following
                // recursive call will not get job 'v' again
                if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
                                         seen, matchR))
                {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
 
    // Returns maximum number
    // of matching from M to N
    int maxBPM(boolean bpGraph[][])
    {
        // An array to keep track of the
        // applicants assigned to jobs.
        // The value of matchR[i] is the
        // applicant number assigned to job i,
        // the value -1 indicates nobody is assigned.
        int matchR[] = new int[N];
 
        // Initially all jobs are available
        for(int i = 0; i < N; ++i)
            matchR[i] = -1;
 
        // Count of jobs assigned to applicants
        int result = 0;
        for (int u = 0; u < M; u++)
        {
            // Mark all jobs as not seen
            // for next applicant.
            boolean seen[] =new boolean[N] ;
            for(int i = 0; i < N; ++i)
                seen[i] = false;
 
            // Find if the applicant 'u' can get a job
            if (bpm(bpGraph, u, seen, matchR))
                result++;
        }
        return result;
    }
 
    // Driver Code
    public static void main (String[] args)
                       throws java.lang.Exception
    {
        // Let us create a bpGraph shown
        // in the above example
        boolean bpGraph[][] = new boolean[][]{
                              {false, true, true,
                               false, false, false},
                              {true, false, false,
                               true, false, false},
                              {false, false, true,
                               false, false, false},
                              {false, false, true,
                               true, false, false},
                              {false, false, false,
                               false, false, false},
                              {false, false, false,
                               false, false, true}};
        GFG m = new GFG();
        System.out.println( "Maximum number of applicants that can"+
                            " get job is "+m.maxBPM(bpGraph));
    }
}


Python3




# Python program to find
# maximal Bipartite matching.
 
class GFG:
    def __init__(self,graph):
         
        # residual graph
        self.graph = graph
        self.ppl = len(graph)
        self.jobs = len(graph[0])
 
    # A DFS based recursive function
    # that returns true if a matching
    # for vertex u is possible
    def bpm(self, u, matchR, seen):
 
        # Try every job one by one
        for v in range(self.jobs):
 
            # If applicant u is interested
            # in job v and v is not seen
            if self.graph[u][v] and seen[v] == False:
                 
                # Mark v as visited
                seen[v] = True
 
                '''If job 'v' is not assigned to
                   an applicant OR previously assigned
                   applicant for job v (which is matchR[v])
                   has an alternate job available.
                   Since v is marked as visited in the
                   above line, matchR[v]  in the following
                   recursive call will not get job 'v' again'''
                if matchR[v] == -1 or self.bpm(matchR[v],
                                               matchR, seen):
                    matchR[v] = u
                    return True
        return False
 
    # Returns maximum number of matching
    def maxBPM(self):
        '''An array to keep track of the
           applicants assigned to jobs.
           The value of matchR[i] is the
           applicant number assigned to job i,
           the value -1 indicates nobody is assigned.'''
        matchR = [-1] * self.jobs
         
        # Count of jobs assigned to applicants
        result = 0
        for i in range(self.ppl):
             
            # Mark all jobs as not seen for next applicant.
            seen = [False] * self.jobs
             
            # Find if the applicant 'u' can get a job
            if self.bpm(i, matchR, seen):
                result += 1
        return result
 
 
bpGraph =[[0, 1, 1, 0, 0, 0],
          [1, 0, 0, 1, 0, 0],
          [0, 0, 1, 0, 0, 0],
          [0, 0, 1, 1, 0, 0],
          [0, 0, 0, 0, 0, 0],
          [0, 0, 0, 0, 0, 1]]
 
g = GFG(bpGraph)
 
print ("Maximum number of applicants that can get job is %d " % g.maxBPM())
 
# This code is contributed by Neelam Yadav


C#




// A C# program to find maximal
// Bipartite matching.
using System;
 
class GFG
{
    // M is number of applicants
    // and N is number of jobs
    static int M = 6;
    static int N = 6;
 
    // A DFS based recursive function
    // that returns true if a matching
    // for vertex u is possible
    bool bpm(bool [,]bpGraph, int u,
             bool []seen, int []matchR)
    {
        // Try every job one by one
        for (int v = 0; v < N; v++)
        {
            // If applicant u is interested
            // in job v and v is not visited
            if (bpGraph[u, v] && !seen[v])
            {
                // Mark v as visited
                seen[v] = true;
 
                // If job 'v' is not assigned to
                // an applicant OR previously assigned
                // applicant for job v (which is matchR[v])
                // has an alternate job available.
                // Since v is marked as visited in the above
                // line, matchR[v] in the following recursive
                // call will not get job 'v' again
                if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
                                         seen, matchR))
                {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
 
    // Returns maximum number of
    // matching from M to N
    int maxBPM(bool [,]bpGraph)
    {
        // An array to keep track of the
        // applicants assigned to jobs.
        // The value of matchR[i] is the
        // applicant number assigned to job i,
        // the value -1 indicates nobody is assigned.
        int []matchR = new int[N];
 
        // Initially all jobs are available
        for(int i = 0; i < N; ++i)
            matchR[i] = -1;
 
        // Count of jobs assigned to applicants
        int result = 0;
        for (int u = 0; u < M; u++)
        {
            // Mark all jobs as not
            // seen for next applicant.
            bool []seen = new bool[N] ;
            for(int i = 0; i < N; ++i)
                seen[i] = false;
 
            // Find if the applicant
            // 'u' can get a job
            if (bpm(bpGraph, u, seen, matchR))
                result++;
        }
        return result;
    }
 
    // Driver Code
    public static void Main ()
    {
        // Let us create a bpGraph shown
        // in the above example
        bool [,]bpGraph = new bool[,]
                          {{false, true, true,
                            false, false, false},
                           {true, false, false,
                            true, false, false},
                           {false, false, true,
                            false, false, false},
                           {false, false, true,
                            true, false, false},
                           {false, false, false,
                            false, false, false},
                           {false, false, false,
                            false, false, true}};
        GFG m = new GFG();
    Console.Write( "Maximum number of applicants that can"+
                            " get job is "+m.maxBPM(bpGraph));
    }
}
 
//This code is contributed by nitin mittal.


PHP




<?php
// A PHP program to find maximal
// Bipartite matching.
 
// M is number of applicants
// and N is number of jobs
$M = 6;
$N = 6;
 
// A DFS based recursive function
// that returns true if a matching
// for vertex u is possible
function bpm($bpGraph, $u, &$seen, &$matchR)
{
    global $N;
     
    // Try every job one by one
    for ($v = 0; $v < $N; $v++)
    {
        // If applicant u is interested in
        // job v and v is not visited
        if ($bpGraph[$u][$v] && !$seen[$v])
        {
            // Mark v as visited
            $seen[$v] = true;
 
            // If job 'v' is not assigned to an
            // applicant OR previously assigned
            // applicant for job v (which is matchR[v])
            // has an alternate job available.
            // Since v is marked as visited in
            // the above line, matchR[v] in the following
            // recursive call will not get job 'v' again
            if ($matchR[$v] < 0 || bpm($bpGraph, $matchR[$v],
                                    $seen, $matchR))
            {
                $matchR[$v] = $u;
                return true;
            }
        }
    }
    return false;
}
 
// Returns maximum number
// of matching from M to N
function maxBPM($bpGraph)
{
    global $N,$M;
     
    // An array to keep track of the
    // applicants assigned to jobs.
    // The value of matchR[i] is the
    // applicant number assigned to job i,
    // the value -1 indicates nobody is
    // assigned.
    $matchR = array_fill(0, $N, -1);
 
    // Initially all jobs are available
 
    // Count of jobs assigned to applicants
    $result = 0;
    for ($u = 0; $u < $M; $u++)
    {
        // Mark all jobs as not seen
        // for next applicant.
        $seen=array_fill(0, $N, false);
 
        // Find if the applicant 'u' can get a job
        if (bpm($bpGraph, $u, $seen, $matchR))
            $result++;
    }
    return $result;
}
 
// Driver Code
 
// Let us create a bpGraph
// shown in the above example
$bpGraph = array(array(0, 1, 1, 0, 0, 0),
                    array(1, 0, 0, 1, 0, 0),
                    array(0, 0, 1, 0, 0, 0),
                    array(0, 0, 1, 1, 0, 0),
                    array(0, 0, 0, 0, 0, 0),
                    array(0, 0, 0, 0, 0, 1));
 
echo "Maximum number of applicants that can get job is ".maxBPM($bpGraph);
 
 
// This code is contributed by chadan_jnu
?>


Javascript




<script>
 
    // A JavaScript program to find maximal
    // Bipartite matching.
     
    // M is number of applicants
    // and N is number of jobs
    let M = 6;
    let N = 6;
   
    // A DFS based recursive function that
    // returns true if a matching for
    // vertex u is possible
    function bpm(bpGraph, u, seen, matchR)
    {
        // Try every job one by one
        for (let v = 0; v < N; v++)
        {
            // If applicant u is interested
            // in job v and v is not visited
            if (bpGraph[u][v] && !seen[v])
            {
                   
                // Mark v as visited
                seen[v] = true;
   
                // If job 'v' is not assigned to
                // an applicant OR previously
                // assigned applicant for job v (which
                // is matchR[v]) has an alternate job available.
                // Since v is marked as visited in the
                // above line, matchR[v] in the following
                // recursive call will not get job 'v' again
                if (matchR[v] < 0 || bpm(bpGraph, matchR[v],
                                         seen, matchR))
                {
                    matchR[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
   
    // Returns maximum number
    // of matching from M to N
    function maxBPM(bpGraph)
    {
        // An array to keep track of the
        // applicants assigned to jobs.
        // The value of matchR[i] is the
        // applicant number assigned to job i,
        // the value -1 indicates nobody is assigned.
        let matchR = new Array(N);
   
        // Initially all jobs are available
        for(let i = 0; i < N; ++i)
            matchR[i] = -1;
   
        // Count of jobs assigned to applicants
        let result = 0;
        for (let u = 0; u < M; u++)
        {
            // Mark all jobs as not seen
            // for next applicant.
            let seen =new Array(N);
            for(let i = 0; i < N; ++i)
                seen[i] = false;
   
            // Find if the applicant 'u' can get a job
            if (bpm(bpGraph, u, seen, matchR))
                result++;
        }
        return result;
    }
     
    // Let us create a bpGraph shown
    // in the above example
    let bpGraph = [
      [false, true, true,
        false, false, false],
          [true, false, false,
            true, false, false],
              [false, false, true,
                false, false, false],
                  [false, false, true,
                    true, false, false],
                      [false, false, false,
                        false, false, false],
                          [false, false, false,
                            false, false, true]];
     
    document.write( "Maximum number of applicants that can"+
                       " get job is "+ maxBPM(bpGraph));
   
</script>


Output

Maximum number of applicants that can get job is 5

Time Complexity: O(V*E)

The time complexity of the above algorithm is O(V*E) where V is the number of vertices in the graph and E is the number of edges. The algorithm iterates over each vertex in the graph and then performs a DFS on the corresponding edges to find the maximum bipartite matching.

Space Complexity: O(V + E)

The space complexity of this algorithm is O(V + E) as it uses a two-dimensional boolean array to store the graph and an array to store the maximum matching.

You may like to see below also: 
Hopcroft–Karp Algorithm for Maximum Matching | Set 1 (Introduction) 
Hopcroft–Karp Algorithm for Maximum Matching | Set 2 (Implementation)



Previous Article
Next Article

Similar Reads

Maximum number of edges in Bipartite graph
Given an integer N which represents the number of Vertices. The Task is to find the maximum number of edges possible in a Bipartite graph of N vertices.Bipartite Graph: A Bipartite graph is one which is having 2 sets of vertices.The set are such that the vertices in the same set will never share an edge between them. Examples: Input: N = 10 Output:
3 min read
Maximum number of edges to be added to a tree so that it stays a Bipartite graph
A tree is always a Bipartite Graph as we can always break into two disjoint sets with alternate levels. In other words we always color it with two colors such that alternate levels have same color. The task is to compute the maximum no. of edges that can be added to the tree so that it remains Bipartite Graph. Examples: Input : Tree edges as vertex
6 min read
Check if a given graph is Bipartite using DFS
Given a connected graph, check if the graph is bipartite or not. A bipartite graph is possible if the graph coloring is possible using two colors such that vertices in a set are colored with the same color. Note that it is possible to color a cycle graph with an even cycle using two colors. For example, see the following graph. It is not possible t
9 min read
Minimum Bipartite Groups
Given Adjacency List representation of graph of N vertices from 1 to N, the task is to count the minimum bipartite groups of the given graph. Examples: Input: N = 5 Below is the given graph with number of nodes is 5: Output: 3 Explanation: Possible groups satisfying the Bipartite property: [2, 5], [1, 3], [4] Below is the number of bipartite groups
8 min read
Divide given Graph into Bipartite sets
Given a graph G(V, E), divide it into two sets such that no two vertices in a set are connected directly. If not possible print "Not Possible". Examples: Input: V = 7, E = 6, Edge = {{1, 2}, {2, 3}, {3, 4}, {3, 6}, {5, 6}, {6, 7}}Output: 7 5 1 3 6 2 4 Explanation: node {7, 5, 1, 3} are not connected directly and nodes {6, 2, 4} are not connected di
10 min read
Maximize number of edges added to convert given Tree into a Bipartite Graph
Given a tree of N nodes, the task is to find the maximum number of edges that can be added to the tree such that it becomes a bipartite graph. Note: Self loop or multiple edges are not allowed but cycles are permitted. Examples: Input: N = 4, Edges = {{1, 2}, {2, 3}, {1, 4}} 1 / \ 2 4 / 3Output: 1Explanation: An edge between nodes 3 and 4 can be ad
13 min read
What is Bipartite Graph
A bipartite graph is a graph in which the vertices can be divided into two disjoint sets, such that no two vertices within the same set are adjacent. In other words, it is a graph in which every edge connects a vertex of one set to a vertex of the other set. An alternate definition: Formally, a graph G = (V, E) is bipartite if and only if its verte
3 min read
Check Whether a Linked List is Bipartite or Not
Given a linked list representing a graph with directed edges, check whether the given linked list is a Bipartite graph or not. Examples: Input: 1-&gt;2-&gt;3-&gt;4-&gt;NULLOutput: PossibleExplanation: It is possible to color the above linked list using 2 colors. We can color node 1 and 3 with one color and node 2 and 4 with other color. Input: 1-
8 min read
Check whether a given graph is Bipartite or not
A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U. In other words, for every edge (u, v), either u belongs to U and v to V, or u belongs to V and v to U. We can also say that there is no edge that connects vertices of
15+ min read
Bipartite Graphs in Python
Bipartite graphs are a special type of graph where the nodes can be divided into two distinct sets, with no edges connecting nodes within the same set. Every edge connects a node from the first set to a node in the second set. What is a Bipartite Graph?A graph where the nodes can be divided into two sets, V1 and V2, such that no edges connect nodes
5 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg