Breadth-first search (BFS)

The idea: ripples in water

Drop a stone in a pond and the ripples spread in rings: first the ring closest to the stone, then the next ring, and so on. Breadth-first search (BFS) explores a graph the same way. It visits the start, then every vertex one edge away, then every vertex two edges away. Nothing at distance 3 is visited before everything at distance 2.

The queue and the visited set

BFS keeps a queue: a line where items join at the back and leave from the front (first in, first out). In Python use collections.deque, whose popleft() is O(1). A plain list with pop(0) shifts every item, which is O(n) per pop.

Graphs can have cycles, so BFS also keeps a visited set: the vertices it has already put in the queue. Mark a vertex as visited WHEN YOU ADD IT to the queue, not when you take it out. Otherwise the same vertex can be added many times by different neighbours before it is processed.

from collections import deque

def bfs_dist(adj, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in dist:          # dist doubles as the visited set
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

adj = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
print(bfs_dist(adj, 0))   # Output: {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}

Every vertex enters the queue at most once and every edge is looked at once from each end, so BFS takes O(V + E) time with an adjacency list. The queue and the visited set take O(V) extra space.

Why BFS finds shortest paths

Because BFS works layer by layer, the first time it reaches a vertex is along a path with the fewest possible edges. So in an unweighted graph, dist[v] is the shortest distance from the start. "Fewest metro stops from Andheri to Churchgate" or "fewest connections between two people" are BFS questions. When edges have different weights (km, minutes, rupees), BFS is no longer enough; topic 5 covers Dijkstra.

Grids are graphs too

In a grid problem, each cell is a vertex and its neighbours are the cells up, down, left and right. You do not build an adjacency list; you compute neighbours on the fly with a list of four direction steps, checking that the new cell is inside the grid and not a wall. A grid with R rows and C columns has R × C vertices, so BFS costs O(R × C).

DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dr, dc in DIRS:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#":
        ...   # (nr, nc) is a neighbour you may visit

Multi-source BFS

Sometimes the spreading starts from many places at once. In the "rotting oranges" problem, every rotten orange makes its fresh neighbours rotten each minute. Put ALL the rotten oranges in the queue at minute 0, then run one BFS. Each layer is one minute. This is far faster than running a separate BFS from every source, and it answers "distance to the NEAREST source" for every cell.

To count layers, process the queue one layer at a time: for _ in range(len(queue)) pops exactly the vertices of the current layer, then you add 1 to the layer count.

Common mistakes

• Marking visited when a vertex is popped instead of when it is pushed. The answer may still be right, but vertices get queued many times. Fix: mark on push.
• Using list.pop(0) for the queue, which makes BFS O(V²) on big inputs. Fix: deque and popleft().
• Forgetting the case start == target, where the answer is 0. Fix: check it first, or let dist[start] = 0 answer it.
• Indexing grid[nr][nc] before checking 0 <= nr < rows. Negative indexes wrap around in Python, so the bug is silent. Fix: check bounds first.
• Mixing up "number of moves" and "number of cells on the path" (they differ by 1). Fix: read the prompt and test on a 1 × 1 grid.
• Using BFS on a graph with different edge weights. Fix: Dijkstra (topic 5).