Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is the topological sort?
3.2.
What is an Acyclic Graph?
3.3.
What is Depth First Search?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Hopcroft–Karp Algorithm for Maximum Matching

Author Ayush Mishra
1 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

A matching of a maximum number of edges is called Maximum Matching. If any edge is added to a maximum matching, it is no longer matching. A Bipartite Graph may have more than one maximum matching.

This blog will discuss the problem of finding the Maximum Matching using the Hopcroft-Karp Algorithm. We will discuss this article in detail. Let's start going!

Hopcroft–Karp Algorithm for Maximum Matching

Problem Statement

In this problem, we will take the Bipartite graph as input and find an augmented path. An augmented path is a path with free vertices as starting and ending points that alternates between matching and non-matching edges.

Let's look at the problem of finding the Maximum Matching using the Hopcroft-Karp Algorithm.

Sample Examples

Example 1:

Input:

1 1
1 3
2 3
3 4
4 3
4 2

Output:

 4

 

Explanation: 

Example1

In the above example, green edges show the maximum matching path.

Example 2:

Input:

2 3
3 1
1 2

Output: 

3

 

Explanation: 

Example2

In the above example, green edges show the maximum matching path.

Approach

We will first find the Augmented Path, an alternative path between matching and non-matching edges, and add it to the existing matching path, which makes the previous matching edges non-matching and non-matching as matching.

The basic idea to find the augmented path is Breadth First Search. BFS traversal divides the edges into matching and non-matching.

Algorithm

1️⃣ Set Maximal Matching M to be empty.

2️⃣ While an Augmenting Path p exists, remove the matching edges of p from M and add the not-matching edges of p to M.

3️⃣ Return M

Implementation

C++ Program to implement Hopcroft-Karp Algorithm for Maximum Matching:-

#include<bits/stdc++.h>
using namespace std;
#define NIL 0
#define INF INT_MAX

class Bipartite_Graph
{

  int n, m;
  list<int> *adj;
  int *pair_U, *pair_V, *dist;
  public:
 
   Bipartite_Graph(int m, int n);
   void add_Edge(int u, int v);
   bool bfs();
   bool dfs(int u);
   int hckalgo();
};

int Bipartite_Graph::hckalgo()
{
  pair_U = new int[m+1];
  pair_V = new int[n+1];
  dist = new int[m+1];

  for (int i=0; i<=m; i++)
  pair_U[i] = NIL;
  for (int j=0; j<=n; j++)
  pair_V[j] = NIL;
  int res = 0;

 while (bfs())
	{
		for (int u=1; u<=m; u++)
		if (pair_U[u]==NIL && dfs(u))
		res++;
	}
	return res;
}

bool Bipartite_Graph::dfs(int u)
	{
		if (u != NIL)
			{
				list<int>::iterator i;
				for (i=adj[u].begin(); i!=adj[u].end(); i++)
					{

						int v = *i;

						if (dist[pair_V[v]] == dist[u]+1)
							{
								if (dfs(pair_V[v]) == true)
									{
										pair_V[v] = u;
										pair_U[u] = v;
										return true;
									}
							}
					}

			dist[u] = INF;
			return false;
		}
	return true;
}
bool Bipartite_Graph::bfs()
{
queue<int> q; 
for (int u=1; u<=m; u++)
	{
		if (pair_U[u]==NIL)
			{
				dist[u] = 0;
				q.push(u);
			}
		else dist[u] = INF;
	}
dist[NIL] = INF;
while (!q.empty())
	{
	int u = q.front();
	q.pop();

	if (dist[u] < dist[NIL])
		{
			list<int>::iterator i;
			for (i=adj[u].begin(); i!=adj[u].end(); i++)
				{
					int v = *i;
					if (dist[pair_V[v]] == INF)
						{

							dist[pair_V[v]] = dist[u] + 1;
							q.push(pair_V[v]);
						}
				}
		}
	}
	return (dist[NIL] != INF);
}

// Constructor
Bipartite_Graph::Bipartite_Graph(int m, int n)
{
  this->m = m;
  this->n = n;
  adj = new list<int>[m+1];
}

void Bipartite_Graph::add_Edge(int u, int v)
{
  adj[u].push_back(v); 
}

// Driver Program
int main()
{
  Bipartite_Graph g(4, 4);
  g.add_Edge(1, 2);
  g.add_Edge(1, 3);
  g.add_Edge(2, 1);
  g.add_Edge(3, 2);
  g.add_Edge(4, 2);
  g.add_Edge(4, 4);
  cout << g.hckalgo();
  return 0;
}

 

Output:

 4

Time Complexity

The time complexity of the Hopcroft-Karp Algorithm for maximum matching is O(√V x E), where E is the number of Edges and V is the number of vertices.

Space Complexity

The space complexity of the Hopcroft-Karp Algorithm is O(V) as we are using extra space for storing u and v.

Check out this problem - Check If A String Is Palindrome

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

Frequently Asked Questions

What is the topological sort?

The topological sort algorithm takes a directed graph and returns an array of nodes in which each node appears before all of the nodes to which it points. A topological ordering is the arrangement of the nodes in an array.

What is an Acyclic Graph?

An acyclic graph is one that lacks cycles. We will never visit the same node twice if you follow the graph from node to node. If one or more of the tree branches are broken, the acyclic graph is referred to as a forest.

What is Depth First Search?

Depth-first search is a tree or graph traversal technique. Backtracking is used for traversal in this case. This traversal visits the deepest node first, then returns to its parent node if that node has no siblings.

Conclusion

Congratulations on finishing the blog! We have studied the Hopcroft-Karp Algorithm for Maximum Matching.

We hope this blog has helped you enhance your knowledge regarding the topic of Graph data structure, and if you want to learn more, then you can check articles on:-

1. Introduction to  Graph Theory

2. Depth First Search Problem

3. Breadth First Search (BFS)

4. Kadane's Algorithm

Please refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please do upvote our blogs if you find them helpful and informative!

Happy learning!

Thanking You
Previous article
Find the largest subset of Graph Vertices with Edges of 2 or more colors
Next article
Construct Binary Palindrome by Repeated Appending and Trimming
Live masterclass