🎓 A1Learner
🔍
0 of 47 lessons completed

Breadth-First Search in Interviews

Breadth-first search is a search that visits neighbours level by level. It finishes one level before it moves to the next level.

Spot the signal

A problem asks for the nearest item or the fewest steps. The start node and its neighbours form the first two levels.

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print("start: A")
print("neighbours of A:", graph["A"])

The template

A queue holds waiting nodes, and a visited set stops repeats. Nodes leave the queue in level order.

from collections import deque
def bfs(graph, start):
    seen = {start}
    order = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append(neighbour)
    return order
graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": ["G"], "E": [], "F": [], "G": []}
print(bfs(graph, "A"))

Worked problem: steps to a node

Track the step count beside each node in the queue. The count at the target is the fewest steps.

from collections import deque
graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": ["G"], "E": [], "F": [], "G": []}
def steps_to(graph, start, target):
    seen = {start}
    queue = deque([(start, 0)])
    while queue:
        node, steps = queue.popleft()
        if node == target:
            return steps
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append((neighbour, steps + 1))
    return -1
print(steps_to(graph, "A", "G"))

Example

from collections import deque
graph = {"A": ["B", "C"], "B": ["D", "E"], "C": ["F"], "D": ["G"], "E": [], "F": [], "G": []}
levels = {"A": 0}
queue = deque(["A"])
while queue:
    node = queue.popleft()
    for neighbour in graph[node]:
        if neighbour not in levels:
            levels[neighbour] = levels[node] + 1
            queue.append(neighbour)
print(levels)

Key points

  • Level: a set of nodes at the same step distance from the start.
  • Use breadth-first search when a problem asks for the shortest path in steps.
  • A queue holds the nodes waiting to be visited, oldest first.
  • Mark a node visited when it joins the queue, so it is never queued twice.
  • The first visit to a node uses the fewest steps from the start.
  • Breadth-first search spreads outward one level at a time.

The code records the level of each node as it joins the queue. A neighbour sits one level past its parent node. The map gives every level in one pass.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Which structure holds the waiting nodes in breadth-first search?