BFS and DFS: one algorithm, two orders

Breadth-first and depth-first search are usually taught as two algorithms, which is why people mix them up for years. They are one algorithm. You keep a collection of nodes you have discovered but not yet explored; you take one out, look at its neighbours, put the new ones in. If you take from the front of that collection you get breadth-first. If you take from the back you get depth-first.

That is the whole difference — one line — and once you have seen it side by side, the two stop being separate things to remember. Everything else about them follows from where you take nodes from.

One function, one line of difference

Here they are as the same function, because they are:

from collections import dequedef traverse(graph, start, mode):    frontier = deque([start])    visited = {start}    order = []    while frontier:        node = frontier.popleft() if mode == "bfs" else frontier.pop()        order.append(node)        for nxt in graph.get(node, ()):            if nxt not in visited:                visited.add(nxt)      # mark on ENQUEUE, not on dequeue                frontier.append(nxt)    return order

On a small directed graph where a leads to b and c, both lead toward d and e, and everything converges on f:

BFS from a: ['a', 'b', 'c', 'd', 'e', 'f']DFS from a: ['a', 'c', 'e', 'f', 'd', 'b']

Breadth-first sweeps outward in rings: everything one step away, then everything two steps away. Depth-first commits to a path and follows it to the end before backtracking. Same graph, same code, one call to popleft instead of pop.

Two details in that function are load-bearing.

The visited set is not optional. Remove it and a graph containing a cycle loops forever. Even on a graph with no cycles it is required for efficiency: with several paths converging on the same node, you re-explore that node's entire subtree once per path, which turns polynomial work exponential.

Mark visited when you add to the frontier, not when you remove. This is the classic subtle bug. If you only mark on removal, a node reachable from three neighbours gets pushed three times before any of those copies is processed, so it is explored repeatedly and your frontier bloats. The code above marks on enqueue, which guarantees each node enters exactly once.

Representation, and the graphs you did not notice

An adjacency list — each node mapped to its neighbours — is the right default. An adjacency matrix, a grid of every possible pair, costs memory proportional to the square of the node count regardless of how many edges exist. For a social graph with a million users averaging a hundred connections each, the list holds a hundred million entries while the matrix would need a trillion cells to store the same information. Matrices earn their place only when the graph is genuinely dense or you need constant-time "is there an edge between these two" lookups.

More useful than either fact: recognising graphs where nobody has labelled one. A grid of cells is a graph whose edges are the adjacencies. A tree is a graph that happens to have no cycles. A dependency file, a state machine, a maze, a set of tasks with prerequisites, a series of moves in a puzzle — all graphs, and all solvable with the twenty lines above once you see them that way. Much of the difficulty in graph problems is noticing that you have one.

Why breadth-first gives shortest paths

Because it explores in order of distance, breadth-first search finds the shortest path in an unweighted graph — and the guarantee comes directly from the ordering. All nodes at distance one are dequeued before any at distance two, so the first time you reach a node, you cannot have reached it by a longer route: a longer route would have arrived on a later ring.

Be precise about the condition, though: unweighted. As soon as edges carry different costs, this breaks. A two-hop path costing 1 + 1 can beat a one-hop path costing 50, and breadth-first will happily return the single expensive edge because it counts hops, not cost. Weighted shortest paths need a different algorithm that considers accumulated cost; the point here is knowing that you have crossed out of BFS territory.

"How far" and "which way" are also different questions. Recording a parent for each node as you discover it lets you reconstruct the route:

def shortest_path(graph, start, goal):    if start == goal:        return [start]    parent = {start: None}    frontier = deque([start])    while frontier:        node = frontier.popleft()        for nxt in graph.get(node, ()):            if nxt in parent:          # `parent` doubles as the visited set                continue            parent[nxt] = node            if nxt == goal:                path = [goal]                while parent[path[-1]] is not None:                    path.append(parent[path[-1]])                return list(reversed(path))            frontier.append(nxt)    return None                        # goal unreachable

shortest a->f: ['a', 'b', 'd', 'f']shortest a->a: ['a']unreachable  : None

Returning None rather than an empty list matters: an empty path and no path are different answers, and conflating them pushes the bug into the caller.

Depth-first suits questions about structure

Depth-first search follows a path to exhaustion, which makes it the tool for questions about how a graph is put together rather than how far apart things are — connected components, cycles, orderings.

Cycle detection in a directed graph is where the useful subtlety lives, and it is where most first attempts are wrong. The instinct is to report a cycle on reaching an already-visited node. That is incorrect, and this graph shows why: a leads to both b and c, and both lead to d. Exploring it, you reach d twice. There is no cycle — you cannot get from d back to a.

The distinction you need is between "visited at some point" and "currently on the path I am exploring". Three states capture it:

WHITE, GREY, BLACK = 0, 1, 2      # unseen, on the current path, finisheddef has_cycle(graph):    colour = {}    def visit(node):        colour[node] = GREY        for nxt in graph.get(node, ()):            c = colour.get(nxt, WHITE)            if c == GREY:              # back edge to the current path                return True            if c == WHITE and visit(nxt):                return True        colour[node] = BLACK           # done: safe to meet again        return False    return any(visit(n) for n in graph if colour.get(n, WHITE) == WHITE)

A node is grey while its exploration is in progress and black once finished. Reaching a grey node means you have looped back onto your own path, which is a cycle. Reaching a black node means you have found a different route to something already fully explored, which is fine. Tested against a chain, a genuine cycle, and the diamond:

has_cycle DAG: False   CYC: True   diamond: False

That third result is the one to check your own implementation against. A version that only tracks "visited" reports True for the diamond and is wrong.

Once cycles are settled, topological ordering follows — arranging nodes so every dependency comes before whatever needs it. Counting incoming edges and repeatedly taking whatever has none left gives both the order and a cycle check for free:

topo DAG: ['shirt', 'socks', 'tie', 'shoes', 'jacket']topo CYC: None

If the output is shorter than the node count, something still had incoming edges when the queue emptied, which can only mean a cycle. A build system reporting a circular dependency is doing exactly this.

Recursion is cleaner and will fail on real input

The has_cycle function above is recursive because the three-colour logic reads far better that way. That comes with a real limitation: each recursive call consumes a stack frame, and interpreters cap stack depth. On a graph that is a long chain — a linked list of ten thousand nodes, a deep dependency tree, a path through a large grid — recursive depth-first search does not run slowly, it terminates with a recursion error.

That is a crash on valid input, not a performance note. If the depth is bounded and small, recursion is the better code. If the input is user-supplied or unbounded, use an explicit stack — the iterative traverse above has no depth limit beyond available memory. Converting the three-colour cycle check to an explicit stack means pushing a marker to run the "colour this node black" step after its children, which is fiddly enough that it is worth writing once and keeping.

Both cost O(V + E)

Each node is visited once and each edge examined once, so the work is proportional to nodes plus edges. The sum rather than the product is the point: the two quantities are independent, and which dominates depends on the graph. A sparse graph — a tree, a road network — has E close to V, so traversal is effectively linear in the node count. A dense graph has E close to V squared, and the edges dominate entirely.

This is why the representation choice reappears in the complexity. With an adjacency list you touch only the edges that exist, giving O(V + E). With an adjacency matrix you must scan a full row of V cells to find each node's neighbours, which makes traversal O(V squared) no matter how few edges there are. Space is O(V) for the visited set and frontier, plus whatever the graph itself occupies.

A grid problem, worked

Counting connected regions in a grid is the applied version of all of this, and it demonstrates the "graphs in disguise" point. Cells are nodes, adjacency is edges, and each unvisited filled cell starts a new region whose full extent one traversal claims:

def count_regions(grid):    if not grid or not grid[0]:        return 0    rows, cols = len(grid), len(grid[0])    seen, regions = set(), 0    for r in range(rows):        for c in range(cols):            if grid[r][c] != "#" or (r, c) in seen:                continue            regions += 1                      # new region found            stack = [(r, c)]            seen.add((r, c))            while stack:                      # claim all of it                y, x = stack.pop()                for dy, dx in ((1,0),(-1,0),(0,1),(0,-1)):                    ny, nx = y + dy, x + dx                    if 0 <= ny < rows and 0 <= nx < cols \                       and grid[ny][nx] == "#" and (ny, nx) not in seen:                        seen.add((ny, nx))                        stack.append((ny, nx))    return regions

On a five-by-four grid it finds five regions, and an empty grid returns zero rather than raising. Note that the outer double loop is not wasted work despite the inner traversal: seen is shared across every region, so each cell is examined a constant number of times overall and the whole function is linear in the cell count. Note too that the adjacency tuple encodes the rules of the problem — add the diagonals and you are answering a different question, which is the kind of detail worth reading carefully in a specification.

Choosing between them

The wording of a problem usually decides it.

• Shortest, fewest, nearest, minimum number of steps — breadth-first, on an unweighted graph. The level-by-level order is the guarantee.
• Is there a path, are these connected, how many components — either works. Depth-first is usually less code.
• Cycle, ordering, dependencies, valid sequence — depth-first, with the grey/black distinction if the graph is directed.
• Explore every possibility, all paths, backtracking — depth-first, because it naturally undoes a choice on the way back up.
• The graph is enormous and the target is probably close — breadth-first, which will find a nearby target without descending into a deep branch first.

If a problem does not obviously demand one, write the iterative version and pick whichever you find clearer to read six months from now. The distance guarantee is the only property that genuinely forces your hand.