Start practising

Is Graph Bipartite?

Medium Graphs Cycle Detection Original on LeetCode

Is Graph Bipartite? is a medium graphs problem solved with the cycle detection pattern. The best approach, dfs two-colouring, runs in O(V + E) time and O(V) space. Below are 2 approaches in Java, from bfs two-colouring up.

Problem

An undirected graph is bipartite if its nodes can be split into two groups so that every edge connects nodes from different groups. graph[u] lists the neighbours of u. Decide whether the graph is bipartite.

Examples

Example 1

Input
graph = [[1,3],[0,2],[1,3],[0,2]]
Output
true
Why
Sets {0, 2} and {1, 3}.

Example 2

Input
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output
false
Why
0, 1, 2 form a triangle, which is an odd cycle.

Constraints

  • 1 <= n <= 100; undirected, possibly disconnected.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
BFS two-colouringO(V + E)O(V)
DFS two-colouringO(V + E)O(V)

1BFS two-colouring

TimeO(V + E)
SpaceO(V)

Colour an uncoloured node 0, then give every neighbour the opposite colour with BFS. A neighbour with the same colour means the graph is not bipartite.

  1. color[] = -1.
  2. For each uncoloured start: BFS; neighbour uncoloured → 1 - color[u]; same colour → false.
Java
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);
        for (int s = 0; s < n; s++) {
            if (color[s] != -1) continue;
            Queue<Integer> q = new ArrayDeque<>();
            q.add(s);
            color[s] = 0;
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : graph[u]) {
                    if (color[v] == -1) { color[v] = 1 - color[u]; q.add(v); }
                    else if (color[v] == color[u]) return false;
                }
            }
        }
        return true;
    }
}

2DFS two-colouring

TimeO(V + E)
SpaceO(V)

Same idea recursively: colour a node, then try to colour each neighbour with the opposite colour.

  1. dfs(u, c): color[u] = c; for each v: if uncoloured and !dfs(v, 1 - c) return false; if same colour return false.
Java
class Solution {
    public boolean isBipartite(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;
    }

    private boolean dfs(int[][] g, int u, int c, int[] color) {
        color[u] = c;
        for (int v : g[u]) {
            if (color[v] == -1) { if (!dfs(g, v, 1 - c, color)) return false; }
            else if (color[v] == c) return false;
        }
        return true;
    }
}

Edge cases to test

  • Disconnected graph
  • Isolated nodes

Hints

Hint 1

Try to colour the graph with two colours so every edge joins different colours. It fails exactly when there is an odd cycle.

FAQ

What is the best time complexity for Is Graph Bipartite??

DFS two-colouring runs in O(V + E) time and O(V) extra space.

Which pattern does Is Graph Bipartite? use?

It is a graphs problem that uses the cycle detection pattern. Other problems with the same pattern: Undirected Graph Cycle, Directed Graph Cycle.

Is there a brute force solution for Is Graph Bipartite??

Yes. BFS two-colouring takes O(V + E) time and O(V) space. Colour an uncoloured node 0, then give every neighbour the opposite colour with BFS.

Which edge cases should I test for Is Graph Bipartite??

Disconnected graph; Isolated nodes.