Bipartite Graph

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.

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

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.