785. Is Graph Bipartite? - Explanation

1. Depth First Search

Intuition

A graph is bipartite if we can split its nodes into two groups such that every edge connects nodes from different groups. This is equivalent to checking if the graph is 2-colorable. Using DFS, we assign a color to the starting node and then assign the opposite color to all its neighbors. If we ever find a neighbor that already has the same color as the current node, the graph is not bipartite. Since the graph may be disconnected, we run dfs from every unvisited node.

Algorithm

Create a color array initialized to 0 (unvisited). Use 1 and -1 as the two colors.
Define a recursive dfs function that takes a node i and a color c:
- Assign color[i] = c.
- For each neighbor, if it has the same color, return false.
- If the neighbor is unvisited, recursively call dfs with the opposite color. If that returns false, propagate the failure.
- Return true if all neighbors pass.
For each node, if unvisited, run dfs with color 1. If any dfs fails, return false.
Return true if all components are bipartite.

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [0] * len(graph)  # Map node i -> odd=1, even=-1

        def dfs(i, c):
            color[i] = c
            for nei in graph[i]:
                if color[nei] == c:
                    return False
                if color[nei] == 0 and not dfs(nei, -c):
                    return False
            return True

        for i in range(len(graph)):
            if color[i] == 0 and not dfs(i, 1):
                return False
        return True

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V)$

Where $V$ is the number of vertices and $E$ is the number of edges.

2. Breadth First Search

Intuition

BFS provides another way to check 2-colorability. Starting from an uncolored node, we assign it a color and add it to a queue. For each node we process, we check all neighbors: if a neighbor has the same color, the graph is not bipartite; if uncolored, we assign it the opposite color and enqueue it. BFS naturally explores the graph level by level, alternating colors between levels.

Algorithm

Create a color array initialized to 0.
For each node i from 0 to n-1:
- If already colored, skip it.
- Initialize a queue with node i and set color[i] = -1.
- While the queue is not empty:
  - Dequeue a node.
  - For each neighbor: if it has the same color, return false. If uncolored, assign the opposite color and enqueue it.
Return true if all nodes are processed without conflict.

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [0] * len(graph)  # Map node i -> odd=1, even=-1

        def bfs(i):
            if color[i]:
                return True
            q = deque([i])
            color[i] = -1
            while q:
                i = q.popleft()
                for nei in graph[i]:
                    if color[i] == color[nei]:
                        return False
                    elif not color[nei]:
                        q.append(nei)
                        color[nei] = -1 * color[i]
            return True

        for i in range(len(graph)):
            if not bfs(i):
                return False
        return True

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V)$

Where $V$ is the number of vertices and $E$ is the number of edges.

3. Iterative DFS

Intuition

Iterative DFS uses an explicit stack instead of recursion to traverse the graph. The coloring logic remains the same: assign a color to a node, then process all neighbors by checking for conflicts and pushing uncolored neighbors onto the stack with the opposite color. This avoids potential stack overflow issues with very deep graphs while achieving the same result as recursive DFS.

Algorithm

Create a color array initialized to 0.
For each node i from 0 to n-1:
- If already colored, skip it.
- Set color[i] = -1 and push i onto the stack.
- While the stack is not empty:
  - Pop a node.
  - For each neighbor: if it has the same color, return false. If uncolored, assign the opposite color and push it onto the stack.
Return true if no conflicts are found.

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        color = [0] * len(graph)  # Map node i -> odd=1, even=-1
        stack = []

        for i in range(len(graph)):
            if color[i] != 0:
                continue
            color[i] = -1
            stack.append(i)
            while stack:
                node = stack.pop()
                for nei in graph[node]:
                    if color[node] == color[nei]:
                        return False
                    elif not color[nei]:
                        stack.append(nei)
                        color[nei] = -1 * color[node]

        return True

Time & Space Complexity

Time complexity: $O(V + E)$
Space complexity: $O(V)$

Where $V$ is the number of vertices and $E$ is the number of edges.

4. Disjoint Set Union

Intuition

DSU (Union-Find) offers an alternative perspective. For a bipartite graph, a node must be in a different set than all of its neighbors, but all neighbors should belong to the same set. For each node, we union all its neighbors together. If a node ever ends up in the same set as one of its neighbors, the graph is not bipartite. This works because being in the same connected component in the neighbor graph implies they must share a color in a valid 2-coloring.

Algorithm

Initialize a DSU structure with n nodes.
For each node:
- If it has no neighbors, continue.
- For each neighbor:
  - If the node and neighbor are in the same set, return false.
  - Union the neighbor with the first neighbor of the current node (grouping all neighbors together).
Return true if no conflict is detected.

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n))
        self.Size = [0] * n

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, u, v):
        pu, pv = self.find(u), self.find(v)
        if pu == pv:
            return False
        if self.Size[pu] > self.Size[pv]:
            self.Parent[pv] = pu
        elif self.Size[pu] < self.Size[pv]:
            self.Parent[pu] = pv
        else:
            self.Parent[pv] = pu
            self.Size[pu] += 1
        return True

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        dsu = DSU(n)

        for node in range(n):
            for nei in graph[node]:
                if dsu.find(node) == dsu.find(nei):
                    return False
                dsu.union(graph[node][0], nei)

        return True

Time & Space Complexity

Time complexity: $O(V + (E * α(V)))$
Space complexity: $O(V)$

Where $V$ is the number of vertices and $E$ is the number of edges. $α()$ is used for amortized complexity.

Common Pitfalls

Forgetting to Handle Disconnected Components

The graph may consist of multiple disconnected components. If you only run BFS/DFS from node 0, you will miss other components that might not be bipartite. Always iterate through all nodes and start a new traversal from any unvisited node to ensure every component is checked.

Checking Only Unvisited Neighbors

When traversing the graph, you must check the color of all neighbors, not just unvisited ones. If a neighbor is already colored with the same color as the current node, the graph is not bipartite. Skipping already-visited neighbors misses these conflict cases.

Using Wrong Initial Color Values

Using 0 as a valid color while also using it to represent "unvisited" creates ambiguity. A clean approach is to use 0 for unvisited nodes and 1/-1 as the two actual colors. Alternatively, use a separate visited array. Mixing up these states leads to incorrect bipartiteness detection.