Is Graph Bipartite? - Video Solutions

Problem Overview: You are given an undirected graph represented as an adjacency list. The task is to determine whether the graph is bipartite. A graph is bipartite if its nodes can be divided into two groups such that no edge connects nodes within the same group. In practice, this means you should be able to color the graph using only two colors so that every edge connects nodes with different colors.

Approach 1: Two-Coloring using BFS (O(V + E) time, O(V) space)

This approach treats the problem as a graph coloring task. Maintain a color array where each node is assigned either 0 or 1. Iterate through every node because the graph may have multiple disconnected components. For each uncolored node, start a BFS traversal and assign it a color. When visiting neighbors, assign the opposite color (1 - color[current]). If you ever encounter a neighbor already colored with the same color as the current node, the graph is not bipartite. BFS works well because it naturally processes nodes level by level, which aligns with alternating colors between adjacent nodes. This method relies on standard graph traversal using a queue and is commonly implemented with Breadth-First Search over an adjacency list.

Approach 2: DFS Coloring (O(V + E) time, O(V) space)

The DFS solution uses the same two-color idea but applies it recursively. Start from an uncolored node, assign a color, then recursively explore its neighbors using Depth-First Search. Each recursive call attempts to color the neighbor with the opposite color. If a conflict occurs (a neighbor already has the same color), immediately return false and propagate the failure up the recursion stack. DFS tends to produce slightly shorter code and works well when recursion depth is manageable. The underlying insight remains identical: adjacent vertices must always have opposite colors.

Alternative Idea: Union-Find Perspective

A less common approach models the constraint using Union Find. For each node, all of its neighbors must belong to the opposite partition. You can union all neighbors of a node together and check that none share the same root as the node itself. While theoretically valid, this implementation is less intuitive than graph coloring and rarely the first choice during interviews.

Recommended for interviews: Use the BFS or DFS two-coloring solution. Interviewers expect you to recognize the bipartite property as a graph coloring problem. Explaining the idea of alternating colors across edges demonstrates strong understanding of graph traversal. BFS is often preferred because it avoids recursion depth issues, while DFS is equally acceptable and slightly more concise.