The Four Core Patterns of BFS
Understanding BFS Patterns
Breadth-First Search can be applied to a wide variety of problems, but most of them follow one of these four core patterns.
Each pattern represents a different way of thinking about and applying BFS to solve problems.
Level Order Traversal Pattern
Bipartite Graph Pattern
Learning Objective
Understand the core patterns of breadth-first search and how they can be applied to solve different types of problems.
The Four Core Patterns of Breadth-First Search
While breadth-first search can be applied to many different problems, most solutions follow one of these four core patterns. Understanding these patterns will help you recognize when and how to apply BFS to new problems.
Shortest Path Pattern
Find the shortest path between two vertices in an unweighted graph, where the path with the fewest edges is guaranteed to be the shortest.
Examples: Shortest path in a maze, Word ladder problem
Level Order Traversal Pattern
Traverse a tree level by level, visiting all nodes at each level before moving to the next level, useful for problems requiring level-wise processing.
Examples: Level order traversal, Zigzag traversal, Right side view
Connected Components Pattern
Find all connected components in an undirected graph by running BFS from each unvisited vertex, useful for analyzing graph structure.
Examples: Number of islands, Friend circles
Bipartite Graph Pattern
Check if a graph is bipartite by coloring vertices such that no adjacent vertices have the same color, useful for problems involving binary relationships.
Examples: Possible bipartition, Is graph bipartite
Choosing the Right Pattern
When faced with a problem that might be solved using breadth-first search, ask yourself these questions to identify the most appropriate pattern:
For Shortest Path Pattern
"Am I looking for the shortest path between two points in an unweighted graph? Do I need to find the minimum number of steps to reach a target?"
For Level Order Traversal Pattern
"Am I working with a tree or hierarchical structure? Do I need to process elements level by level or group them by their distance from the root?"
For Connected Components Pattern
"Do I need to find or count distinct groups in a graph? Am I looking for isolated regions or clusters in a grid or network?"
For Bipartite Graph Pattern
"Does the problem involve dividing elements into two groups with specific relationship constraints? Can the problem be modeled as a graph coloring problem?"