Breadth-First Search

First PublishedFeb 11, 2026ByAtif Alam

Difficulty: Easy. ROI: High.

Other common names: BFS, level-order traversal (on trees).

When to use: Use when you need shortest path in an unweighted graph, or to process a tree/graph level by level (e.g. “minimum steps to reach target,” level-order traversal).

Idea: Use a queue. Start with the source in the queue. Repeatedly dequeue a node, process it, and enqueue its unvisited neighbors. Ensures you visit nodes in order of increasing distance from the source.

Time / space: O(V + E) for graph with V vertices and E edges; O(n) for a tree with n nodes. Space O(n) for the queue.

Example #1 — Shortest Path in Unweighted Graph

Find the minimum number of edges from start to end by exploring level by level with a queue. First time we reach a node, we have the shortest path to it.

Sample input and output

1
graph = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}
2
print(bfs_shortest_path(graph, 1, 4))  # 2  (path 1 → 2 → 4)
3
print(bfs_shortest_path(graph, 1, 1))   # 0

Sample input: graph = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2]}, start 1, end 4.
Sample output: 2 — shortest path from 1 to 4 has 2 edges (1 → 2 → 4).

Code (with inline comments)

1
from collections import deque
2

3
def bfs_shortest_path(graph, start, end):
4
    queue = deque([(start, 0)])  # (node, distance); FIFO so we explore by level
5
    seen = {start}
6
    while queue:
7
        node, dist = queue.popleft()  # take next node (smallest distance so far)
8
        if node == end:
9
            return dist
10
        for neighbor in graph[node]:
11
            if neighbor not in seen:
12
                seen.add(neighbor)
13
                queue.append((neighbor, dist + 1))  # one step further
14
    return -1

Line-by-line:

from collections import deque — A deque (double-ended queue) supports fast append and pop from both ends. We use it as a FIFO queue: we add neighbors at the back and always take from the front, so we process nodes in order of increasing distance.
queue = deque([(start, 0)]) — We start with the start node and distance 0. The queue holds pairs (node, distance_from_start).
seen = {start} — A set of nodes we’ve already added to the queue (or processed). We skip a neighbor if it’s already in seen, so we don’t revisit nodes and the first time we see a node we have the shortest path to it.
while queue: — Keep processing until the queue is empty (then we’ve reached everything reachable and didn’t find end).
node, dist = queue.popleft() — Take the next node from the front of the queue. Because we always push nodes with distance dist+1, we process nodes in order of distance (level by level).
if node == end: return dist — We reached the target; the distance we stored is the shortest path length.
for neighbor in graph[node]: — Look at every neighbor of the current node. graph[node] is the list of nodes connected to node (adjacency list).
if neighbor not in seen: — Only add a neighbor we haven’t seen yet; that way we never overwrite a shorter distance.
seen.add(neighbor); queue.append((neighbor, dist + 1)) — Mark as seen and add to the back of the queue with distance one more than the current node.

Execution trace (numbered list)

For start=1, end=4:

Step 0: queue=[(1,0)], seen = {1}.
Step 1: Pop (1,0). 1≠4. Add 2, 3 → queue=[(2,1),(3,1)], seen = {1, 2, 3}.
Step 2: Pop (2,1). 2≠4. Add 4 → queue=[(3,1),(4,2)], seen = {1, 2, 3, 4}.
Step 3: Pop (3,1). 3≠4; 4 already in seen, skip. queue=[(4,2)].
Step 4: Pop (4,2). 4==4 → return 2.

Execution trace (code with step comments)

1
# Step 0: queue=[(1,0)], seen={1}
2
# Step 1: popleft (1,0), add (2,1),(3,1) → queue=[(2,1),(3,1)], seen={1,2,3}
3
# Step 2: popleft (2,1), add (4,2) → queue=[(3,1),(4,2)], seen={1,2,3,4}
4
# Step 3: popleft (3,1), 4 in seen → skip
5
# Step 4: popleft (4,2), node==end → return 2

Execution trace (ASCII diagram)

Levels from start; we process by distance and return when we hit end.

1
Graph:  1 --- 2 --- 4
2
        |
3
        3
4

5
Level 0: [1]
6
Level 1: [2, 3]
7
Level 2: [4]  → first time we see 4, return dist=2