Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Intuition
4.
Approach
4.1.
Implementation in C++ using BFS
4.2.
Implementation in Java
4.3.
Complexity Analysis
4.3.1.
Time Complexity: O(V + E)
4.3.2.
Space Complexity: O(V)
5.
Frequently Asked Questions
5.1.
What is a bipartite graph?
5.2.
How can we say if a graph is bipartite or not?
5.3.
What are the applications of bipartite graphs?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if Graph is Bipartite

Author Sonu Deo
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

When a graph's vertices can be separated into two distinct sets, every edge connecting two vertices from different sets is known as a bipartite graph (i.e., there are no edges that connect vertices from the same set). Typically, these sets are referred to as sides.

Check if a Graph is Bipartite

Problem Statement

We will be given an undirected graph, and we have to check if the given graph is bipartite, i.e., if we can divide all the vertices into two sets such that no two adjacent vertices are from the same set.

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

Intuition

First, let us consider an undirected graph without any cycles if we can have some useful results for it.

To check if this graph is bipartite or not, we will use colors (red and green) to denote two sets of vertices. In the given graph below, we can see that if we start our coloring from node 1 and color it red, then for all its adjacent vertices, we can use the color green, i.e., nodes 2, 3, 4, and 6 will be colored green. The same will follow for all the vertices with green color that adjacent vertices of it will be colored red.

With this result, we can see that any graph having no cycles can be divided into two sets (colors). Therefore, all graphs which don’t contain any cycle are bipartite.

graph without cycles

Now, we will focus on graphs having cycles of even length, i.e., all cycles in it must contain an even number of nodes.

Again we will be dividing the sets using colors. In the graph given below, the cycle length is 6, which is even. We will start our coloring from node 1, coloring it with red, then all of its adjacent nodes (2 and 6) will be colored green. Now for 2, its adjacent node, which is not colored yet, 3 will be colored red. Similarly, node 5 will be colored red, and now nodes 3 and 5 both will be coloring node 4 with green color. So we can see that for cycles of even length, we can start coloring from any node and end up coloring all the nodes without contradiction.

Therefore, we can say that a graph with cycles of even length only will be bipartite.

cycle of even length

Now consider an undirected graph having one or more cycles of odd length.

From the graph given below, we can see that if we start our coloring from node 3, its adjacent nodes (2 and 4) will be colored green, now node 2 will color its adjacent node 1 with red color, and 4 will color its adjacent node 5 with red color. Here we can see that node 5 and node 1 are having the same color and are also connected, which violates the condition of the bipartite graph. 

Therefore, any graph having one or more cycles of odd length will not be a bipartite graph.

cycle of odd length

Approach

According to a theorem, a graph is bipartite if and only if all of its cycles are the same length. In actuality, it is more practical to use the definition as follows: A graph is bipartite if and only if it is two-colorable. Here will be assigning sides to each vertex (1 and 2).

  • Starting from each vertex that hasn't been explored yet, let's perform a series of breadth-first searches. 
  • Assign the starting vertex of each search to side 1. 
  • We assign a vertex to the other side each time we visit a neighbor that hasn't yet been visited by one of its allotted sides. 
  • When attempting to reach a vertex assigned to one side that has already been visited, we first check to see if its neighbor has been assigned to the other side.
    • If it has, we deduce that the graph is not bipartite. 
    • Otherwise, the graph is bipartite, and we have successfully created its partitioning after we have visited every vertex and successfully allocated it to a side.

Implementation in C++ using BFS

#include <bits/stdc++.h>
using namespace std;


bool isBipartite(vector<vector<int>> graph){
    int nodes = graph.size();       //number on nodes in the graph
    vector<int> side(nodes, -1);    //initialising sides of each vertex with -1
    bool is_bipartite = true;       //let us assume that graph is bipartite
    queue<int> q;
    for (int st = 0; st < nodes; ++st)
    {
        if (side[st] == -1)         //only the nodes that has not been
                                    //colored yet will enter the queue
        {
            q.push(st);
            side[st] = 0;
            //giving the starting node with side 0
            //you can start with side 1 also
            while (!q.empty())
            {
                int par = q.front();
                q.pop();
                for (int child : graph[par])
                {
                    //for each child, we are checking if it is colored or not
                    //if colored and if it matches the parent color, then 
                    //we will make is_bipartite false
                    //else we will assign it with the side opposite to its parent 
                    if (side[child] == -1)
                    {
                        side[child] = 1 - side[par];
                        q.push(child);
                    }
                    else
                    {
                        if(side[child]==side[par]) is_bipartite = false;
                    }
                }
            }
        }
    }


    return is_bipartite;
}


int main(){
    vector<vector<int>> graph
    {
        {1, 2, 3},  //node 0 is connected with 1, 2 and 3
        {0, 2},     //node 1 is connected with 0 and 2
        {0, 1, 3},  //node 2 is connected with 0, 1 and 2
        {0, 2}      //node 3 is connected with 0 and 2
    };


    cout << (isBipartite(graph) ? "YES" : "NO") << endl;
}


Output:

NO

 

It means that the graph given is bipartite. Also, we can get the sides assigned to each vertex by just printing the vector side.

Implementation in Java

import java.util.*;

public class Main {

    static boolean isBipartite(int V, ArrayList<ArrayList<Integer>> adj) {
        // let's assume that graph is bipatite
        boolean is_bipartite = true;
        int side[] = new int[V];
        // initialise each side with -1
        Arrays.fill(side, -1);

        Queue<Integer> q = new LinkedList<Integer>();

        for (int i = 0; i < V; i++) {

            if (side[i] == -1) { // only the nodes that has not been
                                 // colored yet will enter the queue
                q.add(i);
                side[i] = 0;
                // giving the starting node with side 0
                // you can start with side 1 also
                while (!q.isEmpty()) {
                    int par = q.peek();
                    q.poll();

                    for (int child : adj.get(par)) {
                        // for each child, we are checking if it is colored or not
                        // if colored and if it matches the parent color, then
                        // we will make is_bipartite false
                        // else we will assign it with the side opposite to its parent
                        if (side[child] == side[par])
                            is_bipartite = false;

                        if (side[child] == -1) {
                            side[child] = (side[par] == 1) ? 0 : 1;
                            q.add(child);
                        }
                    }
                }
            }
        }

        return is_bipartite;
    }

    public static void main(String args[]) {

        int V;
        V = 4;

        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<Integer>());
        }

        // node 0 is connected with 1, 2 and 3
        adj.get(0).add(1);
        adj.get(0).add(2);
        adj.get(0).add(3);

        // node 1 is connected with 0 and 2
        adj.get(1).add(0);
        adj.get(1).add(2);

        // node 2 is connected with 0, 1 and 3
        adj.get(2).add(0);
        adj.get(2).add(1);
        adj.get(2).add(3);

        // node 3 is connected with 0 and 2
        adj.get(3).add(0);
        adj.get(3).add(2);

        boolean ans = isBipartite(V, adj);

        if (ans)
            System.out.println("YES");
        else
            System.out.println("NO");

    }
}


Output:

NO

Complexity Analysis

Time Complexity: O(V + E)

If we observe the traversal carefully, we have only visited each node once and each edge once. So, its time complexity is O(V+E). Where V is the number of vertices, and E is the number of edges in the graph.

Space Complexity: O(V)

We are using Queue for implementing BFS and a vector of side for storing the sides of each vertex. So, its space complexity is O(V), where V is the number of nodes.

Check out this problem - Queue Implementation

Frequently Asked Questions

What is a bipartite graph?

When a graph's vertices can be separated into two distinct sets, every edge connecting two vertices from different sets is known as a bipartite graph (i.e., there are no edges that connect vertices from the same set).

How can we say if a graph is bipartite or not?

To detect any bipartite graph, we have to ensure that the given graph doesn’t contain any cycle of odd length. E.g., any graph without cycles or graphs with cycles of even length only.

What are the applications of bipartite graphs?

Each edge connecting a vertex in one set to a vertex in the other can be used to partition a bipartite graph's vertices into two distinct sets. Users are defined for the AllElectronics user purchase data via a set of vertices with one user per vertice. For every vertex of the many set, a single product is defined. By linking the user to the product, an edge defines the user's purchase of the item.

Conclusion

In this article, we have discussed a coding problem to check if a graph is bipartite or not and its implementation in C++ and JAVA using Breadth-First-Algorithm with the help of a queue.

Solve more problems on Data Structures and Algorithms and enhance your knowledge with these interesting articles:

Depth-First-Search

Topological sort

Visit our website to read more such blogs. Make sure you enroll in the courses we provide, take mock tests, solve problems, and interview puzzles. Also, you can pay attention to interview stuff- interview experiences and an interview bundle for placement preparations.

Live masterclass