Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a Bipartite Graph
3.
Types of Bipartite Graph
3.1.
Balanced Bipartite
3.2.
Complete Bipartite
4.
Properties of Bipartite Graphs
5.
Check if a Given Graph is Bipartite or Not
5.1.
Problem Statement
5.2.
Approach 
6.
Algorithm
7.
Dry Run
8.
Implementation
8.1.
Using DFS(Depth First Search)
8.2.
Complexity
8.2.1.
Constraints 
8.2.2.
Time Complexity
8.2.3.
Space Complexity
8.3.
Using BFS(Breadth First Search)
8.4.
Complexity Analysis
8.4.1.
Constraints 
8.5.
Output
9.
Limitations 
9.1.
Breadth First Search (BFS)
9.2.
Depth First Search (DFS)
10.
Applications of Bipartite Graphs
11.
Frequently Asked Questions
11.1.
What are graphs?
11.2.
What is a bipartite graph?
11.3.
Is a tree a bipartite graph?
11.4.
Can a bipartite graph contain a cycle of odd length?
11.5.
What is the chromatic number of bipartite graphs?
12.
Conclusion
Last Updated: Mar 27, 2024
Medium

Bipartite Graph

Author Ayushi Goyal
1 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Graphs are non-linear Data Structure composed of nodes and edges. There are different types of graphs like directed graphs, undirected graphs, Euler graphs, hamiltonian graphs, etc. One of them is a Bipartite graph

introduction

In this article, we will learn everything about Bipartite graphs in one of the simplest ways. We will start with a quick definition of bipartite graphs, their properties, and examples. Our primary focus will be to understand an algorithm to check whether a graph is bipartite, along with its analysis in terms of time and space complexity.

What is a Bipartite Graph

Bipartite graphs or Bi-graphs are a type of graph where all of the vertices are divided into two independent groups, U and V, such that each edge [u,v] in the graph connects a vertex u from set U and a vertex v from set V. In other words, none of the edges connects two vertices from the same set. 

Let's see an example of a bipartite graph

bipartite graph example

The above graph is undirected, in which every edge connects one vertex of blue color and the other vertex of green color. The two colors represent two different sets. For instance, see the edge [E, F]E is green while F is blue. Similarly, other edges also like [A, E][A, B], [E, H],[H, G],[G, C], [D, C], [B, C], etc.

We can also see the mapping below to get a clear picture as to why the above graph is an example of a bipartite graph - 

bipartite graph example

The two sets U and V in this graph are:

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

Types of Bipartite Graph

Balanced Bipartite

If both the sets of vertices in a bipartite graph have an equal number of vertices or, in other words, have equal cardinality, then the graph is called balanced bipartite.

Complete Bipartite

A bipartite graph is said to be complete if all the vertices in  set-1 are connected to every vertex of set-2. So, if set-1 has m vertices and set-2 has n vertices, then the total number of edges will be - m*n.

In the next section, let's see some of the properties of a bipartite graph.

Properties of Bipartite Graphs

  • All the bipartite graphs are 2-colorable, which means that using only two colors, every vertex of the bipartite graph can be assigned a color such that none of the adjacent nodes has the same color.
     
  • Every subgraph of a bipartite graph is also bipartite.
     
  • It does not have odd cycles. This is because a graph having a cycle of odd length is not 2-colorable, so it can't be bipartite.
     
  • In a bipartite graph with the sets of vertices, as set U and set V, the following always holds:
Sum of the degrees of all vertices in set U = Sum of the degrees of all vertices in set V 

Check if a Given Graph is Bipartite or Not

Problem Statement

Given a graph, check whether the graph is bipartite or not. Your function should return true if the given graph's vertices are divided into two independent groups, U and V, such that each edge [u,v] in the graph connects a vertex u from set U and a vertex v from set V

You are given a 2D vector or adjacency matrix edges which contains 0 and 1, where edges[i][j] = 1 denotes a bi-directional edge from i to j. A bi-directional edge implies that the graph is undirected.

Before moving on to the solution approach, please first try to solve the question here by yourself.

Approach 

We know that all the bipartite graphs are 2-colorable, which means that using only two colors, every vertex of the bipartite graph can be assigned a color such that none of the adjacent nodes has the same color.

Adjacent nodes - Two nodes connected by an edge in a graph are said to be adjacent to each other.

So, for a given graph, we will check if the graph is 2-colorable or not. If it is 2-colorable, then it is a bipartite graph; else, it is not bipartite. We will use both DFS Algorithm(Depth First Search) and BFS(Breadth First Search) to solve this problem.

Algorithm

Following are the steps of the algorithm:

  1. Assign a color (say green) to the source node.
  2. Assign a different color(say blue) to all of the neighbours of the source node.
  3. Iterate over all the neighbours and assign the color green to their neighbours.
  4. If, at any point in time, we encounter a neighbour node with the same color as the current node, the process stops because it means that the graph is not 2-colorable and is not bipartite.

Dry Run

Let’s understand the working before implementation using an example. The graph we are using for this example is displayed below:

graph representation

We will create an array of size = No of vertex and an empty queue. And assign all elements of that array as zero. In this example, the number of vertices = 5.

array and queue

We will start with vertex 0 and assign a color to it (say green). 

vertex 0 iteration

Check all its neighboring vertex and assign a color to them(say blue). 

assign color

After removing 0 from the queue, 1 is the first element, so we will visit all neighboring vertices of 1 and assign the opposite color if uncolored.

vertex 1 iteration

After removing 1 from the queue, 3 is at the top. But all neighboring vertices satisfy the condition of Bipartite Graph. So, no change will is made. After removing 3, vertex 2 will be checked. 

vertex 2 iteration

As the color of vertex 2 and 4 is the same, the loop will go to the else block and return false. So our graph is not a Bipartite graph. 

Implementation

Using DFS(Depth First Search)

The code to check if a given graph is bipartite or not using DFS is given below:

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

// Function to add nodes in graph
void storeNodes(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}
bool isBipartite(vector<int> edges[], int vtx, vector<bool>& searched, vector<int>& colors)
{
    // Start traversing nodes
    for (int i : edges[vtx]) 
    {
    	// Check if vertex i is searched before or not
    	if (searched[i] == false) 
    	{
    		// Mark vertex == searched
    		searched[i] = true;
    		colors[i] = !colors[vtx];
    		
    		// Check recursively for subtree
    		if (!isBipartite(edges, i, searched, colors))
    		return false;
    	}
    	
    	// Check if color is same then return false
    	else if (colors[i] == colors[vtx])
    	return false;
    }

// Otherwise graph is Bipartite
return true;
}

// Main Code
int main()
{
    int no_of_vertex = 5;
    
    // Declare adjacency list
    vector<int> edges[no_of_vertex];
    
    // Declare required arrays
    vector<bool> searched(no_of_vertex);
    vector<int> colors(no_of_vertex);
    
    // adding edges to the graph
    storeNodes(edges, 0,1);
    storeNodes(edges, 2,0);
    storeNodes(edges, 0,3);
    storeNodes(edges, 3,4);
    storeNodes(edges, 2,4);
    storeNodes(edges, 4,1);
    storeNodes(edges, 3,2);
    
    // Mark start vertex = searched and assign a color
    searched[0] = true;
    colors[0] = 0;
    
    bool result = isBipartite(edges, 1, searched, colors);
    if (result == true)
    cout << "The given graph is Bipartite.\n";
    else
    cout << "The given graph is not Bipartite.\n";
    
    return 0;
}

Complexity

Constraints 

The maximum number of nodes we can use are 10^8. 
 

Time Complexity

It is O(N), where ‘N’ is the number of nodes. As we are traversing all the nodes onces. So, for N number of nodes the number of traversals are also equal to N. Hence, the overall time complexity is O(N).
 

Space Complexity

It is O(N), where ‘N’ is the number of nodes. Since we are using an array to store the colour of each node and an array to store visited nodes for DFS traversal, so the overall space complexity will be O(N).

Using BFS(Breadth First Search)

The code to check if a graph is bipartite or not using BFS is given below:

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

bool isBipartite(vector<vector<int>> &graph)
{
    // N is total number of nodes in graph
    int n = graph.size(); 
    
    // initialize an array of size N with all 0 values
    vector<int> colors(n, 0); 
    
    // Create an empty queue for BFS traversal
    queue<int> q;
    
    // Loop over all the nodes one by one
    for (int i = 0; i < n; i++) 
    {
        // If color already assigned
        if (colors[i] == 1) 
        continue;
        
        // Assign color 1 to the node 
        colors[i] = 1; 
        
        // Push current node to the queue for bfs
        q.push(i);     
        
        while (!q.empty())
        {
            int temp = q.front();

            // Loop over all the neighbors of current node
            for (auto neighbor : graph[temp])
            {
                // Check if color is not assigned to the neighbor
                if (!colors[neighbor])
                {
                    // Assign an opposite color to the neighbors
                    colors[neighbor] = -colors[temp];
                    q.push(neighbor);
                }

                // If neighbor has the same color return false
                else if (colors[neighbor] == colors[temp])
                return false;
            }
            
            // Pop the front node from the queue
            q.pop(); 
        }
    }
    return true;
}

// Main code to test
int main()
{
    int no_of_vertex = 5;
    
    // Declare adjacency list
    vector<vector<int>> edges(no_of_vertex, vector<int>(no_of_vertex, 0)); 

    edges[0][1] = edges[1][0] = 1;
    edges[0][2] = edges[2][0] = 1;
    edges[0][3] = edges[3][0] = 1;
    edges[1][2] = edges[2][1] = 1;
    edges[1][4] = edges[4][1] = 1;
    edges[2][3] = edges[3][2] = 1;
    edges[2][4] = edges[4][2] = 1;

    // Construct adjacency list from adjacency matrix
    vector<vector<int>> graph(no_of_vertex, vector<int>());
    for (int i = 0; i < no_of_vertex; i++)
        for (int j = 0; j < no_of_vertex; j++)
            if (edges[i][j] == 1)
                graph[i].push_back(j);

    bool result = isBipartite(graph);
    if (result == true)
    cout << "The given graph is Bipartite.\n";
    
    else
    cout << "The given graph is not Bipartite.\n";
}

Complexity Analysis

Constraints 

The maximum number of nodes we can use are 10^5. 

Time Complexity 

It is O(N ^ 2), where ‘N’ is the number of nodes. As we have to color all the nodes present, and for each node, we have to traverse its neighbours. In the worst cases, there can be at most ‘N’ neighbours. Hence, the overall time complexity is O(N ^ 2).

Space Complexity 

It is O(N), where ‘N’ is the number of nodes. Since we are using an array to store the color of each node and a queue to do BFS, the overall space complexity will be O(N).

Output

output

Limitations 

Breadth First Search (BFS)

  • BFS traversal consumes a lot of time. As you can see above, the time complexity using BFS traversal is O(N ^2). 
  • Also, BFS traversal search for all the nodes present on the same level before moving on to the next. 

Depth First Search (DFS)

  • Due to recursion a lot of stack memory is used. 

Applications of Bipartite Graphs

  • Bipartite graphs are used for similarity ranking in search advertising and e-commerce.
  • They are used to predict the movie preferences of a person.
  • It is extensively used in coding theory. Bipartite graphs are used for decoding codewords. 
  • Bipartite graphs are also used to mathematically model real-world problems like big data, cloud computing, etc.

Frequently Asked Questions

What are graphs?

A graph is a non-linear data structure containing points called nodes and links between them called edges. 

What is a bipartite graph?

A graph whose vertices are divided into two independent groups, U and V, such that every edge connects a vertex in U to a vertex in V, is said to be bipartite.

Is a tree a bipartite graph?

Yes. Every tree is a bipartite graph.

Can a bipartite graph contain a cycle of odd length?

No. If a graph has a cycle of odd length, then it can’t be bipartite.

What is the chromatic number of bipartite graphs?

Since the bipartite graphs are 2-colorable, the chromatic number is 2.

Conclusion

In this article, we learnt all about bipartite graphs. We started with understanding which graphs can be called bipartite, and then we saw the properties of bipartite graphs. Finally, we landed upon the algorithm to check if a given graph is bipartite. We used BFS in the algorithm, saw its implementation in C++, and analyzed the algorithm in terms of space and time complexity. 

If you want to get confident about the various algorithms in graphs, do check out:

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Live masterclass