BFS vs DFS: When to Use Which?

BFS explores nodes in order of distance from the start, so it is the right choice whenever the answer depends on distance: shortest path in an unweighted graph, fewest edges between two nodes, or the order in which things become reachable. DFS goes as deep as possible before backtracking, so it is the right choice for cycle detection, topological sorting, connected components, and exhaustive search such as backtracking.

from collections import deque


def bfs_distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in distance:
                distance[neighbour] = distance[node] + 1
                queue.append(neighbour)
    return distance


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

The output shows A at distance zero, B and C at distance one, and D at distance two, which is the shortest number of edges from A to D.

The mechanism is the order in which the frontier is expanded. BFS keeps a queue of the nodes discovered but not yet processed, and because it always expands the oldest one, every node at distance k is processed before any node at distance k plus one. DFS uses a stack instead, so the newest node is expanded next and the search dives down one branch as far as it can go.

The trade-off to name is memory. BFS holds as many nodes as the widest level of the graph, while DFS holds as many as the longest path, so on a wide shallow graph BFS is expensive and on a narrow deep graph DFS is. That is why the iterative DFS is usually written with an explicit stack rather than recursion, because a recursive DFS can blow the Python call stack on a deep graph.

Take a node, mark it as visited, and then recurse into each of its unvisited neighbours. The order matters: marking a node as visited when you first reach it, rather than when you expand it, is what stops a graph with cycles from recursing forever.

def dfs(graph, start, seen=None):
    if seen is None:
        seen = set()
    seen.add(start)
    order = [start]
    for neighbour in graph[start]:
        if neighbour not in seen:
            order.extend(dfs(graph, neighbour, seen))
    return order


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

The output is A, B, D, C. From A the traversal goes to B first, then to D, and only then backtracks to C, because D was already visited by the time C was reached.

The mechanism is the recursion stack acting as the frontier. Each recursive call pushes a node onto the stack, and the search continues from the most recently added node, so one branch is explored to its end before any sibling is considered. The visited set is shared across the whole traversal, which is why it is passed as an optional argument rather than created fresh at each level.

The trade-off to name is that this recursive version uses stack space proportional to the depth of the graph, so a long chain of nodes can exceed the Python recursion limit. Writing the same traversal with an explicit stack avoids that at the cost of a slightly less natural implementation, since the order in which you push the neighbours determines whether the result matches the recursive order exactly. If you only need the set of reachable nodes rather than an order, a set and a stack is all you need and the recursion is not worth it.

Run BFS from the start node and keep the path with each queued node. When the goal is dequeued, the path stored with it is the shortest one.

from collections import deque


def shortest_path(graph, start, goal):
    queue = deque([(start, [start])])
    seen = {start}
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append((neighbour, path + [neighbour]))
    return None


graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": [], "E": []}
print(shortest_path(graph, "A", "E"))

The output is A, C, E. The path through B and D would be three edges long, while the path through C is two, so the shorter one is returned.

The mechanism is that BFS processes nodes in non-decreasing order of distance from the start. A node at distance k is only dequeued after every node at distance less than k has been dequeued, so the first time the goal is reached it has been reached by a shortest path. That property is exactly what DFS lacks, which is why the search order matters so much here.

The trade-off to name is the cost of carrying the path with each queued node, which copies the path for every neighbour and so uses quadratic time in the path length. The standard fix is to remember only the parent of each node and reconstruct the path once at the end, which is linear in the number of nodes. The other point is that this whole argument relies on every edge having the same cost. With weighted edges you need Dijkstra's algorithm or A star instead, because BFS would find a path with the fewest edges rather than the least total weight.