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.
In the previous week, we discussed about Bipartite graph checking using BFS algorithm.

Lets try Depth-First Search algorithm.

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).

1. 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.

2. If the current node is not colored, color the current node with colourToBeColoured.

3. Traverse through the children of the current node.

4. Do dfs on the children.

5. 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

1. 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 color array, and an adjacency list for the graph. So the space complexity will be O(V) + O(V + E) + extra space for the recursion stack.

Code

Originally Published on : LinkedIn Newsletter

Practice Problem

Bipartite Graph

Github Link