Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
2.1.
Sample Example
3.
Approach
3.1.
Algorithm
3.2.
Java Code
3.2.1.
Output
3.2.2.
Complexity analysis
4.
Frequently Asked Questions
4.1.
What is the purpose of a tree data structure? 
4.2.
Describe a self-balanced tree.
4.3.
How many colors can we use in a bipartite graph?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Maximum Bipartite Matching in Graph

Author Ashish Sharma
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

A graph is a non-linear data structure made up of vertices and edges. The vertices are also known as nodes, while the edges are lines or arcs that connect any two nodes in the network. A graph comprises vertices (V) and edges (E). We can define the Graph as G(E, V).

graph

This article will briefly discuss about graph data structure, bipartite matching, the bipartite Graph, examples, approach, how to solve maximum bipartite matching in graph problems, and its time and space complexity.

Also see: Application of graph data structure

Bipartite graph

A bipartite graph is one in which we can separate the V vertices into two distinct sets, V1 and V2, and each edge connects one vertex in V1 to one vertex in V2. Every vertex of V1 connects to every vertex of V2 in a full bipartite Graph.

Bipartite Matching

Bipartite Matching is Matching in a bipartite graph where each edge has unique endpoints, i.e., no two edges share the same endpoints. 

For example, suppose there are M employees and N works. Each employee is capable of performing some work. Each employee is assigned work during the matching process.

bipartite matching

Maximum Bipartite Matching

If we have M employees and N works, we assign the positions to the employees to get the most matching, which means we set the most employees to work. Once we find a maximum match, we will not add any further edges, and any edges added are no longer matching. In a given bipartite graph, there may be more than one maximum matching.

maximum bipartite matching

Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm states that if we are given a graph with a source and the target node, our task is to find the maximum possible flow in the Graph to reach from start to destination. Let's discuss an example of it.

ford-fulkerson algorithm

Problem statement

Given a bipartite graph, our task is to find the Maximum Bipartite Matching in Graph.

Sample Example

 Input

Input

Output

Output

In the above example, as you can see, all the employee nodes are connected to works that utilize the maximum matching of the Graph.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

🔺Make a source vertex and a target vertex.

🔺In the bipartite Graph, add the edges from the source vertex to all the vertices in one collection (for example, all employees).

🔺Add edges in the bipartite Graph from all the vertices of another set (all jobs) to the target vertex.

🔺Mark each edge's capacity as 1.

🔺The Max Flow - Ford-Fulkerson Algorithm can be used to solve the maximum bipartite matching.

🔺A bipartite network represented by an adjacency matrix, say adjMatrix[][], with jobs represented by rows and applicants represented by columns. If a employee x is capable of performing occupations a, b, and c, then adjMatrix[x][a]=1, adjMatrix[x][b]=1, and adjMatrix[x][c]=1, otherwise it is 0.

Algorithm

🔻Keep track of works allotted to employees by using an assign[] array. For example, assign[1]=2 indicates that we have assigned employee number 2 to work number 1.

🔻Each employee will keep a visited[] array to keep track of the work they have already applied for (to avoid going in loops).

🔻Conduct a Depth-First Search (DFS Algorithm) for each employee (to find work). Iterate through all of the work, one at a time.

🔻Check if the employee is qualified for this position and has never been considered for it (adjMatrix[applicant][job] == 1 && visited[job]==false), if so, mark visited[job]==true (employee is being considered for this work now and will not be considered again)

🔻If no other applicants are allocated to the position (assign[job]==-1) - assign the work to this employee.

🔻If we find the job assigned earlier to another employee, say 'X.' We make a recursive call for employee 'X' (perform another DFS) to see if we can assign another work to employee' X.' If this occurs, assign the position to the current employee, break the current loop 3a, and look for the next employee. And If we cannot give this work to this employee, we will look for the next available position.

Java Code

//  java program on how to solve maximum bipartite matching in graph 
import java.util.*;
public class Codingninjas4 {
   static class Graph {
       int works;
       int employees;
       int adjMatrix[][];
       public Graph(int employees, int works) {
           this.works = works;
           this.employees = employees;
           adjMatrix = new int[employees][works];
       }
       public void dowork(int employee, int work) {
           // add edge - means employee can do this work
           adjMatrix[employee][work] = 1;
       }
   }
   public int Matching(Graph graph) {
       int employees = graph.employees;
       int works = graph.works;
       int assign[] = new int[works]; // an array to track which work is assigned to which employee
       for (int i = 0; i < works; i++)
           assign[i] = -1; // initially set all works are available
       int workCount = 0;
       for (int employee = 0; employee < employees; employee++) { // for all employees
           // for each employee, all works will be not visited initially
         
             boolean visited[] = new boolean[works];
           // check if employee can get a work
           if (bipartiteMatch(graph, employee, visited, assign)) {
               // if yes then increase the work count
               workCount++;
           }
       }
       return workCount;
   }
   // boolean function to show how to solve maximum bipartite matching in graph
   boolean bipartiteMatch(Graph graph, int employee, boolean visited[], int assign[]) {
       // check each work for the employee
       for (int work = 0; work < graph.works; work++) {
           if (graph.adjMatrix[employee][work] == 1 && !visited[work]) {
               // mark as work is visited, means employee is considered for this work
               visited[work] = true;
              
                // now check if work was not assigned earlier - assign it to this employee
               // OR work was assigned earlier to some other employee 'X' earlier then
               // make recursive call for employee 'X' to check if some other work can be
               // assigned
               // so that this work can be assigned to current candidate.
             
                 int assignedemployee = assign[work];
               if (assignedemployee < 0 || bipartiteMatch(graph, assignedemployee, visited, assign)) {
                   assign[work] = employee; // assign work work to employee employee
                   return true;
               }
           }
       }
       return false;
   }
 
     // driven code to show how to solve maximum bipartite matching in graph
   public static void main(String[] args) {
    
          // Construct Graph with employees and works
       int employees = 6;
       int works = 6;
       Graph graph = new Graph(employees, works);
       Scanner sc = new Scanner(System.in);
       System.out.println("\nEnter the size ");
       int size = sc.nextInt();
       System.out.println("Enter the elements of the array");
       for (int i = 0; i < size; i++) {
           int x = sc.nextInt();
           int y = sc.nextInt();
           graph.dowork(x, y);
       }
       Codingninjas4 m = new Codingninjas4();
       System.out.println("Maximum number of employees that could" + " get works are: " + m.Matching(graph));
   }
}

 

Output

output

Complexity analysis

Time complexity

O(N), since we are using a loop with the size N to get the values from the user to find Maximum Bipartite Matching in Graph.

Space complexity

O(N), since N is the array's size that takes the input in the Graph to take the data from the user for each node.
Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

What is the purpose of a tree data structure? 

The primary purpose of tree data structure is to store hierarchical data, such as folder structure, organization structure, and XML/HTML. A binary Search Tree is a tree that allows you to quickly search, insert, and delete data that has been sorted. It also helps you to find the object that is nearest to you. Heap is a tree data structure that uses arrays to construct priority queues.

Describe a self-balanced tree.

When we perform insertion and deletion operations in a self-balanced binary search tree, it retains its height as minimal as possible.

To be self-balanced, a BST must constantly obey the BST rules, with the left subtree having lower-valued values and the right subtree having high-valued keys.

The use of two operations accomplishes this:

 right rotation

 left rotation

How many colors can we use in a bipartite graph?

A bipartite graph is conceivable if the Graph can be colored with two colors so that vertices in a set are all the same color. A cycle graph can be colored with two colors when the cycle graph has even cycles.

Conclusion

In this article, we have discussed the graph data structure, bipartite matching, the bipartite Graph, examples, approach, and how to solve maximum bipartite matching in graph problems, its time, and space complexity.

After reading about how to find the maximum bipartite matching in Graph, are you not feeling excited to read/explore more articles on the topic of Graph? Don't worry; Coding Ninjas has you covered. If you want to practice questions on the binary tree, then follow these links Introduction to Graphsprint all mother vertices in graphConstruct a graph from the size of the component of each nodeImplementation of graph in python, Fibonacci Series in Python

Refer to our Guided Path on Coding Ninjas Studio to increase your skills in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to check your Knowledge of coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Check if a Graph has a Cycle of Odd Length
Next article
Bidirectional Search in Graph
Live masterclass