BFS / DFS

Bipartite Check

Can you color the graph with 2 colors such that no adjacent nodes share a color? BFS/DFS and alternate colors. If you ever need to color a node the same color as its neighbor, it's NOT bipartite.

O(V + E)

O(V)

How It Works

A bipartite check asks whether a graph's vertices can be split into two sets with every edge crossing between them — equivalently, whether the graph is 2-colorable. Traverse with BFS or DFS, assigning each newly discovered node the opposite color of the node you came from. Whenever an edge connects two nodes that already share a color, the graph is not bipartite; if the traversal finishes with no conflict, it is.

The theory behind this is clean: a graph is bipartite if and only if it contains no odd-length cycle, and a same-color conflict is exactly the signature of an odd cycle. The check runs in O(V + E) since it is a single traversal, and it must be repeated from every unvisited node to cover disconnected components.

Step-by-Step Visualization

Check if graph is bipartite (2-colorable)

Color[0]Blue

1/3

Code

Java

static boolean isBipartite(int[][] graph) {
  int[] color = new int[graph.length];
  Arrays.fill(color, -1);

  for (int i = 0; i < graph.length; i++) {
    if (color[i] != -1) continue;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(i);
    color[i] = 0;

    while (!queue.isEmpty()) {
      int node = queue.poll();
      for (int nei : graph[node]) {
        if (color[nei] == -1) {
          color[nei] = 1 - color[node];
          queue.add(nei);
        } else if (color[nei] == color[node]) return false;
      }
    }
  }
  return true;
}

Tips & Gotchas

1Try to 2-color the graph using BFS or DFS

2Color a node, then color all neighbors with the opposite color

3If a neighbor already has the same color, it's not bipartite

Practice Problems

1Is Graph Bipartite?
2Possible Bipartition
3Divide Nodes Into the Maximum Number of Groups

About the BFS / DFS Pattern

The two fundamental ways to explore a graph. DFS goes as deep as possible before backtracking (uses a stack or recursion). BFS explores all neighbors first before going deeper (uses a queue). Both visit every node exactly once.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

Why does an odd cycle make a graph non-bipartite?

Colors must alternate along any path, so a cycle returns to its start having flipped color once per edge. After an odd number of flips the start node would need both colors at once, which is a contradiction. Even cycles alternate cleanly and cause no conflict.

Does it matter whether I use BFS or DFS for two-coloring?

No — correctness only requires that every edge is checked for a color conflict, which both traversals do. Pick whichever you write more comfortably; just remember to restart the coloring from every unvisited node so disconnected components are covered.