Bipartite Graph

Yukti Kumari
Last Updated: May 13, 2022

Introduction

We know that graphs are quite useful data structures that can simply solve many real-world problems. 

 

Graphs are non-linear data structures 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

 

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 main focus will be to understand an algorithm to check if a graph is bipartite or not, along with its analysis in terms of time and space complexity.

 

Following are the prerequisites you should know to understand bipartite graphs better - 

 

Before starting with this blog make sure you tick mark the prerequisite for better understanding. 

What is a Bipartite graph?

Bipartite graphs or Bi-graphs is a type of graph in which all of its vertices can be divided into two independent sets 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

 

 

The above graph is an undirected graph in which every edge connects one vertex of blue colour and the other vertex of green colour. The two colours 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 - 

 

 

The two sets U and V in this graph are:

  • Set U: {A,C,F,H}
  • Set V: {B,D,E,G}

 

Further, there are two types of bipartite graphs:

 

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.

 

Let’s see some of the properties of a bipartite graph in the next section.

Properties of Bipartite Graphs

  • All the bipartite graphs are 2-colourable which means that using only two colours, every vertex of the bipartite graph can be assigned a colour such that none of the adjacent nodes has the same colour.
  • 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-colourable 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 can be divided into two independent sets, and V, such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U.

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-colourable, which means that using only two colours, every vertex of the bipartite graph can be assigned a colour such that none of the adjacent nodes has the same colour.

 

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-colourable or not. If it is 2-colourable, then it is a bipartite graph; else it is not bipartite.

 

We will use BFS to solve this problem.

 

Following are the steps of the algorithm:

 

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

 

C++ Implementation

/* C++ code to check if a given graph is bipartite or not */
#include <bits/stdc++.h>
using namespace std;

bool isBipartite(vector<vector<int>> &graph)
{
    int n = graph.size();     //n is total number of nodes in graph
    vector<int> colors(n, 0); /*initialize it with 0 which implies color not assigned yet*/
    queue<int> q;             //for bfs

    for (int i = 0; i < n; i++) /*loop over all the nodes one by one*/
    {
        if (colors[i]) //if color already assigned
            continue;

        colors[i] = 1//assign color 1 to the node
        q.push(i);     //push current node to the queue for bfs

        while (!q.empty()) //bfs code
        {
            int temp = q.front();

            /*loop over all the neighbours of current node*/
            for (auto neighbor : graph[temp])
            {
                /*check if color is not assigned to the neighbour*/
                if (!colors[neighbor])
                {
                    // assign opposite color to the neighbours
                    colors[neighbor] = -colors[temp];
                    q.push(neighbor);
                }

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

// Main code to test the above implementation
int main()
{
    int n = 4;
    vector<vector<int>> edges(n, vector<int>(n, 0)); //adjacency matrix

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

    //construct adjacency list from adjacency matrix
    vector<vector<int>> graph(n, vector<int>());
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; 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";
    }
}

 

Output:

The given graph is Bipartite.

 

Time Complexity -

It is O(N ^ 2), where ‘N’ is the number of nodes.

As we have to colour 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 colour of each node and a queue to do BFS, the overall space complexity will be O(N).

 

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 model real-world problems like big data, cloud computing etc. mathematically.

Frequently Asked Questions

  1. What is a bipartite graph?
    A graph whose vertices can be divided into two independent sets U and V, such that every edge connects a vertex in U to a vertex in V is said to be bipartite.
     
  2. Is a tree a bipartite graph?
    Yes. Every tree is a bipartite graph.
     
  3. 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.
     
  4. What is the chromatic number of bipartite graphs?

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

 

Key Takeaways

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 Greedy Algorithms in Graph to learn all the important algorithms like Kruskal’s algorithm, Prim’s algorithm etc., on graphs in one place. 

Also, practice TOP GRAPHS INTERVIEW QUESTIONS from Codestudio to ace your technical interview.

 

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think