Topics › Graphs › Problems on BFS/DFS

Bipartite graph

Hard TUF ID 499 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an undirected graph with V vertices numbered 0 to V - 1. graph[u] lists the neighbours of u, and every edge appears in both endpoints’ lists. The graph may be disconnected. Return true if the graph is bipartite: its vertices can be split into two groups so that every edge joins a vertex of one group to a vertex of the other. Equivalently, you can colour each vertex with one of two colours so that no edge has both ends the same colour. This is the BFS version of the check.

Constraints: 1 ≤ V ≤ 100 on LeetCode (up to 10^5 in other versions), no self-loops, no repeated edges.

Example 1

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

Vertices 0, 1 and 2 are pairwise adjacent. Whichever two colours you use, two of the three must share one, and the edge between them breaks the rule.

Example 2

graph = [[1,3],[0,2],[1,3],[0,2]]
answer = true       // groups {0, 2} and {1, 3}

The graph is the square 0 - 1 - 2 - 3 - 0; opposite corners share a colour.

A useful fact to keep in mind: a graph is bipartite exactly when it has no cycle of odd length. Walking around any cycle, colours must alternate, so you can only get back to the start with the right colour after an even number of steps. Triangles and pentagons are the smallest offenders.

Approach 1: Brute force, try every 2-colouring

Intuition. Each vertex goes to side 0 or side 1, so there are 2^V possible splits. Represent a split as a bitmask, where bit u gives the side of vertex u, and test each one against every edge. If any split has no edge inside a side, the graph is bipartite. This is the definition turned directly into code.

Algorithm.

1. For every mask from 0 to 2^V - 1:
2. For every edge u - v, check whether bits u and v of mask are equal. If any are, this split fails.
3. If some mask passes every edge, return true; otherwise return false.

static boolean bruteForce(int[][] graph) {
    int V = graph.length;
    for (long mask = 0; mask < (1L << V); mask++) {  // bit u of mask = side of vertex u
        boolean ok = true;
        for (int u = 0; u < V && ok; u++) {
            for (int v : graph[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) beyond the input. It only works for about V ≤ 20, and the tests keep it to small graphs.

The waste is that almost every choice is forced. Once one vertex has a colour, all its neighbours must take the other colour, their neighbours the first colour again, and so on. For a connected graph there are really only two candidate colourings, mirror images of each other. We should propagate colours rather than guess them.

Approach 2: Optimal, BFS 2-colouring

Intuition. Pick an uncoloured vertex, colour it 0, and run BFS from it. When a vertex u is dequeued, each neighbour v has to be the opposite colour:

• If v is uncoloured, colour it 1 - color[u] and enqueue it. This choice is forced, not a guess.
• If v already has the opposite colour, the edge is fine.
• If v has the same colour as u, the forced choices have collided. Since every colour in this component was forced by the first one, and the mirror-image colouring collides in the same place, no valid colouring exists. Return false.

BFS is a natural fit because it explores in layers: the start vertex is layer 0, its neighbours are layer 1, and so on, and the colour of a vertex is simply the parity of its layer. A same-colour edge means an edge between two vertices whose layers have the same parity, which, together with the BFS tree paths back to their common ancestor, forms an odd cycle.

If BFS finishes a component without a clash, that component’s colouring is valid, because every edge was checked from at least one end. Repeat from every uncoloured vertex to cover all components.

Algorithm.

1. Fill color with -1 (uncoloured).
2. For each vertex s still uncoloured: set color[s] = 0 and enqueue it.
3. While the queue is not empty, dequeue u and scan neighbours v with the three cases above.
4. If no clash occurs in any component, return true.

static boolean optimal(int[][] graph) {
    int V = graph.length;
    int[] color = new int[V];
    Arrays.fill(color, -1);                           // -1 = not coloured yet
    Deque<Integer> queue = new ArrayDeque<>();
    for (int s = 0; s < V; s++) {
        if (color[s] != -1) continue;                 // already handled as part of an earlier component
        color[s] = 0;
        queue.add(s);
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph[u]) {
                if (color[v] == -1) {
                    color[v] = 1 - color[u];          // forced: the opposite side of u
                    queue.add(v);
                } else if (color[v] == color[u]) {
                    return false;                     // an edge inside one side
                }
            }
        }
    }
    return true;
}

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

The clash on edge 1 - 2 exposes the triangle 0 - 1 - 2. On example 2 the colouring settles as 0:0, 1:1, 3:1, 2:0 with no clash, so the answer is true.

Complexity. Time O(V + E): each vertex is coloured and enqueued once, and each adjacency entry is checked once. Space O(V) for the colour array and the queue.

Edge cases and pitfalls

• Disconnected graphs. Each component is coloured independently, and a single odd cycle anywhere makes the whole graph non-bipartite. Starting BFS only at vertex 0 misses the others; the tests include a graph whose odd cycle lives in the second component.
• Isolated vertices and the empty graph are trivially bipartite.
• Colour when enqueuing. Assign the colour at the moment a vertex is first seen. If you wait until it is dequeued, it can be enqueued twice and its colour decided by whichever copy comes first.
• Use three states. A boolean[] cannot express “not yet coloured”. Use -1 for uncoloured, or a separate visited array.
• Even cycles are fine. A square or a hexagon is bipartite; only odd cycles break it.
• Self-loops. A self-loop makes a graph non-bipartite (a vertex would need a colour different from itself). The BFS reports this, because u sees itself with the same colour.
• Trees are always bipartite, since they have no cycles at all.

Related problems

• Bipartite Check using DFS does the same colouring with depth-first search.
• Bipartite Graph (DFS) is the A2Z version of the problem.
• Detect A cycle in Undirected Graph using BFS uses the same layer-by-layer traversal to find any cycle, not only odd ones.
• Number of islands(Do in Grid and Graph Both) shows the per-component outer loop on a grid.