Graph Algorithm — Bipartite Graph(DFS)
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.
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 Depth-First Search Algorithm
Algorithm
1. Initialize an integer colour array with all values 0. This colour array stores three values.0 means not colored and not visited, 1 means visited, and colored using colour 1, -1 means visited and colored using colour 2.
2. Run a loop from the start node to the end node, and start our DFS algorithm. (Useful for disconnected graph).
Our DFS function passes the following properties and do recursion. dfsFunction(graph, node, colourArray, colourToBeColoured).
3. Check if the current node is already colored. If already colored, return true only if colored with the same colour that needs to be colored. Else return false.
4. If the current node is not colored, color the current node with colourToBeColoured.
5. Traverse through the children of the current node.
6. Do dfs on the children.
7. If the method returns false in any of the recursion, two adjacent nodes are colored with the same color and the graph is not bipartite.
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 :