How to Determine If a Graph Is Bipartite Using DFS/BFS (Graph Coloring & Odd Cycle Detection)

Graph theory is one of the most versatile tools in computer science. Many real-world systems from networks to data relationships naturally form graphs. Among the most fundamental graph structures is the bipartite graph. Understanding bipartite graphs helps in solving constraint-based problems, partitioning systems, matching tasks, and reasoning about conflicts in large networks.

What Is a Bipartite Graph?

A graph is bipartite if its vertices can be divided into two disjoint sets such that:

Every edge connects a vertex from one set to the other
No two vertices within the same set are directly connected

Formal Definition

A graph G = (V, E) is bipartite if the vertex set V can be partitioned into two disjoint sets U and W such that U ∩ W = ∅, and every edge in E connects a vertex in U to a vertex in W.

The Core Property

A graph is bipartite if and only if it contains no odd-length cycle.

This single statement is the backbone of all bipartite-checking techniques.

Even-length cycles → allowed
Odd-length cycles → impossible to split into two valid sets

Bipartite Graphs as a Coloring Problem

Instead of explicitly forming two sets, we can reframe the problem using graph coloring:

Assign each node one of two colors (e.g., 0 and 1)
Adjacent nodes must always have different colors
If a conflict occurs, the graph is not bipartite

This approach works seamlessly for both connected and disconnected graphs.

Approach 1: Depth-First Search (DFS)

Intuition

DFS explores a graph deeply before backtracking. While traversing:

Start from an uncolored node
Assign it a color
Recursively assign the opposite color to its neighbors
If a neighbor already has the same color, the structure is invalid
Repeat for all components

C++ Implementation (DFS)

class Solution {
public:
    bool dfsCheck(int node, vector<vector<int>>& graph, vector<int>& color) {
        for (int neighbor : graph[node]) {
            if (color[neighbor] == -1) {
                color[neighbor] = 1 - color[node];
                if (!dfsCheck(neighbor, graph, color))
                    return false;
            } else if (color[neighbor] == color[node]) {
                return false;
            }
        }
        return true;
    }

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

        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                color[i] = 0;
                if (!dfsCheck(i, graph, color))
                    return false;
            }
        }
        return true;
    }
};

Complexity

Time: O(V + E)
Space: O(V) (color array + recursion stack)

Approach 2: Breadth-First Search (BFS)

Intuition

BFS processes the graph level by level:

Start from an uncolored node
Assign a color and push it into a queue
Assign opposite colors to its neighbors
Detect conflicts during traversal
Repeat for all components

C++ Implementation (BFS)

class Solution {
public:
    bool bfsCheck(int start, vector<vector<int>>& graph, vector<int>& color) {
        queue<int> q;
        q.push(start);
        color[start] = 0;

        while (!q.empty()) {
            int node = q.front();
            q.pop();

            for (int neighbor : graph[node]) {
                if (color[neighbor] == -1) {
                    color[neighbor] = 1 - color[node];
                    q.push(neighbor);
                } else if (color[neighbor] == color[node]) {
                    return false;
                }
            }
        }
        return true;
    }

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

        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!bfsCheck(i, graph, color))
                    return false;
            }
        }
        return true;
    }
};