Breadth-First Search (BFS)
Visualize Breadth-First Search (BFS). Learn how to traverse graphs layer by layer using a Queue. Essential for finding shortest paths in unweighted graphs.
Ready to start
Queue (FIFO)
Traversal Order
Intuition
Imagine dropping a stone in a calm pond.
Ripples generated by the stone move outward in concentric circles.
BFS works similarly: starting from a source node, it visits all immediate neighbors (first ripple), then neighbors of neighbors (second ripple), and so on.
Concept
Breadth-First Search (BFS) is a graph traversal algorithm that explores the neighbor nodes first, before moving to the next level neighbors.
It uses a Queue (First-In-First-Out) data structure to keep track of nodes to explore.
How it Works
- Enqueue the starting node and mark it as visited.
- While the Queue is not empty:
- Dequeue a node (let's call it current).
- Visit current.
- Enqueue all unvisited neighbors of current and mark them as visited.
Step-by-Step Breakdown
Watch the visualization above:
- Orange (Primary-500) Node: Currently being processed.
- Dark Orange (Primary-300) Nodes: In the Queue (waiting to be visited).
- Emerald (Emerald-500) Nodes: Completely visited.
Legend
Current / Processing
In Queue / Stack
Visited
When to Use
Use BFS when:
- Finding the shortest path in an unweighted graph (e.g., fewest hops to reach a destination).
- Finding all nodes within a certain distance from a source (e.g., friends of friends).
- Level-order traversal of a tree.
When NOT to Use
- Memory Constraints: BFS stores all nodes at the current level, which can be memory-intensive for wide graphs.
- Weighted Graphs: For shortest paths in weighted graphs, use Dijkstra's Algorithm instead.
How to Identify
Problems asking for "shortest path", "least number of steps", or "nearest neighbor" usually imply BFS.
Frequently Asked Questions
Why use a Queue for BFS?
A Queue ensures FIFO (First-In-First-Out) order, which naturally explores all neighbors at the current depth before moving to the next level.
BFS vs DFS traversal?
BFS explores "wide" and finds the shortest path in unweighted graphs. DFS explores "deep" and is often used for topological sorting or connectivity.
Real-world uses of BFS?
Searching in peer-to-peer networks (Gnutella), finding the shortest path on GPS maps, and social network friend suggestions.