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

- Bipartite Graph

- 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

## Github Link

## Rohithv07 / LeetCodeTopInterviewQuestions

### Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions

# LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions-easy/

Also Question answered from CodeSignal.com : https://app.codesignal.com/

## Top comments (0)