Hopcroft–Karp Algorithm for Maximum Matching

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!

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: 

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

Example 2:

Input:

2 3
3 1
1 2

Output: 

3

Explanation: 

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;
}

You can also try this code with Online C++ Compiler

Run Code

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