Is Graph Bipartite

Description

Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

• There are no self-edges (graph[u] does not contain u).
• There are no parallel edges (graph[u] does not contain duplicate values).
• If v is in graph[u], then u is in graph[v] (the graph is undirected).
• The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: We can partition the nodes into two sets: {0, 2} and {1, 3}.

Constraints:

• 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.

Primary Approach: BFS 2-Coloring ($O(V+E)$ Time, $O(V)$ Space)

Intuition

A graph is bipartite if its nodes can be divided into two sets such that every edge connects a node in set A to a node in set B. Equivalently, a graph is bipartite if and only if it can be colored using 2 colors (e.g., 1 and -1) without any two adjacent nodes sharing the same color:

1. Maintain an array color[] of size $N$ initialized to 0 (uncolored).
2. Loop through all nodes $0$ to $N-1$ to handle disconnected graph components.
3. For any uncolored node, assign it color = 1 and push it to a Queue.
4. Poll a node and inspect its adjacent neighbors:
   • If a neighbor is uncolored (color[neighbor] == 0), assign it the opposite color (-color[curr]) and push it into the queue.
   • If a neighbor is already colored with the same color as curr, a conflict exists—return false.

import java.util.ArrayDeque;
import java.util.Queue;
 
class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n]; // 0: uncolored, 1: Color A, -1: Color B
 
        for (int i = 0; i < n; i++) {
            if (color[i] != 0) continue; // Skip already colored components
 
            Queue<Integer> queue = new ArrayDeque<>();
            queue.add(i);
            color[i] = 1; // Assign initial color
 
            while (!queue.isEmpty()) {
                int curr = queue.poll();
 
                for (int neighbor : graph[curr]) {
                    if (color[neighbor] == 0) {
                        // Assign opposite color to neighbor
                        color[neighbor] = -color[curr];
                        queue.add(neighbor);
                    } else if (color[neighbor] == color[curr]) {
                        // Conflict: adjacent nodes have the same color
                        return false;
                    }
                }
            }
        }
 
        return true;
    }
}
 

Complexity

• Time Complexity: $O(V+E)$ — Every vertex $V$ and edge $E$ is processed once.
• Space Complexity: $O(V)$ — color[] array and BFS queue take $O(V)$ memory.

---

Alternative Approach: DFS 2-Coloring ($O(V+E)$ Time, $O(V)$ Space)

Intuition

Perform recursive Depth-First Search to color adjacent nodes with alternating colors (1 and -1):

1. For each node $i$, if uncolored, invoke dfs(i, 1).
2. Inside DFS, set color[node] = currentColor.
3. For each neighbor:
   • If uncolored, recursively call dfs(neighbor, -currentColor). If it returns false, propagate false up.
   • If colored and matches currentColor, return false.

class Solution {
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n]; // 0: uncolored, 1: Color A, -1: Color B
 
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                if (!dfs(i, 1, color, graph)) {
                    return false;
                }
            }
        }
 
        return true;
    }
 
    private boolean dfs(int node, int currentColor, int[] color, int[][] graph) {
        color[node] = currentColor;
 
        for (int neighbor : graph[node]) {
            if (color[neighbor] == 0) {
                // Color neighbor with opposite color
                if (!dfs(neighbor, -currentColor, color, graph)) {
                    return false;
                }
            } else if (color[neighbor] == currentColor) {
                // Color conflict detected
                return false;
            }
        }
 
        return true;
    }
}
 

Complexity

• Time Complexity: $O(V+E)$ — Visits each node and edge once across all components.
• Space Complexity: $O(V)$ — $O(V)$ space for the color[] array and recursive stack depth.

---

The Graph 2-Coloring approach works on a simple principle: Can we assign one of two colors (e.g., Red and Blue) to every node such that no two connected nodes share the same color?
If yes, the graph is Bipartite; if a conflict arises, it is Not Bipartite.

Step-by-Step Mechanism

1. State Tracking: Use an array initialized to 0 (Uncolored). Use 1 for Red and -1 for Blue.
2. Start Traversal (BFS/DFS): Pick an uncolored node, color it 1 (Red), and inspect its neighbors.
3. Neighbor Checks: For every neighbor of the current node:
   • If Uncolored (0): Assign it the opposite color (-color[curr]) and push it to the queue/DFS stack.
   • If Already Colored:
     • Opposite Color: Valid! Continue traversing.
     • Same Color: Conflict! Two adjacent nodes share the same color. Immediately return false.
4. Disconnected Subgraphs: Loop through all nodes $0$ to $N-1$ so disconnected graph components are also checked.

Why It Works (The Intuition)

• Even Cycles vs. Odd Cycles:
  • An even cycle (4 nodes: $A\to B\to C\to D\to A$) can alternate colors perfectly: $\text{Red}\to \text{Blue}\to \text{Red}\to \text{Blue}$.
  • An odd cycle (3 nodes: $A\to B\to C\to A$) forces a conflict: if $A$ is Red and $B$ is Blue, $C$ must be Red—but $C$ connects back to $A$ (Red)!
• Bottom Line: Bipartite graphs are free of odd-length cycles. 2-coloring explicitly tests for odd cycles as it traverses the graph.

---

Key Interview Discussion Points

• Odd-Length Cycle Property: A graph is bipartite if and only if it contains NO odd-length cycles. An odd-length cycle (e.g., triangle $A-B-C-A$) inevitably forces two adjacent nodes to take the same color.
• Disconnected Graphs Edge Case: Always emphasize looping through for (int i = 0; i < n; i++). Relying on a single BFS/DFS starting at node 0 will miss disconnected components (which is explicitly permitted in the constraints).

---

Easy Memory Rule

“Bipartite = 2-Colorable $\to$ Alternate colors (1 & -1) $\to$ Same color on adjacent neighbor means NOT Bipartite!”