Is Graph Bipartite?
Asked at Apple
Problem
Given an adjacency list representation of an undirected graph, determine if the graph is bipartite. A graph is bipartite if its nodes can be split into two groups such that every edge connects nodes from different groups.
Asked At
| Company | Difficulty | |
|---|---|---|
| Apple | MEDIUM | View all Apple questions → |
How to Think About It
Brute force: Try all possible 2-colorings of the nodes (exponential, not practical).
BFS or DFS coloring: Start from any uncolored node, color it red, then alternate colors for neighbors.
If you ever encounter a neighbor that is already colored with the same color, the graph is not bipartite.
The graph may be disconnected, so iterate over all nodes and start BFS/DFS from each unvisited node.
Union-Find approach: For each edge, if both endpoints are already in the same set, it is not bipartite.
Optimal Approach
Perform a BFS or DFS on each disconnected component, assigning alternating colors (0 and 1) to nodes. For each node, color all its neighbors with the opposite color. If any neighbor already has the same color as the current node, the graph is not bipartite. The array colors stores the assignment, with 0 meaning unvisited, 1 for one group, and -1 for the other.
What Trips People Up in Real Interviews
Clarify that the graph may contain disconnected components and multiple edges.
Confirm that self-loops immediately make a graph non-bipartite.
Explain the invariant: a node and all its neighbors must have opposite colors.
Discuss BFS vs DFS tradeoffs; both are O(V + E) time.
Mention the Union-Find alternative where each edge flips the parity of one endpoint.
Solution Code
from collections import deque
def isBipartite(graph):
n = len(graph)
colors = [0] * n
for start in range(n):
if colors[start] != 0:
continue
colors[start] = 1
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if colors[neighbor] == 0:
colors[neighbor] = -colors[node]
queue.append(neighbor)
elif colors[neighbor] == colors[node]:
return False
return TrueFrequently Asked Questions
What is the Is Graph Bipartite? problem?
Given an adjacency list representation of an undirected graph, determine if the graph is bipartite. A graph is bipartite if its nodes can be split into two groups such that every edge connects nodes from different groups.
How do you solve Is Graph Bipartite??
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Is Graph Bipartite??
Is Graph Bipartite? is asked at Apple. It is a medium difficulty problem.
What are common mistakes on Is Graph Bipartite??
- Clarify that the graph may contain disconnected components and multiple edges.
- Confirm that self-loops immediately make a graph non-bipartite.
- Explain the invariant: a node and all its neighbors must have opposite colors.
- Discuss BFS vs DFS tradeoffs; both are O(V + E) time.
- Mention the Union-Find alternative where each edge flips the parity of one endpoint.