Bipartite Graph Check — BFS 2-Coloring Algorithm

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.

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

BFS 2-coloring iterates through all nodes to handle disconnected graphs. For each uncolored component, assign colors alternately using BFS. A color conflict immediately signals a non-bipartite graph (an odd cycle). The algorithm runs in O(V+E) time and O(V) space for the color array and BFS queue. DFS works equally well — the color assignment logic is identical, just with a stack or recursion instead of a queue.

from collections import deque

def is_bipartite(num_v, adj):
    """
    adj: dict or list of lists, adjacency list
    Returns True if the graph is bipartite.
    """
    color = [-1] * num_v  # -1 = uncolored

    for start in range(num_v):
        if color[start] != -1:
            continue  # already colored in a previous BFS
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in adj.get(u, []):
                if color[v] == -1:
                    color[v] = 1 - color[u]  # assign opposite color
                    queue.append(v)
                elif color[v] == color[u]:
                    return False  # same color on adjacent nodes
    return True

# Bipartite graph: two sides {0,2,4} and {1,3}
adj1 = {0:[1,3], 1:[0,2], 2:[1,3], 3:[0,2,4], 4:[3]}
print(is_bipartite(5, adj1))  # True

# Non-bipartite: triangle 0-1-2
adj2 = {0:[1,2], 1:[0,2], 2:[0,1]}
print(is_bipartite(3, adj2))  # False

Frequently Asked Questions