Coding Interview PatternsIs Graph Bipartite?
MediumGraphs

Is Graph Bipartite?

Explanation & Solution

Practice Problem

Description

Given an undirected graph represented as an adjacency list, where graph[i] is a list of nodes that node i is connected to, return true if and only if the graph is bipartite.

A graph is bipartite if the nodes can be partitioned into two sets such that no two adjacent nodes belong to the same set. Equivalently, the graph can be colored with two colors so that every edge connects nodes of different colors.

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 groups such that every edge connects nodes from different groups. For instance, nodes 0, 1, and 2 are all mutually connected, forming a triangle (odd cycle), which makes the graph non-bipartite.

Constraints

  • graph.length == n
  • 1 <= n <= 100
  • 0 <= graph[i].length < n
  • 0 <= graph[i][j] <= n - 1
  • graph[i][j] != i (no self-loops)
  • If graph[i] contains j, then graph[j] contains i (undirected)
  • The graph may be disconnected

Approach

Graphs pattern

1. Initialize a Color Array

  • Create an array color of length n, filled with -1
  • -1 means the node has not been visited yet
  • We will use 0 and 1 as the two colors

2. Iterate Over All Nodes

  • For each node start from 0 to n - 1:
  • If the node is already colored, skip it
  • Otherwise, start a BFS from this node
  • This outer loop ensures we handle disconnected components

3. BFS Coloring

  • Assign color 0 to the starting node and push it into the queue
  • While the queue is not empty:
  • Dequeue the front node
  • For each neighbor of the current node:
  • If the neighbor is uncolored (-1), assign it the opposite color (1 - color[node]) and enqueue it
  • If the neighbor has the same color as the current node, a conflict is found — return false

4. Return True

  • If BFS completes for all components without any conflict, the graph is bipartite — return true

Key Insight

  • A graph is bipartite if and only if it contains no odd-length cycles. BFS naturally explores nodes level by level, alternating colors at each level. If two adjacent nodes end up with the same color, it means there is an odd cycle — making 2-coloring impossible. By running BFS from every unvisited node, we also handle disconnected graphs correctly.

Visualization

Input:
2-Coloring Check4 nodes, 5 edges
0123
output—

Press play to start 2-coloring check

Group AGroup BCurrent
10 steps

Solution Code

Previous
Keys and Rooms
Next
Possible Bipartition