DFS Implementation

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 $O(V + E)$ time and uses $O(V)$ space.