Graph: Given a graph, check if it is bipartite or not – Using BSF

Problem Statement:

You are given a graph with the number of vertices and list of edges.

You need to check if the graph is bipartite or not.

A graph is considered as bipartite if the set of vertices can be divided into 2 disjoint sets, U and V, such that every edge that connect vertex in U to a vertex in V, there are no edges between vertices within the same set.

In simple terms, no 2 adjacent vertices has the same color.

In other words, a graph which can be colored using 2 colors such that no adjacent nodes have the same color.

A graph with no cycle is a bipartite graph.

A graph with cycle with even cycle length can be a bipartite graph.

A graph with odd cycle length can never be a bipartite graph.

Example:

Example 1:

Output: False

Here its not possible to color 2 nodes, because there exist a cycle of odd length. Because of this, there exist a adjacent nodes end up with same color

Example 2:

Output: True

The given graph can be colored in 2 colors, hence it is a bipartite graph

Solution 1: BSF

We will solve the problem with the help of BSF.

In this solution, we will traverse the graph by level and assign colors alternatively.

First initialize colors of all the vertices to -1

For that we pick any vertex and assign color 0.

Then for each vertices, color its uncolored neighbor with opposite color.

If the neighbor already has the same color as the current vertex, then return false.

else return true at the end.

Time Complexity: O(V + E)
Space Complexity: O(V)

Solution 2: DSF

We will solve the problem with the help of DSF.

In DSF we start from any vertex and recursively color the uncolored neighbors.

If we find a neighbor that has the same color as the current vertex then return false, else return true at the end of the result.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


bool dfs_helper(vector<vector<int>>& graph, vector<int>& colors, int node, int color) 
{
    if (colors[node] != 0) 
    {
        return colors[node] == color; 
    }

    colors[node] = color; // assign color

    for (int neighbor : graph[node]) 
    {
        if (!dfs_helper(graph, colors, neighbor, -color)) 
        {
            return false; 
        }
    }
    return true;
}



bool dfs_solution(vector<vector<int>>& graph) 
{
    int n = graph.size();
    vector<int> colors(n, 0); // 0 = uncolored, 1 = color A, -1 = color B

    for (int i = 0; i < n; i++) 
    {
        if (colors[i] == 0 && !dfs_helper(graph, colors, i, 1)) 
        {
            return false;
        }
    }
    return true;
}



bool bfs_solution(vector<vector<int>>& graph) 
{
	int n = graph.size();
	vector<int> color(n); // 0 = uncolored, 1 = color A, -1 = color 
	    
	queue<int> q; // queue, resusable for BFS    

	for (int i = 0; i < n; i++) 
	{
	  if (color[i]) continue; 
	  
	  color[i] = 1; 

	  for (q.push(i); !q.empty(); q.pop()) 
	  {
	    int cur = q.front();

	    for (int neighbor : graph[cur]) 
		{
	      if (!color[neighbor])
	      { 
	      		color[neighbor] = -color[cur]; q.push(neighbor); 
	      } 
		  
	      else if (color[neighbor] == color[cur]) 
	        return false; 
	    }        
	  }
	}

	return true;
}

int main() 
{

    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};

    if(bfs_solution(edges))
        cout << "true\n";
    else
        cout << "false\n";

	edges = {{0, 1}, {0, 2}, {1, 2}, {2, 3}};
    
    if(dfs_solution(edges))
        cout << "true\n";
    else
        cout << "false\n";
    

    return 0;
}

Output

false
false