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 :