☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Bipartite Check using DFS

Hard TUF ID 2812 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an undirected graph with V vertices 0..V-1, where graph[u] lists the neighbours of u (each edge appears in both lists). Decide whether the graph is bipartite: can every vertex be painted one of two colours so that each edge connects two different colours? The graph may be disconnected. Solve it with depth-first search.

Constraints: 1 ≤ V ≤ 100 on LeetCode, larger in other versions; no self-loops, no repeated edges.

Example 1

graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
answer = false      // triangle 0 - 1 - 2

Example 2

graph = [[1,3],[0,2],[1,3],[0,2]]
answer = true       // colour 0 and 2 red, 1 and 3 blue

The characterisation behind every solution: a graph is bipartite if and only if it contains no odd cycle. Going around a cycle, the colour must flip on every edge, so you return to the starting vertex with its own colour only after an even number of edges. Conversely, if there is no odd cycle, the “colour by parity of distance from a root” rule never clashes.

Approach 1: Brute force, backtracking over colour choices

Intuition. Assign colours to the vertices one at a time in index order. For vertex u, try colour 0 and then colour 1, skipping a colour if an already coloured neighbour has it. If some vertex has no legal colour, undo the previous decision and try its other colour. If every vertex gets a colour, the graph is bipartite. This explores the space of colourings directly, pruning only obvious clashes.

Algorithm.

  1. assign(u): if u == V, return true.
  2. For side in {0, 1}: if no coloured neighbour of u has side, set color[u] = side and return true if assign(u + 1) succeeds; otherwise reset color[u].
  3. Return false if neither side works.
static boolean bruteForce(int[][] graph) {
    int[] color = new int[graph.length];
    Arrays.fill(color, -1);
    return assign(graph, 0, color);
}

static boolean assign(int[][] graph, int u, int[] color) {
    if (u == graph.length) return true;               // every vertex placed without a clash
    for (int side = 0; side < 2; side++) {
        boolean clash = false;
        for (int v : graph[u]) if (color[v] == side) { clash = true; break; }
        if (clash) continue;
        color[u] = side;
        if (assign(graph, u + 1, color)) return true;
        color[u] = -1;                                // undo and try the other side
    }
    return false;
}

Complexity. Worst case O(2^V · V) time, since a non-bipartite graph can force the search to try many combinations before giving up. Space O(V) for colours and recursion.

The backtracking treats each vertex’s colour as a free choice, but it is not. In a connected component, choosing one vertex’s colour forces every other vertex’s colour along the edges. Propagating those forced choices along a traversal removes all the guessing.

Approach 2: Optimal, recursive DFS colouring

Intuition. Start a DFS at an uncoloured vertex with colour 0. Every time the DFS steps from u to an uncoloured neighbour v, give v the opposite colour, 1 - c, and continue from v. When u meets a neighbour that is already coloured, there are two cases. A different colour is consistent. The same colour is a contradiction: both colours were forced from the same root, so no choice anywhere could fix it, and the graph is not bipartite.

The DFS tree paths from the root to u and to v, plus the edge u - v, form a cycle. Equal colours mean the two tree paths have the same parity, so the cycle has odd length. The algorithm is effectively an odd-cycle detector.

If the DFS of a component ends without a contradiction, every edge has been looked at from both ends with no clash, so the colouring of that component is valid. Repeat for every component.

Algorithm.

  1. Set every color to -1.
  2. For each uncoloured vertex s, call dfs(s, 0); if it returns false, return false.
  3. dfs(u, c): set color[u] = c. For each neighbour v: if uncoloured, recurse with dfs(v, 1 - c) and propagate a false; if color[v] == c, return false.
  4. Return true.
static boolean optimal(int[][] graph) {
    int[] color = new int[graph.length];
    Arrays.fill(color, -1);
    for (int s = 0; s < graph.length; s++) {
        if (color[s] == -1 && !dfs(graph, s, 0, color)) return false;
    }
    return true;
}

static boolean dfs(int[][] graph, int u, int c, int[] color) {
    color[u] = c;
    for (int v : graph[u]) {
        if (color[v] == -1) {
            if (!dfs(graph, v, 1 - c, color)) return false;
        } else if (color[v] == c) {
            return false;                             // both ends of edge u-v on the same side
        }
    }
    return true;
}

Dry run on example 1 (0: [1,2,3], 1: [0,2], 2: [0,1,3], 3: [0,2]):

call neighbour neighbour colour action
dfs(0, 0) 1 -1 recurse dfs(1, 1)
dfs(1, 1) 0 0 different, fine
dfs(1, 1) 2 -1 recurse dfs(2, 0)
dfs(2, 0) 0 0 same as 2’s colour: return false

The DFS went 0 -> 1 -> 2, giving 2 the same colour as 0, and the edge 2 - 0 closes the odd cycle 0 - 1 - 2 - 0. The false propagates up through every caller.

On example 2 the DFS colours 0:0, 1:1, 2:0, 3:1, every edge joins different colours, and the answer is true.

Complexity. Time O(V + E): each vertex is coloured once and each adjacency entry inspected once. Space O(V) for colours and up to V nested calls.

Approach 3: Optimal, DFS with an explicit stack

Intuition. The recursion in Approach 2 can be as deep as the longest path, which overflows Java’s stack for a path of a few hundred thousand vertices. Replace it with a Deque used as a stack. Colour a vertex at the moment it is pushed, which guarantees each vertex is pushed only once and already has its final colour when any neighbour inspects it. When a vertex is popped, check and extend its neighbours exactly as before.

The exact visiting order differs slightly from recursive DFS (all neighbours of a vertex are pushed at once), but the correctness argument never relied on the order. Any traversal that propagates forced colours and checks every edge gives the same verdict.

Algorithm.

  1. For each uncoloured vertex s: colour it 0 and push it.
  2. While the stack is not empty, pop u. For each neighbour v: if uncoloured, colour it 1 - color[u] and push it; if color[v] == color[u], return false.
  3. Return true.
static boolean optimalIterative(int[][] graph) {
    int V = graph.length;
    int[] color = new int[V];
    Arrays.fill(color, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (color[s] != -1) continue;
        color[s] = 0;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v : graph[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];          // colour on push, so no vertex is pushed twice
                    stack.push(v);
                } else if (color[v] == color[u]) {
                    return false;
                }
            }
        }
    }
    return true;
}

Complexity. Time O(V + E). Space O(V) on the heap. The Java tests run it on a path of 200,000 vertices.

Edge cases and pitfalls