Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 30 Dec, 2020

Moderate

```
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.
```

```
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.
```

```
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.
```

```
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.
```

```
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.
```

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.

- If the current vertex is not visited:
- 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.

The idea is the same as the previous approach, but we will be using breadth first search to traverse the graph.

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:
- Use a queue to perform BFS, and push the current vertex in the queue.
- Dequeue a vertex from the queue, say current vertex.
- Assign green color ( 0 ) to the current vertex.
- Mark the current vertex as visited and traverse its neighbors using the adjacency list.
- If the neighbor is not visited, push it into the queue and assign yellow color to it.
- If the neighbor of the current 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.

- Repeat this process until the queue is empty.

- Use a queue to perform BFS, and push the current vertex in the queue.
- If we have successfully colored the graph using 2 colors, return ‘True’ as the graph is bipartite.

A bipartite graph will never contain an odd cycle because if it contains an odd-cycle, we can not color the graph using 2 colors such that every adjacent vertex has different colors. Thus, we will check whether the graph contains an odd-cycle or not. If it does, it is not a bipartite graph.

How to check for an odd-cycle?

We will assign levels to each vertex, starting from level 0, 1, and so on…

Now, if a vertex and it’s neighbor have the same level, it means there exists an odd-cycle and the graph is not bipartite.

If the graph does not contain an odd-cycle, then we can color the odd level vertices with the first color and the even level vertices with the second color.

Note: If a vertex has a level ‘X’, then its adjacent vertices should have level ‘X’ + 1.

Let’s understand by some examples:

The graph shown below has 4 vertices and 4 edges. If we start with vertex 0, level of the vertex 0 will be 0, level of vertex 1, and vertex 3 will be 1 as they are adjacent to 0. Now, 2 is adjacent to 1 and 3. Thus, the level of 2 will be 2.

We can color even level vertices with green color and odd level vertices with yellow color. Thus, the graph is bipartite.

Now, consider the below graph. It has 5 vertices and 5 edges. If we start traversing the graph from vertex 0, level of vertex 0 will be 0, level of vertex 1, and vertex 3 will be 1 as they are adjacent to 0. Vertex 2 is adjacent to vertex 1, so the level of vertex 2 will be 2. Now, we will process vertex 3. Vertex 4 is adjacent to vertex 3, so the level of vertex 4 will be 2.

Clearly, the level of adjacent vertices 2 and 4 is the same. It means we can not color the graph using 2 colors only. Hence, the graph is not 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 ‘storeLevel’ of size ‘V’ to keep track of the level of the vertices.
- 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:
- Use a queue to perform BFS, and push the current vertex in the queue and set its level as 0.
- Dequeue a vertex from the queue, say current vertex.
- Mark the current vertex as visited and traverse its neighbors using the adjacency list.
- If the neighbor is not visited, set it’s level as the level of the current vertex + 1.

- Use a queue to perform BFS, and push the current vertex in the queue and set its level as 0.

Mark this neighbor as visited and push it to the queue.

- If the neighbor of the current vertex is already visited, and has the same level as the current vertex, terminate the process and return ‘False’ as the graph is not bipartite because it contains an odd cycle.
- Repeat this process until the queue is empty.
- If the graph does not contain any odd-cycle, return ‘True’ as the graph is bipartite.

Similar problems

Minimum Swaps To Make Identical Array

Moderate

Posted: 22 Jan, 2022

Find Center of Star Graph

Easy

Posted: 26 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

Critical Connections in a Network

Hard

Posted: 27 Jan, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022

Distance to a Cycle in Undirected Graph

Moderate

Posted: 7 Nov, 2022