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;
    }
}

Frequently Asked Questions