Bipartite Graph Check — Disconnected Component Trap

Graphs show up everywhere in software — social networks, recommendation engines, scheduling systems, even compilers. But not all graphs are created equal. Some have a hidden structure that unlocks powerful optimizations, and bipartiteness is one of the most practically useful of those structures. Knowing whether a graph is bipartite is the difference between a Netflix that recommends movies you'll actually watch and one that just guesses randomly.

The core problem bipartite checking solves is this: can you divide the nodes of a graph into exactly two groups such that every edge crosses from one group to the other? No edge should connect two nodes inside the same group. This property is what makes matching algorithms (like pairing job applicants to job openings) efficient, and it's why databases use it to optimize JOIN operations under the hood.

By the end of this article you'll understand not just how to implement a bipartite check using both BFS and DFS, but why the 2-coloring trick works mathematically, what disconnected graphs mean for your algorithm, and how to handle the edge cases that trip people up in real interviews. You'll walk away with fully runnable Java code and the confidence to reason about graph coloring problems from scratch.

What is Bipartite Graph Check? — Plain English

A graph is bipartite if you can color every node with one of two colors such that no two adjacent nodes share the same color. Imagine trying to seat guests at a party where certain pairs don't get along — you put one group on the left side and another on the right, ensuring every conflict is between sides, not within. Common examples: job assignment graphs (workers on one side, jobs on the other), class scheduling (students on one side, courses on the other), and movie recommendation systems (users and movies as two distinct sets). A graph is bipartite if and only if it contains no odd-length cycle. BFS or DFS can check this in O(V+E) by attempting to 2-color the graph and failing when a conflict is found.

How Bipartite Check Works — Step by Step

BFS 2-coloring algorithm:

1. Initialize color array with -1 for all nodes (uncolored).
2. For each uncolored node (to handle disconnected graphs):
3. a. Assign color 0 to this node and add it to the BFS queue.
4. b. While queue is not empty:
5. i. Dequeue node u.
6. ii. For each neighbor v of u:
7. - If v is uncolored: color v with 1 - color[u] (opposite color), enqueue v.
8. - If v has the same color as u: return False (not bipartite, odd cycle detected).
9. If all nodes are colored without conflict: return True.

import java.util.*;

public class BipartiteCheck {
    public boolean isBipartite(int n, List<List<Integer>> adj) {
        int[] color = new int[n];
        Arrays.fill(color, -1);
        
        for (int i = 0; i < n; i++) {
            if (color[i] != -1) continue;
            color[i] = 0;
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(i);
            
            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : adj.get(u)) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u];
                        queue.offer(v);
                    } else if (color[v] == color[u]) {
                        return false;  // Odd cycle detected
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        // Example: bipartite graph; edges: 0-1,0-3,1-2,2-3,3-4
        int n = 5;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        adj.get(0).addAll(Arrays.asList(1,3));
        adj.get(1).addAll(Arrays.asList(0,2));
        adj.get(2).addAll(Arrays.asList(1,3));
        adj.get(3).addAll(Arrays.asList(0,2,4));
        adj.get(4).addAll(Arrays.asList(3));
        
        BipartiteCheck bc = new BipartiteCheck();
        System.out.println(bc.isBipartite(n, adj));  // true
        
        // Non-bipartite: triangle 0-1-2
        n = 3;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        adj.get(0).addAll(Arrays.asList(1,2));
        adj.get(1).addAll(Arrays.asList(0,2));
        adj.get(2).addAll(Arrays.asList(0,1));
        System.out.println(bc.isBipartite(n, adj));  // false
    }
}

Worked Example — Checking a Graph for Bipartiteness

Graph: nodes 0,1,2,3,4. Edges: (0,1),(0,3),(1,2),(2,3),(3,4).

BFS from 0: color[0]=0. Queue=[0]. 1. Dequeue 0. Neighbors 1,3 uncolored → color[1]=1, color[3]=1. Queue=[1,3]. 2. Dequeue 1. Neighbor 0 (color=0≠1, OK). Neighbor 2 uncolored → color[2]=0. Queue=[3,2]. 3. Dequeue 3. Neighbor 0 (color=0≠1, OK). Neighbor 2 (color=0≠1, OK). Neighbor 4 uncolored → color[4]=0. Queue=[2,4]. 4. Dequeue 2. Neighbor 1 (color=1≠0, OK). Neighbor 3 (color=1≠0, OK). Queue=[4]. 5. Dequeue 4. Neighbor 3 (color=1≠0, OK). Queue=[]. 6. No conflicts. Return True. Bipartition: {0,2,4} and {1,3}.

Now add edge (0,2): color[0]=0, color[2]=0, same color! Not bipartite (triangle 0-1-2 is odd cycle).

Implementation Details – Production-Grade Java Code

import java.util.*;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

public class BipartiteCheckProduction {
    private static final Logger log = LoggerFactory.getLogger(BipartiteCheckProduction.class);

    public boolean isBipartite(int n, List<Integer>[] adj) {
        int[] color = new int[n];
        Arrays.fill(color, -1);
        
        for (int start = 0; start < n; start++) {
            if (color[start] != -1) continue;
            
            color[start] = 0;
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(start);
            
            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (int v : adj[u]) {
                    if (color[v] == -1) {
                        color[v] = 1 - color[u];
                        queue.offer(v);
                    } else if (color[v] == color[u]) {
                        log.warn("Non-bipartite: conflict between nodes {} and {} with color {}", u, v, color[u]);
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

Edge Cases and Pitfalls

Five edge cases that break naive implementations: 1. Disconnected components: As shown, iterate over all vertices. 2. Self-loop: A node connected to itself forces same color → non-bipartite immediately. 3. Graph with 0 or 1 node: Trivially bipartite (no edges). 4. Multiple edges between same nodes: Should not cause false positive but can be optimised: use Set adjacency to avoid duplicate per-tasking. 5. Directed graph: Bipartition is defined on undirected graphs. For directed, ignore direction and treat edges as undirected for coloring.

Also, do not confuse bipartite with complete bipartite. Bipartite only requires that all edges go across the two sets; no requirement that all cross-edges exist.

DFS Alternative – Recursive 2-Coloring

DFS works identically in logic: assign the opposite color to each unvisited neighbor, and recurse. The only difference is recursion stack vs. explicit BFS queue. Use DFS when you need to also find the odd cycle path (DFS can backtrack). For large graphs, prefer iterative BFS to avoid stack overflow.

Pseudo-code for DFS: function dfs(u, c): color[u] = c for each neighbor v: if color[v] == -1: if not dfs(v, 1-c): return false else if color[v] == c: return false return true

Call from each uncolored node: color[start] = 0; if not dfs(start, 0) return false.

public class BipartiteCheckDFS {
    private int[] color;
    private List<Integer>[] adj;
    
    public boolean isBipartite(int n, List<Integer>[] adj) {
        this.adj = adj;
        color = new int[n];
        Arrays.fill(color, -1);
        
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                color[i] = 0;
                if (!dfs(i)) return false;
            }
        }
        return true;
    }
    
    private boolean dfs(int u) {
        for (int v : adj[u]) {
            if (color[v] == -1) {
                color[v] = 1 - color[u];
                if (!dfs(v)) return false;
            } else if (color[v] == color[u]) {
                return false;
            }
        }
        return true;
    }
}

BFS: The Queue Doesn't Lie — Why Adjacency-Level Coloring Works

The BFS approach for bipartite check isn't just another graph traversal. It's the direct answer to the question: can I separate my graph into two camps where no member of a camp shares an edge with another member of the same camp?

The logic is ruthless: assign a color to the starting node (say color 0), then every neighbor gets the opposite color (color 1). The BFS queue enforces level-by-level processing, which means any edge connecting two nodes at the same BFS level instantly reveals an odd-length cycle. That's your smoking gun — the graph fails.

Production teams prefer BFS over DFS for this specific problem because BFS guarantees you find conflicts at the shallowest depth. In a large graph with millions of vertices, BFS also avoids stack overflow that DFS recursion can trigger on deep paths. The adjacency list representation is your default choice here — it's O(V+E) space and time, no surprises. If you're seeing a Java StackOverflowError during DFS on a sparse graph with long chains, switch to BFS immediately.

Feed the graph into a queue, track colors in an integer array (0=uncolored, 1=red, -1=blue), and the moment you try to assign a color that doesn't match, return false.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class BipartiteBFS {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n]; // 0=unvisited, 1=red, -1=blue
        
        for (int start = 0; start < n; start++) {
            if (colors[start] != 0) continue;
            
            Queue<Integer> queue = new LinkedList<>();
            colors[start] = 1;
            queue.offer(start);
            
            while (!queue.isEmpty()) {
                int current = queue.poll();
                int expectedNeighborColor = -colors[current];
                
                for (int neighbor : graph[current]) {
                    if (colors[neighbor] == 0) {
                        colors[neighbor] = expectedNeighborColor;
                        queue.offer(neighbor);
                    } else if (colors[neighbor] != expectedNeighborColor) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

DFS: Recursive Coloring With Explicit Stack State

DFS for bipartite check is elegant — until it isn't. The recursion naturally follows edges deeper, coloring as it goes. If a node is already colored and the neighbor has the same color, the graph fails. The recursion backtracks, and you're done.

The WHY: DFS exploits the graph's connectivity structure. It works beautifully on trees and graphs with shallow depth. The problem? Stack depth. For a graph with a chain of 10,000 nodes, your recursion call stack eats memory proportional to the longest path. In production, that's a StackOverflowError waiting to happen. Senior engineers write the iterative DFS version with an explicit Deque stack — it's the same logic, no recursion risk.

You must pass the parent node in the recursive call to avoid re-coloring the immediate parent (which is fine — it should have the opposite color). The implementation is tight: start at node 0, color it, then for each neighbor, either recurse or check the color conflict.

Disconnected graphs? Same fix as BFS: loop over all vertices. Each uncolored node starts a new DFS component. Complexity is O(V+E) time and O(V) space for the color array plus recursion auxiliary space.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class BipartiteDFS {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] colors = new int[n];
        
        for (int v = 0; v < n; v++) {
            if (colors[v] == 0) {
                if (!dfsColor(graph, colors, v, 1)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private boolean dfsColor(int[][] graph, int[] colors, int node, int color) {
        colors[node] = color;
        for (int neighbor : graph[node]) {
            if (colors[neighbor] == 0) {
                if (!dfsColor(graph, colors, neighbor, -color)) {
                    return false;
                }
            } else if (colors[neighbor] == color) {
                return false;
            }
        }
        return true;
    }
}