# Graph Algorithm — Bipartite Graph(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.

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

## 2. 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 **: