Coding Pattern:
Graph Breadth First Search
This pattern has an earnable cheat sheet.
Note
🛑 We strongly suggest familiarizing yourself with the graph and deque data structures before proceeding past this section.
We also suggest practicing the Tree Breadth First Search section before practicing graph breadth first search.
Pattern concept
Step 1 of 38
Use ← → arrow keys
Code snippets
How to identify
Does the problem involve any of these?
- Find shortest path (BFS is perfect since it explores nodes level by level)
- Word Ladder: Find the shortest sequence of word transformations between two words.
- Find whether two nodes are connected
- Find if Path Exists in Graph: Find if two nodes can reach each other.
- The Maze: Find whether there the ball can reach from start to destination nodes.
- Traverse a form of a graph (including a maze or grid) level by level
- Flood Fill: Change neighboring pixel colors level by level.
Note
It usually takes O(n) time and O(n) space to traverse the graph, where n is the number of nodes in the graph.