Java: Check if an undirected graph is bipartite or not.

Problem Statement: Given an undirected graph , return true if and only if it is bipartite.

A graph is bipartite if we can split its set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

Example:

In the above examples, graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1.

Code:

Explanation:

Above approach is the graph colouring using DFS.

Create an array of size equal to number of nodes and initialise all values with -1, which shows initially all the nodes are uncoloured.

To perform DFS, make use of a stack. Initially keep the start node in the stack and colour it. Use 0, 1, and so on to colour the nodes. Then iterate through all the adjacent nodes of the current node, if they are uncoloured, colour it with different colour and repeat the process for all the nodes.

If the colour of current node is same as the node adjacent to it, it means colouring is not possible and graph is not a bipartite graph.

Complexity Analysis:

Time Complexity: O(V+E), V is the number of nodes and E is the number of edges.

Space Complexity: O(V), array of size V to store the colour.

Github link to the solution: https://github.com/shivanidwivedi/JavaProgramming/commit/c03774df67f540304058cda1f0a70f713e57b437