Is Graph Bipartite?

BFS two-coloring: an edge between same-colored nodes proves it's impossible

time O(V + E)space O(V)

Color nodes one component at a time with BFS: give the start node color 0, then force every uncolored neighbor to the OPPOSITE color and queue it. The only way this can fail is a neighbor that is already colored and happens to match — which can only happen if some cycle has odd length, because walking around an even cycle always alternates back to the opposite color of where you started, while an odd cycle forces two ends of the same edge to agree. Loop over every starting node so a disconnected graph gets checked component by component.

Details

Animated on: 7 nodes, two components: the 4-cycle 0-1-2-3-0 and the triangle 4-5-6-4 — can every node be colored with only two colors so no edge joins two same-colored nodes?

Problem:Is Graph Bipartite?Medium

BFS two-coloring: an edge between same-colored nodes proves it's impossible

step 1 / 9

Undirected graph, every node uncolored

7 nodes. A graph is bipartite only if every node can be painted one of two colors so that no edge joins two nodes of the SAME color — so color node by node and let an edge that disagrees prove it can't be done.

Pseudocode

1FUNCTION isBipartite(n, edges):
2  BUILD adjacency LIST FROM edges
3  color <- ARRAY of n VALUES -1
4  FOR start FROM 0 TO n - 1
5    IF color[start] != -1: CONTINUE
6    color[start] <- 0; queue <- [start]
7    WHILE queue NOT EMPTY
8      u <- REMOVE FIRST FROM queue
9      FOR EACH v IN adjacency[u]
10        IF color[v] = -1
11          color[v] <- 1 - color[u]; APPEND v TO queue
12        ELSE IF color[v] = color[u]
13          RETURN false
14  RETURN true

← / → step · space play · Home restart

Every step in words

Show all 9 steps

7 nodes. A graph is bipartite only if every node can be painted one of two colors so that no edge joins two nodes of the SAME color — so color node by node and let an edge that disagrees prove it can't be done.
Node 0 starts a new component — pick color 0 for it arbitrarily and queue it.
Dequeue 0 (color 0) and check its neighbors: 1 gets color 1, 3 gets color 1, queued.
Dequeue 1 (color 1) and check its neighbors: 2 gets color 0, queued.
Dequeue 3 (color 1) and check its neighbors: every neighbor is already colored and none matches, so nothing to do.
Dequeue 2 (color 0) and check its neighbors: every neighbor is already colored and none matches, so nothing to do.
Node 4 starts a new component (not reachable from anything colored so far) — pick color 0 for it arbitrarily and queue it.
Dequeue 4 (color 0) and check its neighbors: 5 gets color 1, 6 gets color 1, queued.
Dequeue 5 (color 1) and check its neighbors: 6 is ALREADY color 1 — the same as 5. An edge can never join two same-colored nodes, so this graph is not bipartite. RETURN false.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Is Graph Bipartite? in the editor All Graph problems Back to roadmap