Program to check whether a given graph is Bipartite

In this article, we will explain how we can check if a given graph is bipartite or not in detail.

Basic Terminologies

  • Bipartite Graph: A simple graph G(V, E) is called Bipartite Graph if it’s vertices can be partitioned into two disjoint sets – V1 and V2, such that no edge connects vertices belonging to the same set ( or every edge in G connects a vertex in V1 and a vertex in V2).
Bipartite Graph

Algorithm

The algorithm to check if a graph is bipartite or not is based on the fact that each node in the graph must be in set V1 or V2. It cannot be in V1 and V2 simultaneously.

We will use the DFS algorithm to traverse the graph and assign set V1 or V2 to each vertex. Suppose we are currently on vertex a. a is assigned set V1. Let x be a vertex adjacent to a. We have two situations.

  • If x is not visited, then we will mark x as visited and assign x to set V2.
  • If x is already visited. Then we have to check if x belongs to set V1 or V2.
    • If x belongs to set V2 then there is no problem. We simply continue with the algorithm.
    • If x belongs to set V1 then there is a conflict. Vertex a and x are adjacent so they cannot be in same set. Therefore, the graph is not bipartite since we cannot divide the vertices in set V1 and V2 such that no adjacent vertices are in same set.

Program to check if a graph is bipartite using Depth First Search

Assumptions

  • The graph is undirected.
  • The graph contains no self-loops.
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

bool dfs(int v, vector<vector<int>>& adj, vector<int>& setNum) {

	bool isBipartite = true;

	for (auto u : adj[v])
	{
		// checking if u is assigned to any set or not
		if (setNum[u] == -1)
		{
			setNum[u] = 2 - (setNum[v] / 2); 	// the following statement put u to set 1 if v belongs to set 2
												// if v belongs to set 1 then it assigns set 2 to u

			isBipartite = isBipartite && dfs(u, adj, setNum);
		}
		else {

			// this statement is executed if u already belongs to a set
			// in this case, we need to check if u and v belongs to different set or not
			// if they belongs to different set then we simple move to next children of v
			// if they belongs to different set then the graph is not bipartite. We simple return false

			if (setNum[u] == setNum[v]) {
				return false;
			}

		}

	}

	return isBipartite;

}

bool checkIfGraphIsBipartite(vector<vector<int>>& adj, int n)
{

	vector<int> setNum(n, -1); 	// list to check to which set a node belongs to
								// -1 means the node is not assigned any set
								// 1 means the node belongs to set 1
								// 2 means the node belongs to set 2

	bool isBipartite = true;
	for (int i = 0; i < n; ++i)
	{
		if (setNum[i] == -1)
		{
			setNum[i] = 1; // putting vertex i in set 1
			isBipartite = isBipartite && dfs(i, adj, setNum);
		}
	}

	return isBipartite;

}

void addEdge(vector<vector<int>>& adj, int v, int u)
{
	adj[v].push_back(u);
	adj[u].push_back(v);
}

int main() {

	int n = 5; // number of vertices
	vector<vector<int>> adj(n);	 // adjacency list to store graph

	addEdge(adj, 0, 1);
	addEdge(adj, 2, 1);
	addEdge(adj, 3, 4);
	addEdge(adj, 2, 4);
	addEdge(adj, 1, 4);


	if (checkIfGraphIsBipartite(adj, n)) {
		cout << "Graph is Bipartite" << endl;
	}
	else {
		cout << "Graph is not Bipartite" << endl;
	}

}

Output

Graph is not Bipartite

--------------------------------

Program to check if a graph is bipartite using Breadth First Search

The logic is the same as in DFS. We will try to assign adjacent vertices to different sets. If we are able to partition the vertices into 2 sets, then the graph is bipartite otherwise the graph is not bipartite.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

bool bfs(int v, vector<vector<int>>& adj, vector<int>& setNum) {

	bool isBipartite = true;
	
	stack<int> s;
	s.push(v);
	
	while(!s.empty())
	{
		
		int p = s.top();
		s.pop();
		
		for (auto u : adj[p])
		{
			
			if (setNum[u] == -1)
			{
				setNum[u] = 2 - (setNum[p] / 2); 	// the following statement put u to set 1 if p belongs to set 2
													// if p belongs to set 1 then it assigns set 2 to u
	
				s.push(u);
			}
			else {
	
				// this statement is executed if u already belongs to a set
				// in this case, we need to check if u and p belongs to different set or not
				// if they belongs to different set then we simple move to next node in the stack
				// if they belongs to different set then the graph is not bipartite. We simple return false
	
				if (setNum[u] == setNum[p]) {
					return false;
				}
	
			}
			
		}
		
	}

	return isBipartite;

}

bool checkIfGraphIsBipartite(vector<vector<int>>& adj, int n)
{

	vector<int> setNum(n, -1); 	// list to check to which set a node belongs to
								// -1 means the node is not assigned any set
								// 1 means the node belongs to set 1
								// 2 means the node belongs to set 2

	bool isBipartite = true;
	for (int i = 0; i < n; ++i)
	{
		if (setNum[i] == -1)
		{
			setNum[i] = 1; // putting vertex i in set 1
			isBipartite = isBipartite && bfs(i, adj, setNum);
		}
	}

	return isBipartite;

}

void addEdge(vector<vector<int>>& adj, int v, int u)
{
	adj[v].push_back(u);
	adj[u].push_back(v);
}

int main() {

	int n = 5; // number of vertices
	vector<vector<int>> adj(n);	 // adjacency list to store graph

	addEdge(adj, 0, 1);
	addEdge(adj, 2, 1);
	addEdge(adj, 3, 4);
	addEdge(adj, 2, 4);
	addEdge(adj, 1, 4);


	if (checkIfGraphIsBipartite(adj, n)) {
		cout << "Graph is Bipartite" << endl;
	}
	else {
		cout << "Graph is not Bipartite" << endl;
	}

}

Output

Graph is not Bipartite

--------------------------------

Leave a Comment

Your email address will not be published. Required fields are marked *