Last Updated: 30 Dec, 2020

# Bipartite Graph

Moderate

## Problem statement

#### Given an undirected graph of ‘V’ vertices (labeled 0,1,..., V-1) and ‘E’ edges . Your task is to check whether the graph is bipartite or not.

``````A bipartite graph is a graph whose vertices can be divided into two sets such that each edge of the graph connects one vertex from the first set and another vertex from the second set.
We can also define a bipartite graph as a graph which can be colored using two colors such that no two adjacent vertices have the same color.

For example:
Input:
4 4
0 1
0 2
1 3
2 3

An undirected graph to the above input is shown below:
``````

``````In the given input, the number of vertices is 4, and the number of edges is 4.
In the input, following the number of vertices and edges, a list of pairs of numbers is given where each pair (u, v) denotes an edge between vertex u and v.
As per the input, there is an edge between vertex 0 and vertex 1.
The vertices 0 and 2 have an edge between them.

The vertices 1 and 3 have an edge between them.
The vertices 2 and 3 have an edge between them.

As the graph can be colored using two colors, and no adjacent vertices share the same color, the graph is bipartite.
``````

#### Input format:

``````The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains two integers ‘V’ and ‘E’ denoting the number of vertices in the undirected graph and the number of edges in the undirected graph, respectively.
The next E lines contain two space-separated integers ‘u’, ‘v’, denoting two vertices connected by an edge.
``````

#### Output format:

``````For each test case, return “True” (without quotes) if the given graph is bipartite else return “False”.
The output of each test case is printed in a separate line.
``````

#### Note:

``````1.  There are no parallel edges i.e no two vertices are directly connected by more than 1 edge.
2.  The graph is necessarily undirected.
3.  You are not required to print the output explicitly, it has already been taken care of. Just implement the function that checks whether the given graph is bipartite or not.
``````
##### Constraints :
``````1 <= T <= 10
2 <= V <= 200
1 <= E <= V * (V - 1)/2
where ‘T’ is the number of test cases,  ‘V’ is the number of vertices, ‘E’ is the number of edges.
``````

## Approaches

### 01 Approach

The idea is very simple. To separate the vertices of the graph in two sets such that no two vertices of a set are connected, we will try to color the vertices of the graph using two colors only.

If any of the adjacent vertices are of the same color, the graph is not bipartite. Else, it is bipartite.

Note that, if there are more than 1 connected components in the graph, the graph will be bipartite if and only if all the connected components are bipartite.

Algorithm:

• We have the edges of the graph and we need to form an adjacency list from this given information. For this, make an adjacency list that will be storing the two nodes between which an edge exists.
• Create an integer array color of size ‘V’ to keep track of the color assigned the vertices. It can only contain 2 values, 0 or 1. 0 denotes ‘Green’ and 1 denotes ‘Yellow’ color.
• Create a boolean array of size ‘V’ to keep track of the already visited vertices.
• To include all the connected components of the graph, loop from 0 to V - 1:
• If the current vertex is not visited:
• Assign green color ( 0 )  to the current vertex.
• Mark the current vertex as visited and traverse its neighbors using the adjacency list and assign yellow color to them.
• Traverse the neighbor’s neighbor using depth first search and assign them a green color.
• Repeat this process until all the vertices are assigned a color.
• During this process, if a neighbor vertex is already visited and has the same color as the current vertex, terminate the process and return ‘False’ as the graph is not bipartite.
• If we have successfully colored the graph using 2 colors, return ‘True’ as the graph is bipartite.