Breadth-First Search (BFS) is a fundamental graph traversal algorithm that explores all nodes at the current depth level before moving to nodes at the next depth level. It's like exploring a building floor by floor, visiting every room on one floor before going to the next.
In this comprehensive guide, you'll learn how BFS works with simple tree examples, step-by-step visualizations, code implementations, and real-world use cases. We'll make it easy to understand without complex math or jargon.
💡 Quick Tip
Use our free JSON Validator to validate tree structures and our JSON Formatter to visualize hierarchical data.
Definition: What Is Breadth-First Search?
Breadth-First Search (BFS) is a graph traversal algorithm that visits all nodes at the current level (depth) before moving to nodes at the next level. It uses a queue data structure to keep track of nodes to visit next.
Key characteristics of BFS:
Level-by-Level
Visits nodes level by level, not depth by depth
Uses Queue
FIFO (First In First Out) structure
Finds Shortest Path
In unweighted graphs, finds shortest path
Complete Search
Visits all reachable nodes
Real-World Analogy
Imagine you're searching for a friend in a building. BFS is like checking every room on the 1st floor first, then every room on the 2nd floor, then the 3rd floor, and so on. You explore level by level, not room by room going deep into one area first.
What Does BFS Do?
BFS systematically explores a graph or tree by:
1. Starting at the Root
Begins at a starting node (usually the root in trees)
2. Visiting Level by Level
Visits all nodes at distance 1, then distance 2, then distance 3, etc.
3. Using a Queue
Maintains a queue of nodes to visit, processing them in order
4. Marking Visited Nodes
Keeps track of visited nodes to avoid revisiting them
When to Use BFS?
Use BFS in these scenarios:
Finding shortest path - In unweighted graphs, BFS finds the shortest path
Level-order traversal - When you need to process nodes level by level
Social network analysis - Finding connections within N degrees of separation
Web crawling - Exploring websites level by level
Puzzle solving - Finding minimum moves to solve puzzles
How BFS Works: Step-by-Step Example
Example Tree
BFS Traversal Steps
Start: Queue = [1], Visited =
Visit node 1, add its children (2, 3) to queue
Process: Queue = [2, 3]
Visit node 2, add its children (4, 5) to queue
Process: Queue = [3, 4, 5]
Visit node 3, add its children (6, 7) to queue
Process: Queue = [4, 5, 6, 7]
Visit nodes 4, 5, 6, 7 (no children to add)
Result: BFS Order = [1, 2, 3, 4, 5, 6, 7]
All nodes visited level by level!
BFS Code Implementation
BFS Algorithm Flow
Initialize Queue with Root
Queue = [root], Visited =
Is Queue Empty?
Return result
Process next node
Dequeue Node
Remove from front of queue
Mark as Visited & Process
Add to result, mark visited
Enqueue Children
Add unvisited children to end of queue
Repeat Until Queue Empty
Go back to check queue
BFS Time & Space Complexity
| Metric | Complexity | Explanation |
|---|---|---|
| Time Complexity | O(V + E) | V = vertices (nodes), E = edges. Visit each node once, check each edge once |
| Space Complexity | O(V) | Queue can hold at most all nodes at the widest level |
| For Tree (V nodes) | O(V) | In trees, E = V-1, so O(V + E) = O(V) |
Why Use BFS?
Shortest Path
Finds shortest path in unweighted graphs (minimum number of edges)
Level Order
Natural for level-order traversal, perfect for tree printing
Complete Search
Visits all reachable nodes, guaranteed to find solution if exists
Simple Implementation
Uses simple queue, easy to understand and implement
Real-World BFS Applications
1. Shortest Path Finding
Finding minimum steps in unweighted graphs (maze solving, game AI)
Example: Finding shortest path in a maze, minimum moves in chess
2. Social Network Analysis
Finding connections within N degrees (LinkedIn connections, friend suggestions)
Example: "People you may know" feature, finding mutual connections
3. Web Crawling
Crawling websites level by level (search engine indexing)
Example: Googlebot crawling pages, exploring website structure
4. Level-Order Tree Printing
Printing tree nodes level by level (binary tree visualization)
Example: Displaying directory structure, printing organizational chart