BFS and DFS visualizer

Choose a search and a graph, then press Play or Step. Click any node to start from it. Each step is one of four things: a node joins the queue or stack, a node is taken off and visited, an edge is examined, or (in DFS) a node is finished because all its neighbours are done. Neighbours are always tried in alphabetical order. BFS labels each node with its distance from the start; DFS labels it with its discovery time and, once finished, its finish time, counted on one clock that ticks at every discovery and every finish.

Try these:

• Run BFS on the Tree, then DFS. BFS fills in each level before the next; DFS runs down the left side first. Compare the peak sizes of the queue and the stack.
• Run both on the Grid. BFS spreads in a diagonal wave, and the distance labels are the shortest paths. DFS snakes through the whole grid on one long path, so its stack grows to 20 nodes.
• On Branching, watch for edges whose far end was already seen. In DFS each such edge leads back to a node on the current path, an ancestor; that is what makes DFS useful for finding cycles.

The searches are tested on thousands of random graphs: BFS distances match shortest-path lengths, and the DFS order matches a recursive depth-first search exactly.

Graph traversal means visiting every node of a graph that can be reached from a starting node, each exactly once. A graph is a set of nodes connected by edges: a road map, a social network, the links between web pages, the states of a puzzle, the cells of a maze. Breadth-first search and depth-first search are the two basic ways to do it, and many other graph algorithms are one of them with extra bookkeeping.

Both keep track of which nodes have been seen, so that cycles do not send them round forever, and both keep a frontier of nodes still to explore. The only difference is which frontier node they take next: the oldest (BFS, a queue) or the newest (DFS, a stack).

BFS puts the start node in a queue and marks it seen. Then, until the queue is empty, it takes the node at the front and adds each of its unseen neighbours to the back, marking them seen as they go in. Because the queue is first in, first out, every node at distance 1 is taken out before any node at distance 2, and so on: the search moves outward in layers.

That gives BFS its main property. The first time it reaches a node is along a path with the fewest possible edges, so recording each node's parent when it is discovered gives a shortest-path tree. Marking nodes when they enter the queue, not when they leave it, matters: it keeps each node in the queue at most once.

On the Branching graph from A, BFS visits A B C D E F G H I J K L.

DFS goes as deep as it can before backing up. From the current node it moves to the first unseen neighbour, makes that the current node, and repeats. When a node has no unseen neighbours left, it is finished, and the search backs up to the node it came from. The path from the start to the current node is exactly the contents of the stack, or of the call stack in the recursive version.

Recording when each node is discovered and when it is finished gives DFS its power. The intervals nest: a node's interval lies inside its parent's. In an undirected graph, every edge that is not part of the DFS tree joins a node to one of its ancestors (a back edge), so any such edge reveals a cycle. Sorting nodes by finish time, latest first, gives a topological order of a directed acyclic graph, and the same timestamps drive Tarjan's algorithms for strongly connected components and articulation points.

On the Branching graph from A, DFS visits A B D E H I F C G K J L.

Recursive DFS is short, but deep graphs can overflow the call stack (Python's default recursion limit is 1,000), so DFS is often written with an explicit stack. The tempting version swaps BFS's queue for a stack and changes nothing else: pop a node, then push all its unseen neighbours, marking them seen as they are pushed. That visits every node, but not in depth-first order. Marking a node when it is pushed claims it for the current node, even if a deeper path would have reached it first.

On the Branching graph, true depth-first order from A is A B D E H I F C G K J L; the shortcut gives A B D E H I F J L C G K. On 500 random graphs generated by this page, the two orders differed on 279. The difference matters whenever the algorithm relies on DFS's structure, such as back edges or finish times. Two correct iterative versions exist: push neighbours without marking them and skip a node when it is popped if it has already been visited, or store each node on the stack together with how far through its neighbour list the search has got, which is what the simulator does.

• Shortest paths without weights (BFS). Fewest moves in a puzzle, fewest hops in a network, degrees of separation in a social graph. C. Y. Lee's 1961 maze-routing algorithm for connecting circuit points is BFS on a grid.
• Crawling and garbage collection (BFS). Web crawlers explore outward from seed pages. Cheney's 1970 copying garbage collector traverses live objects breadth-first, using the copied objects themselves as the queue.
• Cycles and ordering (DFS). Detecting cycles, ordering build steps or course prerequisites topologically, and resolving dependencies.
• Structure (DFS). Connected components, strongly connected components, bridges and articulation points, all in linear time.
• Backtracking (DFS). Solving puzzles, generating permutations, and searching game trees explore choices depth-first and undo them on the way back.

For weighted graphs, BFS's queue becomes a priority queue and the result is Dijkstra's algorithm; adding a heuristic gives A*.

• Bidirectional BFS searches from both ends and stops when the frontiers meet. Each side only has to go half the distance, which in graphs that branch quickly means far fewer nodes.
• Multi-source BFS starts with several nodes in the queue, giving each node its distance to the nearest source, such as the nearest exit or hospital.
• 0-1 BFS handles edges of weight 0 or 1 with a double-ended queue, adding weight-0 neighbours at the front.
• Iterative deepening DFS, analysed by Richard Korf in 1985, runs depth-limited DFS with limits 1, 2, 3 and so on. It finds shortest paths like BFS while using only DFS's memory, at the cost of repeating the shallow levels.

Depth-first search is older than computers: a version for solving mazes is credited to the 19th-century French mathematician Charles Pierre Trémaux. Breadth-first search was described by Konrad Zuse in 1945, in an unpublished thesis on his Plankalkül language, and reinvented by Edward F. Moore in 1959 to find the shortest path through a maze. C. Y. Lee applied it to wire routing in 1961.

Depth-first search became central to algorithm design through the work of Robert Tarjan and John Hopcroft in the early 1970s. Tarjan's 1972 paper "Depth-First Search and Linear Graph Algorithms" used DFS's discovery order to find strongly connected components and biconnected components in linear time, and Hopcroft and Tarjan applied it to further graph problems, including testing whether a graph can be drawn without crossing edges. They received the 1986 Turing Award in part for this work.