Graph Algorithm — Bipartite Graph(DFS)

Bipartite DFS Graph Coloring

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 from GFG : https://www.geeksforgeeks.org/bipartite-graph/

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

DFS Walkthrough

2. Not a Bipartite Graph

DFS Walkthrough

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

Java Code

Originally Published on :

Graph Algorithm | LinkedIn

Practice Problem

Bipartite Graph | Practice | GeeksforGeeks

GitHub - Rohithv07/LeetCodeTopInterviewQuestions: Leetcode Top Interview questions discussed in…