BFS Using a Queue —
Level by level. FIFO drives everything.
Breadth-First Search explores a graph or tree level by level — visiting all nodes at distance 1 before distance 2, distance 2 before distance 3. The queue is what enforces this. Watch nodes enqueue their neighbours and dequeue in order on LearnBug and BFS stops feeling like magic.
Why does BFS use a queue?
BFS must visit nodes in the order they were discovered — the first node found is the first processed. That's FIFO (First In, First Out), which is exactly what a queue provides. When you dequeue a node, you enqueue all its unvisited neighbours. Because neighbours are enqueued after the current level, they're processed after the current level — level-by-level order is guaranteed.
Why visualization changes everything
Trying to trace BFS by hand — which nodes are visited, which are queued, which level are we on — is error-prone and slow. On LearnBug the queue contents are visible at every step alongside the graph, and nodes light up as they're visited. The level-by-level wave pattern becomes visually obvious.
BFS on a simple graph from node A
Graph: A→B, A→C, B→D, B→E, C→F. Visit order should be: A, B, C, D, E, F
Start — enqueue A, mark visited
Push A into the queue. Mark as visited so we don't process it again. Queue holds the frontier — all nodes discovered but not yet processed.
Dequeue A — enqueue B and C (A's neighbours)
Process A. A's unvisited neighbours are B and C — enqueue both, mark visited. Queue now holds level 1 nodes.
Dequeue B — enqueue D and E (B's neighbours)
Process B. B's unvisited neighbours are D and E — enqueue both. C is still in queue, waiting. Level 2 nodes (D, E) join the queue behind C.
Dequeue C — enqueue F. Then D and E dequeue with no new neighbours.
C's neighbour F is enqueued. D and E have no unvisited neighbours — they dequeue cleanly. F is the last node to process.
Dequeue F — queue empty. BFS complete.
F has no unvisited neighbours. Queue is empty — BFS is done. Visit order: A → B → C → D → E → F. Exactly level by level.
BFS — graph and grid versions
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
order = []
while queue:
node = queue.popleft() # dequeue from front — FIFO
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour) # enqueue to back
return orderdef bfs_grid(grid, start_r, start_c):
rows, cols = len(grid), len(grid[0])
visited = set([(start_r, start_c)])
queue = deque([(start_r, start_c)])
dirs = [(-1,0), (1,0), (0,-1), (0,1)]
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and
0 <= nc < cols and
(nr, nc) not in visited):
visited.add((nr, nc))
queue.append((nr, nc))Time & Space Complexity
Frequently asked questions
Why does BFS guarantee the shortest path in an unweighted graph?
BFS visits nodes in strictly increasing order of distance from the source. The first time a node is reached, it's reached via the fewest edges possible — any alternative path would require the same or more steps. Once a node is marked visited on first discovery, that distance is optimal and we never update it.
What is the difference between BFS and DFS?
BFS uses a queue (FIFO) and explores level by level — good for shortest path and level-order traversal. DFS uses a stack (LIFO, often via recursion) and dives deep before backtracking — good for cycle detection, topological sort, and finding all paths. BFS uses more memory (wide frontier); DFS uses less (thin path).
Why must we mark nodes visited before enqueuing, not after dequeuing?
If you mark visited on dequeue, the same node can be enqueued multiple times by different neighbours before it's processed. This wastes memory and can cause infinite loops in cyclic graphs. Marking visited immediately on enqueue ensures each node enters the queue exactly once.
How do I find the shortest path distance with BFS?
Store distances in a dict: dist[start] = 0. When enqueuing a neighbour, set dist[neighbour] = dist[node] + 1. The distance when a node is first enqueued is its shortest distance. Alternatively, process level by level with a counter that increments after each full level is dequeued.
What are common LeetCode problems that use BFS?
Number of Islands (LC 200), Rotting Oranges (LC 994), Word Ladder (LC 127), Shortest Path in Binary Matrix (LC 1091), Binary Tree Level Order Traversal (LC 102), and Clone Graph (LC 133). If the problem asks for "shortest" or "minimum steps" in an unweighted setting — BFS is almost always the answer.
Watch the queue drive level-by-level exploration
Paste your graph into LearnBug and see BFS enqueue and dequeue every node step by step.