Breadth-First and Depth-First Are the Same Loop, One Line Apart

Breadth-first and depth-first search are usually introduced as two algorithms with different personalities: one spreads out in rings, the other plunges. Then BFS gets written iteratively with a queue and DFS gets written recursively, and the two programs look nothing like each other.

They are the same program. Both keep a frontier of nodes waiting to be visited, both mark nodes as visited, both push unvisited neighbours. The entire difference is which end of the frontier the next node is taken from.

Take it from the front and the frontier is a queue: breadth-first. Take it from the back and it is a stack: depth-first. One line.

Watch the frontier

Choose which end to read from, then step. Dashed circles are on the frontier; filled ones have been visited; the number beside each node is the order it was visited in.

Run it once each way and compare the Path to Z line. Breadth-first gets there in two hops. Depth-first gets there in five, on the same graph, from the same start.

Why breadth-first finds the shortest route

Because it finishes every node at distance 1 before it touches any node at distance 2, and every node at distance 2 before any node at distance 3. A queue enforces that: nodes come out in the order they went in, so a node discovered early is expanded early. The first time breadth-first reaches a node, it cannot have arrived by a longer route than necessary — a shorter one would have been finished already.

Depth-first makes no such promise, and it is easy to see why once the frontier is visible. It commits to the most recently discovered node, which means it follows one corridor to its end before reconsidering. On this graph, that corridor is the long way round. Depth-first does not reject the short route — it simply never looks at it until it has exhausted everything else.

That is why the standard advice holds: use breadth-first when you care about the shortest path in an unweighted graph. For “is there any route at all”, or for problems that naturally recurse like exploring every arrangement, depth-first is fine and uses far less memory.

Both searches, one function

The take_from_back flag is the whole difference. There is no second algorithm anywhere in this program.

from collections import deque

EDGES = [("A", "B"), ("B", "Z"),
         ("A", "C"), ("C", "D"), ("D", "E"), ("E", "F"), ("F", "Z"),
         ("B", "D")]

adj = {}
for a, b in EDGES:
    adj.setdefault(a, []).append(b)
    adj.setdefault(b, []).append(a)
for node in adj:
    adj[node].sort()


def search(start, take_from_back):
    """The SAME loop for both searches. take_from_back=False is breadth-first, True is depth-first."""
    frontier = deque([start])
    visited, parent = [], {start: None}
    while frontier:
        node = frontier.pop() if take_from_back else frontier.popleft()
        if node in visited:
            continue
        visited.append(node)
        for nb in adj[node]:
            if nb not in visited:
                frontier.append(nb)
                parent.setdefault(nb, node)
    return visited, parent


def path(parent, target):
    out, cur = [], target
    while cur is not None:
        out.append(cur)
        cur = parent[cur]
    return list(reversed(out))


for name, take_from_back in [("breadth-first", False), ("depth-first", True)]:
    visited, parent = search("A", take_from_back)
    route = path(parent, "Z")
    print(f"{name:<14} frontier read from the {'back (stack)' if take_from_back else 'front (queue)'}")
    print(f"{'':<14} visit order: {' '.join(visited)}")
    print(f"{'':<14} reached Z by {' -> '.join(route)} ({len(route) - 1} hops)")

breadth-first  frontier read from the front (queue)
               visit order: A B C D Z E F
               reached Z by A -> B -> Z (2 hops)
depth-first    frontier read from the back (stack)
               visit order: A C D E F Z B
               reached Z by A -> C -> D -> E -> F -> Z (5 hops)

Note the visit orders. Breadth-first reaches Z fifth but by the shortest route; depth-first reaches it sixth by a route more than twice as long. Arriving early and arriving cheaply are different things, and only one of the two searches guarantees the second.

Where recursion comes in

Depth-first is usually written recursively, and that version has no visible stack at all — which is exactly why the connection gets lost. The stack is still there. It is the call stack: each recursive call is a frame holding the node it is working on, and returning from a call is popping the frontier.

So the recursive version is not a different algorithm from the iterative one. It is the same algorithm using the language’s stack instead of one you declared. That is also its practical limit: a deep enough graph overflows the call stack, where an explicit stack would simply grow.

What this page simplifies

• Unweighted edges only. Breadth-first finds the fewest hops. When edges carry different costs, fewest hops and cheapest route stop being the same thing, and you need Dijkstra’s algorithm — which is this loop again with the frontier as a priority queue.
• Undirected, connected, small. Directed graphs, disconnected components and cycles all introduce real complications this graph avoids on purpose.
• Neighbours are visited alphabetically. Any fixed order works, but the order determines the exact route depth-first takes, so it is pinned here to keep two runs comparable.
• node in visited is a list scan. Written for readability; a real implementation uses a set, which is the difference between a linear and a constant-time membership test.