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.