Bipartite Check · 2-Coloring BFS

A graph is bipartite if you can split its nodes into two groups with no edge inside a group. BFS colors nodes alternately; a same-color edge means it's impossible.

Concept

Alternate colors

BFS from an uncolored node, painting it color A. Every neighbor gets the opposite color. Their neighbors flip back, and so on, like a checkerboard.

If you ever try to color a node the same as an already-colored neighbor, the two-group split is impossible.

The conflict test

Uncolored neighbor → give it the opposite color
Colored with opposite → fine, continue
Colored with same color → not bipartite
Repeat per component (graph may be disconnected)

Interactive

Paint the checkerboard

Uncolored Color A Color B Conflict edge

BFS queue: empty

slowfast

Step 0

Color A

Color B

At node

–

Bipartite?

Implementation

C++

bool isBipartite(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> color(n, -1);      // -1 = uncolored

    for (int s = 0; s < n; s++) {
        if (color[s] != -1) continue;   // component already done
        queue<int> q;
        q.push(s); color[s] = 0;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : graph[u]) {
                if (color[v] == -1) {
                    color[v] = color[u] ^ 1;  // opposite color
                    q.push(v);
                } else if (color[v] == color[u]) {
                    return false;         // same color → not bipartite
                }
            }
        }
    }
    return true;
}

Complexity

Time

O(V + E)

One BFS sweep; each vertex and edge visited once.

Space

O(V)

Color array plus the BFS queue.

Bipartite iff

no odd cycle

A graph is 2-colorable exactly when it has no odd-length cycle.

Notes

Bipartite ⟺ no odd cycle. The 2-coloring fails precisely when an odd cycle forces two neighbors into the same color.
DFS works too, color on the way down and check on the back edge. Same O(V+E).
Always loop over all start nodes, a disconnected graph can have multiple components to color.
Multi-source BFS is the same queue mechanic with several seeds pushed up front (see Rotting Oranges). 0-1 BFS swaps the queue for a deque: push weight-0 edges to the front, weight-1 to the back, giving Dijkstra-quality paths in O(V+E).
Bipartite matching (Hungarian / Hopcroft-Karp) builds directly on this two-group structure.