Graph Algorithm — Bipartite Graph(BFS)

Rohith Vazhathody
4 min readApr 15, 2022

--

Bipartite Graph Coloring using BFS

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 from GFG : https://www.geeksforgeeks.org/bipartite-graph/

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.

Example

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

Walkthrough for a bipartite graph using BFS

2. Not a Bipartite Graph

Walkthrough for not a bipartite graph using BFS

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

Java Code for BFS Approach

Originally Published on :

Practice Problem

Github Link

--

--

Rohith Vazhathody

Software Engineer | Weekly articles | Interested in DSA, design | Writes about problem solving, algorithm explanation of my understanding and Java Codes.