Is Graph Bipartite — BFS and DFS 2-Coloring with Disconnected Components

Problem Statement#

You are given an undirected graph as an adjacency list graph where graph[u] is the list of nodes adjacent to u. Return true if the graph is bipartite, false otherwise. A graph is bipartite if its node set can be partitioned into two disjoint subsets such that every edge connects a node in one subset to a node in the other.

The graph may be disconnected, may contain self-loops (which immediately disqualify it), and indices range from 0 to n minus 1.

Why This Problem Matters#

Is Graph Bipartite is the canonical bipartite-test problem and a frequent interview question at Amazon, Google, Facebook, and Microsoft. It is the simplest manifestation of graph coloring and a building block for harder problems including Bipartite Matching, Conflict Graph Scheduling, and Possible Bipartition. Recruiters love it because the question is short to state, but a clean answer requires understanding three subtle points: bipartite is equivalent to no-odd-cycle, the graph may be disconnected so you must loop over all starting nodes, and both BFS and DFS work but each has trade-offs.

If you can produce a correct, complexity-aware solution and articulate the bipartite-equals-no-odd-cycle theorem, you signal mathematical maturity beyond pattern matching.

The Core Insight#

A graph is bipartite if and only if you can 2-color it such that adjacent nodes have different colors. The algorithm is straightforward: pick any uncolored node, paint it color 0, then BFS or DFS through the component, alternating colors. If any traversal reveals an edge connecting two nodes with the same color, the graph is not bipartite.

The disconnected-component case forces an outer loop. If you only color the component reachable from node 0, you miss the rest of the graph. Loop over every index, and only launch a coloring traversal when the node is still uncolored.

A quick mental shortcut: the graph is bipartite if and only if every cycle in it has even length. Trees are always bipartite because they contain no cycles at all. Triangles, pentagons, and any odd-length cycle prevent bipartiteness.

Visual Dry Run (BFS/DFS trace)#

Take graph equal to [[1,3], [0,2], [1,3], [0,2]], which is a 4-node cycle 0 to 1 to 2 to 3 back to 0. We use a color array initialized to -1.

Outer loop, i equal to 0. Color is -1, launch BFS. Set color[0] to 0. Push 0.

Pop 0. Neighbors are 1 and 3. color[1] is -1, set to 1, push 1. color[3] is -1, set to 1, push 3.

Pop 1. Neighbors are 0 and 2. color[0] is 0, different from 1's color 1, fine. color[2] is -1, set to 0, push 2.

Pop 3. Neighbors are 0 and 2. color[0] is 0, fine. color[2] is 0, equal to 3's color 1? No, 3's color is 1, 2's color is 0, different, fine.

Pop 2. Neighbors are 1 and 3. color[1] is 1, different from 2's color 0, fine. color[3] is 1, fine.

Outer loop, i equal to 1, 2, 3. All colored, skip. Return true.

Now consider graph equal to [[1,2,3], [0,2], [0,1,3], [0,2]], which contains the triangle 0 to 1 to 2 back to 0.

Color 0 with 0. Color 1 with 1, color 2 with 1, color 3 with 1. Pop 1. Neighbor 2 has color 1, equal to 1's color 1. Return false. The triangle is an odd cycle and ruins bipartiteness.

Solution (Optimal)#

Python — BFS 2-coloring#

from collections import deque
 
class Solution:
    def isBipartite(self, graph):
        n = len(graph)
        color = [-1] * n
        for i in range(n):
            if color[i] != -1:
                continue
            q = deque([i])
            color[i] = 0
            while q:
                u = q.popleft()
                for v in graph[u]:
                    if color[v] == -1:
                        color[v] = 1 - color[u]
                        q.append(v)
                    elif color[v] == color[u]:
                        return False
        return True

JavaScript — DFS 2-coloring#

var isBipartite = function(graph) {
    const n = graph.length;
    const color = new Array(n).fill(-1);
    const dfs = (u, c) => {
        color[u] = c;
        for (const v of graph[u]) {
            if (color[v] === -1) {
                if (!dfs(v, 1 - c)) return false;
            } else if (color[v] === c) {
                return false;
            }
        }
        return true;
    };
    for (let i = 0; i < n; i++) {
        if (color[i] === -1 && !dfs(i, 0)) return false;
    }
    return true;
};

Time complexity is O(V plus E). Space complexity is O(V) for the color array plus O(V) for the BFS queue or DFS recursion stack.

Common Mistakes#

Skipping the outer loop and only checking the component containing node 0 misses disconnected components. Failing to handle nodes already colored when you encounter them through a different path will trigger a false negative if you set the color again instead of comparing. Treating the color array as boolean true or false makes you confuse uncolored with one of the colors; use -1 sentinel for uncolored and 0 or 1 for actual colors. Forgetting that the input is undirected and not adding both edges to the adjacency list (when constructing it manually) breaks the algorithm; here graph is already adjacency-list form, but when given an edge list you must symmetrize.

Interview Tips#

State the bipartite definition, then immediately translate it to 2-colorability. Mention the equivalent characterization that bipartite equals no odd cycles; some interviewers love this depth. Discuss both BFS and DFS, then pick BFS in code to avoid recursion limits on chain-shaped graphs with up to 10,000 nodes. Walk through one even cycle and one odd cycle to show you understand the failure mode. If asked about parallelism, note that each connected component is independent, so you can process components in parallel after a one-pass component identification.

Follow-up Questions#

What if the graph has self-loops? A self-loop on any node makes it non-bipartite because the loop is a cycle of length 1, which is odd. How do you output the two color classes? After the coloring pass, partition nodes by color value. What if you must compute the bipartite indicator for many subgraphs of the same large graph? Precompute connected components and the bipartite verdict per component, then answer queries by lookup. How would Union Find handle this? Use a weighted Union Find where each node tracks parity offset from its root; a non-bipartite graph reveals itself as a parity conflict during a union. What if edges arrive online? Maintain Union Find with parity; each new edge either confirms the same parity expectation or detects an odd cycle.

Key Takeaways#

• Is Graph Bipartite tests 2-colorability; equivalent to having no odd-length cycles
• BFS and DFS coloring both run in O(V plus E) with O(V) space
• Always loop over all node indices to handle disconnected components
• Use -1 as the uncolored sentinel; never overwrite an existing color, only compare
• Self-loops automatically disqualify a graph from being bipartite
• Pattern is the foundation for Possible Bipartition, Bipartite Matching, and Course Schedule