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

Problem Statement❯

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.

Examples❯

Adjacency List	Is Bipartite?	Description
{ 0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2] }	Yes	Even cycle, can be coloured using two colours
{ 0: [1, 2], 1: [0, 2], 2: [0, 1] }	No	Triangle, odd cycle cannot be bipartite
{}	Yes	Empty graph is trivially bipartite
{ 0: [] }	Yes	Single isolated node
{ 0: [1], 1: [0], 2: [3], 3: [2] }	Yes	Two separate components, both bipartite

Solution❯

Understanding the Problem

A graph is bipartite if you can divide its set of vertices into two groups such that no two vertices within the same group are adjacent. In simple terms, adjacent vertices must always belong to opposite groups.

Using DFS to Check Bipartiteness

We use Depth-First Search (DFS) to try and color each node of the graph using two colors (say, 0 and 1). If any adjacent node has the same color, the graph is not bipartite.

Handling Different Scenarios

Case 1: Connected Graph

Start from any node and use DFS to color the graph. If you can color the entire graph without any two connected nodes having the same color, the graph is bipartite.

Case 2: Disconnected Graph

If the graph has multiple disconnected components, we need to perform DFS from each unvisited node. Each component must independently satisfy the bipartite condition.

Case 3: Presence of Odd-Length Cycle

Any graph containing an odd-length cycle cannot be bipartite. While coloring, you’ll find a point where two adjacent nodes need the same color—this is your cue the graph is not bipartite.

Case 4: Empty Graph

An empty graph (with zero edges) is trivially bipartite because there are no edges to violate the bipartite rule.

Conclusion

If all nodes (across all components) can be colored with two alternating colors using DFS without conflict, the graph is bipartite. Otherwise, it is not.

Algorithm Steps❯

Create a color array of size V initialized with -1 (unvisited).
Define a recursive dfs function that takes current node and currentColor.
Color the node and for each of its neighbors:

If neighbor is not coloured, call dfs with opposite colour.
If already coloured and same as current node, return false.

If DFS completes without conflicts, return true.
Check each unvisited node to ensure disconnected components are handled.

Code

JavaScript

function isBipartiteDFS(adj, V) {
  const color = new Array(V).fill(-1);

  function dfs(node, c) {
    color[node] = c;

    for (const neighbor of adj[node] || []) {
      if (color[neighbor] === -1) {
        if (!dfs(neighbor, 1 - c)) return false;
      } else if (color[neighbor] === color[node]) {
        return false;
      }
    }
    return true;
  }

  for (let i = 0; i < V; i++) {
    if (color[i] === -1) {
      if (!dfs(i, 0)) return false;
    }
  }
  return true;
}

// Example usage
const graph1 = { 0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2] };
console.log("Is graph1 bipartite?", isBipartiteDFS(graph1, 4)); // true

const graph2 = { 0: [1, 2], 1: [0, 2], 2: [0, 1] };
console.log("Is graph2 bipartite?", isBipartiteDFS(graph2, 3)); // false

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	Even in the best case, we must traverse all vertices and their edges to ensure bipartite coloring without assumptions.
Average Case	O(V + E)	Each vertex and edge is visited once during the DFS traversal.
Worst Case	O(V + E)	In the worst case, the graph is fully connected and requires full traversal of all vertices and edges.

Space Complexity❯

O(V)

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

⬅ Previous TopicNumber of Distinct Islands using DFS

Next Topic ⮕Topological Sort Using DFS