Check if a Graph is Bipartite Using Depth-First Search (DFS)

Given an undirected graph represented as an adjacency list with V vertices (0-indexed), determine if the graph is bipartite.

A graph is bipartite if we can split the set of vertices into two groups such that no two adjacent vertices belong to the same group. This is equivalent to checking if the graph can be coloured using two colours without any two adjacent nodes having the same colour.

Understanding the Problem

A graph is said to be bipartite if its set of vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set. In simpler words, no two adjacent vertices should belong to the same group.

This concept often comes up in real-world scenarios like assigning tasks to two teams such that no conflicting tasks are handled by the same team.

We are given a graph and we have to check if it is bipartite or not. We’ll solve it using Depth-First Search (DFS), by trying to color the graph using two colors and checking for any coloring conflicts.

Step-by-Step Solution with Example

Step 1: Understand the Input Format

The graph is typically represented as an adjacency list. Each key in the list is a node, and its value is an array of nodes it is directly connected to. Example:

{
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
}

This graph has 4 nodes (0 to 3) and edges between them. We will now try to determine if this graph can be divided into two groups as per bipartite rules.

Step 2: Initialize Color Map

We will use a map or array to keep track of the color assigned to each node. Let’s say color 0 for one group, and 1 for the other.

Initially, no node is colored.

Step 3: DFS Traversal with Coloring

We start DFS traversal from any unvisited node (say node 0), assign it color 0, and then try to assign its neighbors the opposite color (1).

If at any point, a neighbor already has the same color as the current node, we conclude the graph is not bipartite.

Step 4: Continue for All Components

Since the graph may be disconnected, we need to repeat the DFS traversal from every unvisited node to ensure all components are checked.

Step 5: Example Walkthrough

Let’s walk through the example:

{
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
}

Start from node 0 → color it 0

→ visit node 1 → color it 1

→ visit node 2 from node 1 → color it 0

→ visit node 3 from node 2 → color it 1

→ back to node 0, already colored 0 → no conflict

→ visit node 2 from node 3 → already colored 0 → no conflict

All nodes visited without conflict. So this graph is bipartite.

Edge Cases

Case 1: Disconnected Graph

Always check all nodes, not just the first component. Use a loop to start DFS from each unvisited node.

Case 2: Odd-Length Cycle

If the graph contains an odd-length cycle, it cannot be bipartite. For example:

{
  0: [1, 2],
  1: [0, 2],
  2: [0, 1]
}

This is a triangle (3-cycle). You cannot color it with two colors without conflict. Hence, not bipartite.

Case 3: Empty Graph

A graph with no edges is trivially bipartite since no adjacent nodes exist to cause conflicts.

Case 4: Self-Loop

If a node has an edge to itself, the graph is automatically not bipartite, since a node would need to have two different colors.

Finally

Checking whether a graph is bipartite using DFS is a classic and intuitive algorithm. By coloring nodes alternately and validating the coloring rules, we can confidently determine the bipartiteness of a graph.

Always remember to handle disconnected components and edge cases like odd cycles and self-loops to ensure your solution is robust.

1. Create a color array of size V initialized with -1 (unvisited).
2. Define a recursive dfs function that takes current node and currentColor.
3. Color the node and for each of its neighbors:
1. If neighbor is not coloured, call dfs with opposite colour.
2. If already coloured and same as current node, return false.
4. If DFS completes without conflicts, return true.
5. Check each unvisited node to ensure disconnected components are handled.

O(V)

Explanation: We use a color array of size V and recursive call stack of maximum depth V in the worst case.