Check if a graph is bipartite or not in C++

In this tutorial, we will dive into the understanding of a graph and check whether a graph is bipartite or not in C++. For this, we first need to clearly understand a bipartite graph.

A bipartite graph is a graph in which vertices are divided into a set of vertices that satisfies the condition that every vertice is only connected to vertices from the other set, not with the vertices in the same set.

We can represent it as-

Check if a graph is bipartite or not in C++

As we can see in the above image there are no two edges from and to the vertice of the same set.

A bipartite graph can be checked using a breadth-first search algorithm in a graph using two-way coloring as-

  1. Color the source vertex as red.
  2. Color the neighboring vertex of the red vertex blue.
  3. Now again try coloring the neighbors of the blue vertex as red.
  4. Color all the vertices of the graph in a similar manner.
  5. If it is possible to color all the vertices of the graph, return True otherwise False.

Algorithm to check if a graph is bipartite or not-

We are trying to build an algorithm that works well for a connected as well as a disconnected graph. So we will take an adjacency matrix which will represent our graph and will be named G. Create a function called isgraphbipartite() which takes G as a parameter. Inside this function, we will create an array of vertex, in which every element will be initially -1 meaning that there is no color on that particular vertex, 1 denotes the first color say red, and 2 denotes the second color say blue. We will check for every vertex and if it is not colored, we will call a function named as isgraphbipartitefunc() which will take G, vertex, and an array of the vertex as parameters.

When isgraphbipartitefunc() function is invoked, the flow of data is-

  1. Color the source vertex as the first color, say red.
  2. Creating an empty queue and putting the source vertex as its element(enqueue).
  3. Run the loop until the queue is empty.
  4. Move the front element of the queue into u and remove it from the queue(dequeue).
  5. Check for a self-loop.
  6. For every adjacent vertex, check if an edge exists from u to v and if the destination vertex is not colored.
  7. Color the destination vertex opposite to that of the source vertex.
  8. Push v into the queue.
  9. Check if the destination vertex has a similar color to that of the source vertex, if yes return False.
  10. If not, then the adjacent matrix is colored with alternate colors.
#include <bits/stdc++.h>

using namespace std;

const int V = 4;


bool isgraphBipartitefunc(int G[][V], int src, int colorofvertex[])
{
  colorofvertex[src] = 1;

  queue<int> q;
  q.push(src);


  while (!q.empty()) {

    int u = q.front();
    q.pop();


    if (G[u][u] == 1)
      return false;


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

      if (G[u][v] && colorofvertex[v] == -1) {

        colorofvertex[v] = 1 - colorofvertex[u];
        q.push(v);
      }


      else if (G[u][v] && colorofvertex[v] == colorofvertex[u])
        return false;
    }
  }


  return true;
}


bool isgraphBipartite(int G[][V])
{

  int colorofvertex[V];
  for (int i = 0; i < V; ++i)
    colorofvertex[i] = -1;


  for (int i = 0; i < V; i++)
    if (colorofvertex[i] == -1)
      if (isgraphBipartitefunc(G, i, colorofvertex) == false)
        return false;

  return true;
}


int main()
{
  int G[][V] = { { 0, 1, 0, 1 },
        { 1, 0, 1, 0 },
        { 0, 1, 0, 1 },
        { 1, 0, 1, 0 } };

  isgraphBipartite(G) ? cout << "True" : cout << "False";
  return 0;
}

Output-

True

So here we have completed the task to check if a graph is Bipartite or not. Hope you liked it! Thanks for reading!

Leave a Reply

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