BFS vs DFS

The loop body is identical. You are staring at for neighbor in graph[node] and the only open question is what to put around it — and that one choice decides whether you get the shortest route or merely a route, and whether you run out of memory or run out of stack. Both questions have the same answer, because BFS and DFS are the same walk over the same graph — the only thing that changes is which end of a list a single call pops from.

Breadth-first and depth-first, one line of code apart#

Both searches keep a frontier: a list of nodes that have been discovered but not yet processed. Each pass takes one node out of the frontier, records it, and adds its unvisited neighbours to the frontier for a later pass. Nothing about that shape says which end of the list to take from — that choice is the entire difference between the two algorithms.

def bfs(start, graph):
    order, seen = [], {start}
    frontier = [start]
    while frontier:
        node = frontier.pop(0)        # oldest node in the frontier
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                frontier.append(neighbor)
    return order

def dfs(start, graph):
    order, seen = [], {start}
    frontier = [start]
    while frontier:
        node = frontier.pop()         # newest node in the frontier
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                frontier.append(neighbor)
    return order

pop(0) takes the oldest node added to the frontier — everything one step away gets processed before anything two steps away is even looked at, which is breadth-first search. pop() takes the newest node — the search commits to whatever it just found and keeps going deeper on that branch, which is depth-first search. The printed BFS pays for that simplicity, though: pop(0) shifts every remaining element of a plain Python list, so this version costs O(V² + E) rather than the O(V + E) the algorithm itself does — the O(n) shifting cost a deque would not pay. The level-order walk in tree-traversal-orders is breadth-first search under a tree-shaped name, and that article already covers why that one order needs a queue instead of the call stack a tree traversal usually gets for free.

One caveat with the stack-based form above: it does not reproduce recursive DFS’s visit order, and pushing each node’s neighbours in reverse is not enough to make it. The version above marks a node seen the moment it is pushed, so the first branch to discover a node claims it — even when recursion would have arrived there later, down a different branch, and counted it there instead. On a tree nothing is ever discovered twice, so the reversed push alone does match; it is cross edges that break it. Matching recursion on a general graph means moving the bookkeeping as well: mark a node visited when you pop it, skip anything already recorded, and push neighbours in reverse. The frontier then holds the same node more than once for a while, which is the price of letting the last branch to reach a node be the one that owns it. Either way the same nodes get visited at the same asymptotic cost — but a test that checks the exact sequence will catch the difference.

Why only one of them finds the shortest path#

BFS’s queue empties in the order nodes were discovered, which means it finishes every node at distance one from the start before a single node at distance two is even added to the frontier. Depth n is exhausted before depth n+1 begins, every time, because nothing can jump the line. The first time BFS’s queue produces a given node is therefore guaranteed to be by the fewest possible edges — there is no shorter path it could have missed, because a shorter path would have reached the frontier first.

DFS makes no such promise. It commits to one branch and rides it to the end before backing up, so the first path it finds to a node is whatever path that branch happened to take — it can be the shortest one, or it can wander far out of the way first. “Found first” and “fewest edges” are unrelated facts about DFS; they are the same fact about BFS.

That guarantee is specifically about edges, not cost, and it disappears the moment edges carry weights. Fewest edges and cheapest path stop being the same question once one edge can cost 1 and another can cost 100 — a plain queue has no way to prefer the expensive-looking detour that turns out cheaper overall, because it only ever tracks arrival order, never accumulated cost. That is exactly the gap Dijkstra’s algorithm fills: the same frontier idea, with the queue replaced by a priority queue ordered by cost so far instead of discovery order.

Picking one on purpose#

The trade is not speed — both cost O(V + E) to visit everything. It is which question the visit order answers. BFS’s order answers “what is closest,” which is why it is the one with a shortest-path guarantee and the one whose frontier can balloon to the width of the graph. DFS’s order answers “does this branch lead anywhere, and where does it finish,” which is why it is the algorithm behind cycle detection and topological sort, and the one that can run out of room on a graph that goes deep rather than wide.

The failure that actually reaches production is DFS written recursively on a graph nobody checked the shape of. Recursion borrows the call stack for its bookkeeping, and that stack is a fixed region handed to the thread at creation — a graph that stays shallow in every test case and turns out to be one long chain in production runs off the end of it and crashes with a stack overflow, with nothing in the code itself that looked wrong beforehand. Inserting values into the binary search tree visualizer is a fast way to see the same thing happen to a tree: the same values in a different insertion order produce a shape that is either short and wide or one long chain, and it is the data’s shape, not the algorithm, that decides how deep the recursion goes.

The quieter failure is a cycle with no visited set. Recursive DFS follows an edge back to a node it already visited, treats that as a new call, follows its edges again, and never stops — an infinite loop with no error message, just a program that stops returning. A visited set is one line and fixes both the recursive and the iterative form. Leaving it out costs nothing until some input actually closes a loop, which is why it survives review on the acyclic test graphs and fails later, on the one input nobody drew a cycle into.