☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Bipartite Graph (DFS)

Hard TUF ID 2813 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an undirected graph with V vertices as an adjacency list. The graph is bipartite if its vertices can be split into two groups so that every edge joins a vertex of one group to a vertex of the other; no edge stays inside a group. Equivalently, you can colour every vertex with one of two colours so that the two ends of every edge have different colours. Return true if the graph is bipartite.

The graph may be disconnected, and every component must be colourable. Constraints: 1 ≤ V ≤ 10^5, 0 ≤ E ≤ 10^5.

Example 1 (LeetCode 785, graph = [[1,2,3],[0,2],[0,1,3],[0,2]])

0 --- 1
| \   |
|  \  |
3 --- 2         edges: 0-1, 0-2, 0-3, 1-2, 2-3
answer = false  // 0, 1, 2 form a triangle: three vertices, two colours, two must clash

Example 2 (graph = [[1,3],[0,2],[1,3],[0,2]])

0 --- 1
|     |
3 --- 2         edges: 0-1, 1-2, 2-3, 3-0
answer = true   // groups {0, 2} and {1, 3}

The classical characterisation: a graph is bipartite exactly when it has no cycle of odd length. Walking around a cycle, the colours must alternate, so the cycle can only close if its length is even. Example 1 fails because of the triangle 0-1-2. The algorithms below never search for odd cycles explicitly; they try to colour and detect the clash that an odd cycle forces.

Approach 1: Brute force, try every colouring

Intuition. A colouring assigns one bit to each vertex, so there are 2^V colourings. Check each one against every edge, and answer true if any of them has no clash. The integer mask encodes a colouring: bit u is the colour of vertex u.

Algorithm.

  1. For each mask from 0 to 2^V - 1:
  2. For every edge u - v, compare bit u and bit v of mask; on equality, this colouring fails.
  3. If some colouring passes every edge, return true; otherwise false.
static boolean bruteForce(int V, List<List<Integer>> adj) {
    for (int mask = 0; mask < (1 << V); mask++) {     // bit u of mask = colour of vertex u
        boolean ok = true;
        for (int u = 0; u < V && ok; u++) {
            for (int v : adj.get(u)) {
                if (((mask >> u) & 1) == ((mask >> v) & 1)) { ok = false; break; }
            }
        }
        if (ok) return true;
    }
    return false;
}

Complexity. Time O(2^V · (V + E)). Space O(1) extra. It only works for about V ≤ 20, and it wastes effort: once the colour of one vertex is chosen, the colours of its whole component are forced, so almost all of these colourings are pointless to try.

Approach 2: Optimal, DFS colouring

Intuition. Pick any uncoloured vertex and give it colour 0. Every neighbour must then have colour 1, every neighbour of those must have colour 0, and so on. Nothing is being guessed: inside a connected component, the colour of the first vertex decides all the others. The first choice is also harmless, because swapping the two colours of a valid colouring gives another valid colouring.

So DFS simply propagates colours. When it meets a neighbour that is already coloured, there are two possibilities:

Why does a clash really mean an odd cycle? The colour of each vertex equals the parity of its depth in the DFS tree. Two same-coloured vertices u and v joined by an edge have depths of equal parity, so the tree paths from them to their lowest common ancestor have lengths of the same parity, and together with the edge u - v they form a cycle of odd length.

Algorithm.

  1. Set every color to -1 (uncoloured).
  2. For each uncoloured vertex s, call paint(s, 0); return false if it fails. The loop is what handles disconnected graphs.
  3. paint(u, c): set color[u] = c. For each neighbour v: if uncoloured, paint(v, 1 - c) and propagate failure; if color[v] == c, fail.
static boolean dfs(int V, List<List<Integer>> adj) {
    int[] color = new int[V];
    Arrays.fill(color, -1);                          // -1 = not coloured yet
    for (int s = 0; s < V; s++) {
        if (color[s] == -1 && !paint(s, 0, adj, color)) return false;   // each component starts fresh
    }
    return true;
}

static boolean paint(int u, int c, List<List<Integer>> adj, int[] color) {
    color[u] = c;
    for (int v : adj.get(u)) {
        if (color[v] == -1) {
            if (!paint(v, 1 - c, adj, color)) return false;
        } else if (color[v] == c) {
            return false;                            // both ends of edge u-v have the same colour
        }
    }
    return true;
}

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

call neighbour its colour result
paint(0, 0) 1 none paint(1, 1)
paint(1, 1) 0 0 fine, differs from 1
paint(1, 1) 2 none paint(2, 0)
paint(2, 0) 0 0 same as 2’s colour: return false

The clash on edge 2 - 0 closes the odd cycle 0 - 1 - 2 - 0.

Complexity. Time O(V + E): every vertex is coloured once and every adjacency list scanned once. Space O(V) for color and the recursion stack.

Approach 3: BFS colouring

Intuition. The propagation does not care about order, only that each newly reached vertex gets the opposite colour of the vertex it was reached from. BFS does the same thing layer by layer: layer k of the BFS gets colour k mod 2. A clash is an edge inside one layer, which again closes an odd cycle. This version avoids deep recursion, which matters in Java when V is large and the graph is a long path.

static boolean bfs(int V, List<List<Integer>> adj) {
    int[] color = new int[V];
    Arrays.fill(color, -1);
    for (int s = 0; s < V; s++) {
        if (color[s] != -1) continue;
        color[s] = 0;
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(s);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (color[v] == -1) { color[v] = 1 - color[u]; q.offer(v); }
                else if (color[v] == color[u]) return false;
            }
        }
    }
    return true;
}

Complexity. Time O(V + E), space O(V) for the queue and colours.

Edge cases and pitfalls