G-18: Bipartite Graph | DFS | C++ | Java

This chapter covers the definition, core mental model, and algorithmic implementation of checking whether an undirected graph is bipartite using Depth-First Search (DFS) in both C++ and Java.

1. Why Do We Need Bipartite Graph Validation?

In graph theory, certain problems require dividing entities into two distinct, non-overlapping groups where relationships (edges) only exist between the groups, never within them.

• The Problem: Given an undirected graph, can we color its vertices using exactly two colors such that no two adjacent nodes share the same color?
• Real-World Applications: Task scheduling (assigning tasks to two processors without conflicts), social network modeling (separating users into two rival factions or opposing groups based on interactions), and matching algorithms.

2. Core Mental Model & Analogies

The Two-Color Painting Analogy

Imagine you are given a graph and a bucket of two paint colors: Yellow (0) and Green (1). You pick an arbitrary starting node, paint it Yellow, and step across its edges to its neighbors. Because no two adjacent nodes can have the same color, every single neighbor must be painted the opposite color (Green). If you continue this traversal recursively and successfully color the entire graph without color conflicts, the graph is bipartite.

3. The Odd-Length Cycle Rule (The Golden Rule)

The structural property that determines whether a graph is bipartite is the presence of odd-length cycles:

• Even-Length Cycles: Can always be colored alternately with two colors (e.g., Yellow -> Green -> Yellow -> Green -> Yellow -> Green). Bipartite = True.
• Odd-Length Cycles: Mathematically impossible to color with only two colors without two adjacent nodes ending up with the same color. Bipartite = False.
• Linear Graphs (Trees, Paths): Always bipartite because they contain no cycles at all.

4. Naive vs. Better Approach

• Naive / Brute Force Approach: Try every possible color combination for every vertex ($2^V$ combinations), which leads to exponential time complexity and is entirely impractical for large graphs.
• DFS Traversal Approach: Leverage a single pass graph traversal (DFS) keeping track of vertex colors. By assigning alternating colors ($1 - \text{currentColor}$) and validating neighbors on-the-fly, we reduce time complexity to linear graph traversal speeds.

5. Step-by-Step Execution Flow

1. Color Array Initialization: Create a color array of size $V$ initialized to -1 (indicating uncolored).
2. Component Handling: Because graphs can have multiple disconnected components, iterate through all nodes from 0 to V-1. If a node is uncolored (-1), initiate a DFS call from it.
3. DFS Parameter Passing: Pass the current node, the assigned color (0 or 1), the color array, and the adjacency list.
4. Neighbor Validation Check:
   • If a neighbor is uncolored (-1), recursively call DFS with the opposite color (1 - currentColor).
   • If a neighbor is already colored, check if its color matches the current node's color. If it matches, we have found an adjacent node with the exact same color $\rightarrow$ Return false (Not Bipartite).
   • If all recursive branches complete without color clashes $\rightarrow$ Return true (Bipartite).

6. Complete Flow Walkthrough (Conflict Example)

7. C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    bool dfs(int node, int col, int color[], vector<int> adj[]) {
        color[node] = col;
        
        for(auto it : adj[node]) {
            // If the adjacent node is not yet colored, color it with the opposite color
            if(color[it] == -1) {
                if(dfs(it, 1 - col, color, adj) == false) return false;
            }
            // If the adjacent node is already colored and has the same color, it's not bipartite
            else if(color[it] == col) {
                return false;
            }
        }
        return true;
    }

public:
    bool isBipartite(int V, vector<int> adj[]) {
        int color[V];
        for(int i = 0; i < V; i++) color[i] = -1;
        
        // For handling disconnected components
        for(int i = 0; i < V; i++) {
            if(color[i] == -1) {
                if(dfs(i, 0, color, adj) == false) return false;
            }
        }
        return true;
    }
};

8. Java Implementation

import java.util.*;

class Solution {
    private boolean dfs(int node, int col, int[] color, ArrayList<ArrayList<Integer>> adj) {
        color[node] = col;
        
        for (int it : adj.get(node)) {
            // If the adjacent node is uncolored, give it the opposite color
            if (color[it] == -1) {
                if (dfs(it, 1 - col, color, adj) == false) return false;
            }
            // If the adjacent node has the same color, conflict found
            else if (color[it] == col) {
                return false;
            }
        }
        return true;
    }

    public boolean isBipartite(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] color = new int[V];
        Arrays.fill(color, -1);
        
        // Iterate through all components of the graph
        for (int i = 0; i < V; i++) {
            if (color[i] == -1) {
                if (dfs(i, 0, color, adj) == false) return false;
            }
        }
        return true;
    }
}

9. Complexity Analysis

10. Summary and Key Takeaways

• Bipartite Definition: A graph whose vertices can be partitioned into two independent sets such that every edge connects a vertex in set one to a vertex in set two, using only two colors.
• The Odd Cycle Rule: Any graph containing an odd-length cycle can never be bipartite.
• Even & Linear Graphs: Even-length cycles and acyclic structures (trees, paths) are always bipartite.
• Initialization State: The color array must be initialized to -1 to cleanly distinguish between unvisited nodes and colored nodes (0 or 1).
• Component-Safe Checking: Always wrap the traversal in a loop checking all vertices to guarantee full coverage of disconnected graph components.
• Conflict Propagation: If any downstream recursive DFS call returns false, immediately bubble the false result up the stack without continuing further unnecessary checks.