🎓 A1Learner
🔍
0 of 47 lessons completed

Choosing Between BFS and DFS

Choosing between BFS and DFS is matching the walk to the question being asked. The two walks reach the same nodes, but they reach them in different orders.

Recognition signal

The question itself picks the walk. Fewest steps points to breadth-first search, while exploring a full branch points to depth-first search.

signals = [
    "Fewest steps: breadth-first search.",
    "Whole branch: depth-first search.",
    "Only reachable or not: either walk."
]
for line in signals:
    print(line)

Template: both walks side by side

Running both walks on the same graph shows the order difference plainly. Breadth-first search spreads level by level, while depth-first search dives down one branch.

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": [],
    "E": []
}

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return order

def dfs(graph, node, seen, order):
    seen.add(node)
    order.append(node)
    for nxt in graph[node]:
        if nxt not in seen:
            dfs(graph, nxt, seen, order)
    return order

print("BFS:", bfs(graph, "A"))
print("DFS:", dfs(graph, "A", set(), []))

Worked problem: fewest steps

Breadth-first search records a distance for each node when it is first seen. The first time the target is seen, its distance is the fewest steps possible.

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": ["E"],
    "E": []
}

def fewest_steps(graph, start, target):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist[target]

print("Steps:", fewest_steps(graph, "A", "E"))

Example

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["E"],
    "D": ["F"],
    "E": ["F"],
    "F": []
}

def find_path(graph, node, target, seen):
    seen.add(node)
    if node == target:
        return [node]
    for nxt in graph[node]:
        if nxt not in seen:
            path = find_path(graph, nxt, target, seen)
            if path:
                return [node] + path
    return []

print(find_path(graph, "A", "F", set()))

Key points

  • Breadth-first search: a walk that visits nodes level by level from the start.
  • Depth-first search: a walk that follows one branch as far as it goes before backtracking.
  • Use breadth-first search to find the fewest steps between two nodes.
  • Use depth-first search to explore a whole branch or to find any path to a target.

The question asks for any path, not the shortest one, so depth-first search fits. The walk dives from A to B to D and reaches F. The returned path is A, B, D, F.

Note

when the question only asks whether a node is reachable, either walk gives the answer.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A question asks for the fewest edges between two nodes. Which walk fits best?