## DEV Community is a community of 868,017 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. Rohith V

Posted on • Updated on

# 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. 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 Bipartite Graph