Breadth-first and depth-first search: a queue or a stack

Drop a stone in a pond and the ripple reaches everything one step out before anything two steps out. Explore a maze with a ball of string and you do the opposite: follow one passage to its end, and only then wind back to the last junction with a passage you haven't tried.

Those are the two classic ways to visit every node a start can reach in a graph. Breadth-first search (BFS) spreads out in rings, so it finds the route with the fewest edges to each node. Depth-first search (DFS) dives down one path and backs up, the natural way to ask what can be reached, or whether the graph loops back on itself. What sets them apart is where they keep the nodes still waiting: BFS in a queue, DFS in a stack.

reachable

v is reachable from s when some path of edges leads from s to v. A search from s visits exactly these nodes.

discovered

A node is discovered the first time the search finds it, and marked at once, so no later edge adds it again.

frontier

The nodes found but not yet finished with: a queue in BFS, a stack in DFS. Exploring a node means looking at its neighbours.

level

The fewest edges on any path from the start: the start is level 0, its neighbours level 1, and so on.

parent

The node a node was discovered from. Parent links form a tree; in BFS, following them back from a node traces a shortest path.

backtrack

In DFS, stepping back along the current path when the node at its end has no undiscovered neighbours.

This network has 8 nodes and 10 edges, and neighbours are read in alphabetical order. Run BFS from A and watch the Queue panel: nodes join at the back and leave from the front.

A's neighbours, B and C, join the queue first. B leaves and adds D behind C; then C leaves and adds E. So every level-1 node leaves before any level-2 node, and the queue never holds more than two neighbouring levels. That makes the levels exact: when u, at level k, finds an undiscovered v, every node at a lower level has already been explored, and if v were next to any of them it would have been found then. So no path reaches v in fewer than k + 1 edges. The parents back from H in the Levels and parents table give H, F, D, B, A: four edges, and no path is shorter.

Now DFS on the same graph. It is recursive: it calls DFS on a node as soon as it discovers it, and the Call stack panel holds the path from A to the current node.

B's list does hold D, but C comes first, so by the time DFS returns to B, D is finished. On the way down, when C looks at A, A is still on the call stack: that edge closes the loop A–B–C–A. It is called a back edge, and it is how DFS finds cycles.

In both runs Edges examined ends at 20: each list is read once, so each edge is read once from each end. Both take O(V + E) with adjacency lists, and O(V²) with a matrix, whose rows have V cells (see representing graphs). Extra memory is O(V): a mark per node, plus the queue or the call stack.

Same network, but this time BFS starts from D, in the middle. Whenever more than one node is waiting, predict which leaves the queue next. The rule is first in, first out, whatever the nodes are called.

From D nothing is more than two edges away. Within a level, nodes leave in the order they were found: A and C, found by B, go ahead of E, G and H, found by F.

Here is BFS on a square, A–B, B–C, C–D and D–A. The queue is a list with a head index that steps past each node as it leaves, so nothing shifts (see stacks and queues). The map dist holds each node's level and doubles as the mark: a node has an entry once it is discovered.

def bfs(graph, start):
    dist = {start: 0}
    queue = [start]
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                queue.append(v)
    print(' '.join(queue))
    return dist

graph = {'A': ['B', 'D'], 'B': ['A', 'C'], 'C': ['B', 'D'], 'D': ['A', 'C']}
hops = bfs(graph, 'A')
print('C: ' + str(hops['C']))

C joins once only because dist[v] is set when v is found, not when it leaves.

DFS is simplest written recursively, as in its visualiser's code: mark u, then call DFS(v) for each unmarked neighbour v. The calls wait on the call stack (see recursion), so a path of 100,000 nodes nests 100,000 calls, far past Python's default limit of 1,000. An explicit stack avoids that: pop a node, skip it if visited, otherwise mark it and push its unmarked neighbours, each list in reverse so the first is on top. A node can be pushed more than once, so the stack can hold O(E) entries, but only its first pop counts, which keeps the recursive order; push in list order and the route changes.

Either way, DFS reaches every node it can, but not always by the shortest route.

Each search has its jobs. BFS answers "how few steps?": the fewest hops between two people, the fewest moves in a puzzle, how fast something spreads (several starts at level 0 give each node its distance to the nearest). DFS answers "can I get there?" and "is there a loop?": filling regions, finding cycles, and topological sort, ordering tasks so each comes after what it depends on. Neither goes beyond what its start can reach.

To visit a whole graph, start a new search from each node not yet discovered. In an undirected graph each start opens another connected component, and the total is still O(V + E).

The last trap is weights.

• BFS keeps its frontier in a queue, so it explores every node one edge away before any two away. Its levels are the fewest edges from the start, the shortest distance only when edges are unweighted.
• DFS keeps a stack, usually the call stack: it dives down one path and backtracks when stuck. It finds a path, not always the shortest, and an edge to a node still on the stack, other than the edge it came in on, closes a cycle.
• In BFS, mark a node the moment it is discovered, so it joins the queue once. Both take O(V + E) with adjacency lists, O(V²) with a matrix, and O(V) extra memory. Neighbour order decides the visit order.
• A search reaches only what its start can reach; start again from each undiscovered node to cover every component.
• Next: topological sort, Dijkstra's algorithm for weighted edges, minimum spanning trees and strongly connected components. Write both searches in Write breadth-first search and Write depth-first search, then practise with Count the Islands, a search per island, and Spreading Rot, a BFS from every rotten orange at once.