Here is the DFS version for comparison:
function dfs(node, c, graph, color):
color[node] := c
for neighbor in graph[node]:
if color[neighbor] = -1 then
if not dfs(neighbor, 1 - c, graph, color) then
return false
else if color[neighbor] = c then
return false
return true
function isBipartite(graph):
n := length of graph
color := array of size n, all -1
for i from 0 to n - 1:
if color[i] = -1 then
if not dfs(i, 0, graph, color) then
return false
return true
Same logic, recursive style. Choose based on preference and stack limits.
This runs in time and uses space.