← Back to Home
Breadth-First Search (BFS)
A graph traversal algorithm that explores neighbors first before moving to the next level of neighbors.
Visualization
Step 1 / 9
Speed:
Details
Analogy
Imagine a ripple effect when you drop a stone in a pond. BFS is like exploring that ripple. You first visit the nodes the stone directly 'hits' (level 1), then all the nodes connected to them (level 2), and so on, spreading out evenly.
Purpose
To explore a graph level by level. It's often used to find the shortest path between two nodes in an unweighted graph.
Use Cases
Finding the shortest path in unweighted graphs (e.g., GPS navigation for fewest turns), web crawlers indexing pages, finding connected components in a graph, and peer-to-peer networking.
Algorithm Steps
Line 1
1
create queue Q
2
mark start as visited
3
Q.enqueue(start)
4
while Q is not empty:
5
node = Q.dequeue()
6
process node
7
for each neighbor of node:
8
if neighbor not visited:
9
mark neighbor as visited
10
Q.enqueue(neighbor)
Current
Executed
Pending
Explanation
What's Happening?
Step 1/9
Start at node A. Add it to the queue of nodes to visit. Queue: [A]
Updates with each step • Clickfor full view
Code Implementation
from collections import deque
def bfs(graph, start_node):
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
current_node = queue.popleft()
print(current_node)
for neighbor in graph[current_node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)