Is Graph Bipartite: Two-Color BFS on an Adjacency List

You are given an undirected graph represented as an adjacency list. Determine whether the graph is bipartite: can you split all nodes into two independent sets A and B such that every edge connects a node in A to a node in B?

This is LeetCode 785: Is Graph Bipartite?, and it teaches the fundamental graph coloring technique of two-coloring with BFS. The core idea is simple: try to color the graph with two colors so that no two adjacent nodes share the same color. If you succeed, the graph is bipartite. If any neighbor already has the same color as the current node, it is not.

Bipartite (two-colorable)

Every edge connects a blue node to a green node. No two neighbors share a color.

Not bipartite (odd cycle)

Node 2 connects to both node 0 (blue) and node 1 (green). It cannot be either color without a conflict.

Why this problem matters

Bipartite checking shows up in scheduling, matching problems, and conflict detection. Can you assign tasks to two teams without conflicts? Can you split students into two groups where no two friends are in the same group? These are all bipartite problems in disguise.

More importantly, this problem drills a clean BFS pattern that extends to many graph problems: traverse level by level, assign properties to nodes, and check neighbors for constraint violations. Once you internalize this pattern, problems like graph coloring and cycle detection in undirected graphs become much easier.

The approach

The algorithm uses BFS with a color array:

1. Create a color array initialized to -1 (unvisited) for every node.
2. For each unvisited node (the graph may be disconnected), start a BFS.
3. Assign the starting node color 0. Add it to the queue.
4. For each node dequeued, check all its neighbors:
   • If a neighbor is uncolored, assign it the opposite color (1 - current_color) and enqueue it.
   • If a neighbor already has the same color as the current node, return False. The graph is not bipartite.
5. If BFS finishes without conflicts across all components, return True.

Clean solution

from collections import deque

def is_bipartite(graph: list[list[int]]) -> bool:
    n = len(graph)
    color = [-1] * n

    for start in range(n):
        if color[start] != -1:
            continue

        color[start] = 0
        queue = deque([start])

        while queue:
            node = queue.popleft()

            for neighbor in graph[node]:
                if color[neighbor] == -1:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False

    return True

Step-by-step walkthrough

The BFS fans out from the starting node, coloring each layer the opposite color. When it encounters a neighbor that is already colored, it checks: does the existing color match what we would assign? If yes, no problem. If the neighbor has the same color as the current node, we have found an odd cycle, and the graph cannot be two-colored.

The conflict example at the bottom shows why triangles break bipartiteness. Node 2 sits between node 0 (blue) and node 1 (green). It needs to be green (because of node 0) and blue (because of node 1) at the same time. That contradiction is exactly what our color[neighbor] == color[node] check catches.

Complexity analysis

V is the number of vertices, E is the number of edges.

Time: Each node is enqueued and dequeued at most once. Each edge is checked at most twice (once from each endpoint). Total: O(V + E).

Space: The color array takes O(V). The BFS queue holds at most O(V) nodes. Total: O(V).

The building blocks

This problem combines two reusable patterns:

1. BFS level-by-level traversal

The standard BFS pattern of processing nodes layer by layer:

queue = deque([start])
visited[start] = True

while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if not visited[neighbor]:
            visited[neighbor] = True
            queue.append(neighbor)

Here the "visited" set is replaced by a color array that stores more information than a simple boolean. Instead of just tracking "have I seen this node," we track "what color is this node." This is a common upgrade to the basic BFS template.

2. Constraint checking on neighbors

The pattern of assigning a property to a node, then verifying that all neighbors satisfy a constraint relative to that property:

for neighbor in graph[node]:
    if property[neighbor] conflicts with property[node]:
        return False

This neighbor-constraint pattern appears in graph coloring, cycle detection, and scheduling problems. The bipartite check is the simplest version: two colors, and adjacent nodes must differ.

Edge cases to watch for

• Disconnected graph: The graph may have multiple components. You must check every component, not just the one containing node 0. The outer for start in range(n) loop handles this.
• Single node, no edges: A node with no neighbors is trivially bipartite. It can go in either set.
• Self-loop: If graph[i] contains i, the node is adjacent to itself. It would need two colors simultaneously, so the graph is not bipartite. The color[neighbor] == color[node] check catches this because node and neighbor are the same.
• Already colored neighbor with correct color: This is not a conflict. If a neighbor is already colored with the opposite color, skip it. Only same-color neighbors trigger a failure.
• Empty graph: If n is 0, return True. There are no nodes to violate the bipartite property.

From understanding to recall

You have read through the BFS two-coloring solution. You see how the color array replaces the visited set, how the opposite-color assignment works, and how the same-color check catches odd cycles. The logic is clean and makes sense on paper.

But during an interview, the details matter. Remembering to loop over all nodes for disconnected components. Using 1 - color[node] for the opposite color. Checking color[neighbor] == color[node] instead of just color[neighbor] != -1. These small decisions are easy to second-guess under pressure.

Spaced repetition turns this logic into muscle memory. You write the BFS loop, the color assignment, and the conflict check from scratch at increasing intervals. After a few rounds, the pattern flows out automatically. You do not need to re-derive the algorithm. You just write it.

Related posts

• Number of Islands - Graph traversal with BFS/DFS on adjacency structures
• Clone Graph - BFS/DFS graph traversal maintaining visited state
• Course Schedule - Graph coloring for cycle detection