Is Graph Bipartite?
Problem link: https://leetcode.com/problems/is-graph-bipartite/
Problem Statement
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.
Return true if and only if it is bipartite.
Input
An adjacency list graph (2D array).
Output
Boolean (true if bipartite, false otherwise).
Example
Input: graph = [[1,3],[0,2],[1,3],[0,2]] Output: true Explanation: We can color nodes 0 and 2 with color 0, and nodes 1 and 3 with color 1.
Explanation
In this square-like graph (even cycle), we can alternate colors perfectly around the loop without any neighbors sharing a color.
Brute Force
Intuition
Try every possible combination of coloring the $n$ nodes with 2 colors and check if any combination satisfies the condition.
Approach
- Generate all $2^n$ possible colorings.
- For each coloring, check every edge $(u, v)$ to see if
color[u] == color[v]. - If any coloring works, return true.
Dry Run
For 3 nodes, try [R,R,R], [R,R,B], [R,B,R]... [B,B,B].
Complexity Analysis
Exponential time makes this unusable for $n > 20$.
Optimal Solution
Intuition
Use BFS or DFS to color the graph. Start with an uncolored node, color it 0, and color all its neighbors 1. Then color their neighbors 0, and so on. If you ever encounter a neighbor that is already colored with the same color as the current node, the graph is not bipartite.
Approach
- Create a
colorarray initialized to -1 (uncolored). - Loop through every node $i$ (to handle disconnected components).
- If node $i$ is uncolored, start a BFS/DFS.
- During traversal:
- For each neighbor $v$ of current node $u$:
- If $v$ is uncolored, give it the opposite color:
color[v] = 1 - color[u]. - If $v$ is already colored and
color[v] == color[u], returnfalse.
- If $v$ is uncolored, give it the opposite color:
- For each neighbor $v$ of current node $u$:
- If all nodes are processed without conflict, return
true.
Dry Run
Graph: 0-1, 1-2, 2-0 (Triangle)
- color[0]=0.
- Neighbor 1: color[1]=1.
- Neighbor 2: color[2]=1.
- Check node 1 neighbors: 0(color 0, ok), 2(color 1, same as 1!). Conflict found.
Code (Java)
class Solution {
public boolean isBipartite(int[][] graph) {
int n = graph.length;
int[] color = new int[n];
Arrays.fill(color, -1);
for (int i = 0; i < n; i++) {
if (color[i] == -1) {
if (!bfs(i, graph, color)) return false;
}
}
return true;
}
private boolean bfs(int start, int[][] graph, int[] color) {
Queue<Integer> q = new LinkedList<>();
q.add(start);
color[start] = 0;
while (!q.isEmpty()) {
int curr = q.poll();
for (int neighbor : graph[curr]) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[curr];
q.add(neighbor);
} else if (color[neighbor] == color[curr]) {
return false;
}
}
}
return true;
}
}
Complexity Analysis
Time: We visit every vertex and edge once. Space: Color array and Queue/Stack take O(V) space.
Quick Revision (Brute Force)
- Try all 2^N color combinations
- Check edges for each combination
Quick Revision (Optimal)
- Bipartite == 2-Colorable == No Odd Cycles
- Use BFS/DFS to assign alternating colors (0 and 1)
- Conflict if color[neighbor] == color[current]
- Loop through all nodes for disconnected components
- O(V+E) time, O(V) space