Course contentsShow
← Computer Science
Lesson 703 of 2,87217. Graph Traversal AlgorithmsFree lesson

BFS for Bipartiteness Testing

Determining if a graph is bipartite: two-coloring algorithm using BFS, detecting odd cycles.

BFS for Bipartiteness Testing

What you'll learn: How to use BFS to determine if a graph can be split into two independent groups with a two-coloring algorithm.

The Core Idea

A bipartite graph is one where you can divide all vertices into two groups such that every edge connects a vertex from one group to a vertex in the other group—no edges exist within a group. Think of it like a dance: if every person from Team A only dances with people from Team B (and vice versa), you have a bipartite arrangement.

The key insight: a graph is bipartite if and only if it contains no odd-length cycles. We can test this using BFS with a "two-coloring" approach.

The Two-Coloring Algorithm

Start BFS from any unvisited vertex, coloring it with Color 0. As you visit neighbors:

  • Color each neighbor with the opposite color (if the parent is Color 0, child gets Color 1)
  • If you encounter a neighbor already colored with the same color as the current vertex, you've found an odd cycle—the graph is not bipartite
  • If BFS completes without conflicts, that component is bipartite

Since graphs may have multiple components, repeat this process for all unvisited vertices.

Why It Works

BFS assigns colors level-by-level. In a bipartite graph, all vertices at even distances from the start get one color, all at odd distances get the other. If you ever try to color a vertex and find it already has the wrong color, you've discovered an odd cycle (like a triangle), which violates the bipartite property.

Key Takeaway: BFS can test bipartiteness by attempting to two-color the graph; any coloring conflict reveals an odd cycle and proves the graph is not bipartite. This runs in O(V + E) time using the standard BFS traversal structure with parent tracking.