Graph Algorithm - Bipartite Graph(BFS)
Tags: beginners, programming, tutorial, career
Published: 2022-04-03 12:14:01

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


![Bipartite](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wph4xbjhaoseesqzjqko.jpeg)

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


![Examples](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yhquy9vo0ledcwg1dgxy.png)

**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


![Bipartite Graph](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lheddqy254dyojae8929.gif)

2. Not a Bipartite Graph


![Not a bipartite](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3i7u3mn6mhwe9x18atj3.gif)

## 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


![Bipartite BFS Java Code](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ub4ey9mnz22zhxu87dz2.png)

Originally Published on : [LinkedIn Newsletter](https://www.linkedin.com/newsletters/graph-algorithm-6905161199672025088/)

## Practice Problem

[Bipartite Graph](https://practice.geeksforgeeks.org/problems/bipartite-graph/1/)

## Github Link

{% github https://github.com/Rohithv07/LeetCodeTopInterviewQuestions %}