Do you think IIT Guwahati certified course can help you in your career?
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).
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.
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.
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.
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.
Problem statement
Given a bipartite graph, our task is to find the Maximum Bipartite Matching in Graph.
Sample Example
Input
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.
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));
}
}
You can also try this code with Online Java Compiler
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.
84+ registered