Is Graph Bipartite?
Is Graph Bipartite?: can the nodes be split into two sets so every edge crosses between the sets? (2-colorability.)
- graph.length == n
- 1 <= n <= 100
- 0 <= graph[u].length < n
- 0 <= graph[u][i] <= n - 1
- graph[u] does not contain u.
- All the values of graph[u] are unique.
- If graph[u] contains v, then graph[v] contains u.
Intuition
Is graph bipartite asks whether the vertices can be split into two groups so that every edge runs between the groups, never inside one. Testing every possible split is 2ⁿ, so the question needs restating. The restatement is 2-colouring. Paint a vertex red; all its neighbours must then be blue, all of theirs red again, and so on. If the paint spreads through the whole graph without ever demanding that a vertex be both colours, the two colour classes are exactly the two groups. Bipartite and 2-colourable are the same property. That converts the problem into a traversal. Colour a starting vertex, then give every neighbour the opposite colour of the vertex you came from. The moment you meet an already-coloured neighbour, check it: - A neighbour already coloured the same as the current vertex means the graph is not bipartite. What that conflict really detects is an odd cycle. Walking a cycle alternates colours, so returning to the start with the same colour means the cycle had even length and everything is consistent; returning with a clash means odd length, and an odd cycle is precisely what makes a graph non-bipartite. Two practical points. The graph may be disconnected, so every uncoloured vertex must start a fresh traversal — one component being bipartite says nothing about another. And BFS and DFS work identically here; only the visit order differs, not the colouring rule or the conflict test.
Two-colouring is a traversal with one extra rule: every neighbour must get the opposite colour, and a neighbour that already holds your colour proves an odd cycle. Bipartite is exactly "no odd cycle", so this single check settles it. Either BFS or DFS works — only the container changes.
Approach
Before reading on: price up what the direct approach costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(V + E) time and O(V) space.
Restate bipartite as 2-colourable
Splitting into two sets with no internal edges is the same as colouring with two colours so no edge joins matching colours. This turns a search over 2ⁿ splits into a single traversal, which is the key move.
Use an array with three states
Track each vertex as uncoloured, colour 0, or colour 1 — a single array with −1 for unvisited. It doubles as the visited marker, so no separate structure is needed.
Colour each neighbour the opposite
On reaching an uncoloured neighbour, give it the opposite colour of the current vertex and continue the traversal from it. The alternation is what encodes the bipartite requirement directly into the walk.
Detect the conflict
If a neighbour is already coloured the same as the current vertex, the graph is not bipartite — return false immediately. An opposite colour is consistent and needs no action.
Restart at every uncoloured vertex
A disconnected graph can have one bipartite component and one that is not. Loop over all vertices and start a fresh traversal from each uncoloured one, rather than assuming a single pass covers everything.
Understand what the conflict means
A same-colour clash is exactly an odd cycle. Traversing a cycle alternates colours, so an even cycle returns consistently and an odd one cannot. This is why 'bipartite' and 'no odd cycles' are equivalent statements.
Cost of the traversal
Every vertex is coloured once and every edge inspected twice, giving O(V + E) time and O(V) space. BFS and DFS have identical complexity here — the choice is stylistic, or about recursion depth on deep graphs.
Solution & live demo
Common pitfalls
Checking only the component containing vertex 0
color[0] = 0 queue = [0]
for s in range(n):
if color[s] != -1: continue
color[s] = 0The graph may be disconnected, and a conflict can live entirely inside a component unreachable from 0. Every uncoloured vertex needs to seed its own search.
Using a boolean visited array instead of colours
if seen[v]: continue seen[v] = True
if color[v] == -1:
color[v] = 1 - color[u]
elif color[v] == color[u]:
return FalseVisited-ness alone can't detect the conflict — you need to know which side a vertex is on. Three states are required: uncoloured, side 0, side 1.
Rejecting any neighbour that is already coloured
elif color[v] != -1: return False
elif color[v] == color[u]: return False
A neighbour coloured the opposite side is exactly what a bipartite graph should look like — that's a valid edge, not a conflict. Only a same-colour neighbour breaks it.
Edge cases
Outer loop restarts coloring in every uncolored component.
Trivially bipartite.
A node adjacent to itself needs both colors — immediately false.