What is a Bipartite Graph

A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U.

Image is taken from GFG

In simple words, a graph is said to be a Bipartite Graph if we are able to colour the graph using 2 colours such that no adjacent nodes have the same colour.

If the graph has an odd length cycle, it is not a bipartite graph.

Two vertices of the same set will be connected, which contradicts the Bipartite definition saying there are two sets of vertices and no vertex will be connected with any other vertex of the same set.

If the graph has an even length cycle, it is said to be a bipartite graph.

Bipartite Graph Checking using Breadth-First Search Algorithm

Breadth-First Search is used to determine whether a graph is Bipartite or not a Bipartite graph.

Algorithm

• Initialize a queue, an integer colour array with all values 0. This colour array stores 3 values.0 means not colored and not visited, 1 means visited, and colored using colour 1, 2 means visited, and colored using colour 2.
• Run a loop from the start node to the end node, and start our BFS algorithm. (Useful for disconnected graph).
• Add the current node to the queue and colour the node with colour 1. Mark it inside the integer array.
• Until our queue is empty, do the following steps :
• Remove the top element from the queue.
• Traverse through all the adjacent nodes of the removed node.
• If the node is not colored, check the colour of the removed node. Colour the child node in such a way that colour[removed] = 1 means store colour[child] = 2 else colour[child] = 1. Add the child to the queue.
• If the node is already colored, make sure the colours of both the nodes are different.
• If the colour of the nodes is the same, return false indicating the graph is not bipartite.
• If our queue becomes empty, this indicates we can colour the graph using 2 colours such that no adjacent nodes have the same colour. Thus the graph is a Bipartite Graph.

Example

1. Bipartite Graph

1. Not a Bipartite Graph

Time and Space Complexity

• We are traversing through all the nodes and edges. So time complexity will be O(V + E) where V = vertices or node, E = edges.
• We use a coloured array, queue, and an adjacency list for the graph. So the space complexity will be O(V) + O(V) + O(V + E).

Code

Originally Published on : LinkedIn Newsletter

Practice Problem

Bipartite Graph

Github Link