Depth-first search (DFS)
Walk into a maze, keep going until you hit a dead end, then back up to the last fork and try the next way. Depth-first search explores a graph the same way. It is one of the simplest graph algorithms, and the stack it keeps tells you more than you might expect.
The idea
A graph is a set of nodes joined by edges: rooms and doors, web pages and links, tasks and the tasks they depend on. Depth-first search visits every node it can reach from a start, but in a particular order: it always carries on from the node it reached most recently. It keeps a stack of the nodes it is inside. A new node goes on top, and a node comes off only when everything around it has been explored.
Step by step
Put the start on the stack and give it visit number 1. Look at the next neighbour of the node on top. If it has not been seen, give it the next visit number, remember the node it was reached from, and put it on top of the stack. If it was seen before, skip it. When the node on top has no neighbours left to check, it is finished: take it off and carry on with the node below. Stop when the stack is empty, or when the goal is reached.
An example
Take a graph with the edges A–B, A–C, B–D, C–D, C–E and D–F, start at A, and check neighbours in alphabetical order. From A the search goes to B, from B to D, from D to C, and from C to E, so the stack is A, B, D, C, E. On the way, C sees A, which is still on the stack: the edge C–A closes the cycle A, B, D, C. E has nothing new, so it is finished, then C, and the search backs up to D, which still has F. The visit order is A, B, D, C, E, F. With E as the goal, DFS stops with the path A → B → D → C → E, four edges, although A → C → E takes only two.
What it is good for
The stack is always a path from the start to the current node, which makes DFS natural for mazes and puzzles: it is the idea behind backtracking. In a graph without directions, an edge to a node still on the stack closes a cycle. In a graph with directions, listing nodes in the reverse of the order they finish gives a topological order, so tasks come after the tasks they depend on. Depth-first search also finds connected components, bridges and articulation points, and its random version is a classic way to generate mazes.
History
In the 19th century the French mathematician Charles Pierre Trémaux described a way to escape any maze by marking passages, which is depth-first search done with chalk. In 1972 and 1973 Robert Tarjan and John Hopcroft showed that DFS solves many graph problems in linear time, from strongly connected components to testing whether a graph can be drawn without crossings. They received the 1986 Turing Award in part for that work.
Explore it
Open the app and press Step. The node whose neighbours are being checked is highlighted, nodes on the stack are blue, and finished nodes are green, each with its visit number. The stack is shown under the graph, from the start to the node on top. Watch the status line for the edges that close a cycle, and pick a goal to see how long the path found can be compared with breadth-first search.
Frequently asked questions
What is the time complexity of DFS?
O(V + E) for V nodes (vertices) and E edges: each node goes on and off the stack once, and each edge is examined from both ends. It needs O(V) extra memory for the stack and the marks.
Why does DFS use a stack?
Because last in, first out makes the search carry on from the newest node and back up to the one before it. Recursion does the same thing with the program's call stack. With a queue instead, the search would spread out ring by ring: that is breadth-first search.
Is recursive DFS a problem for big graphs?
It can be: a long path means deep recursion, and many languages limit how deep calls can go. An explicit stack in a loop avoids that limit while visiting nodes in the same order.
Where is DFS used?
Solving mazes and puzzles by backtracking, finding cycles, ordering tasks by their dependencies (topological sort), finding connected and strongly connected components, generating mazes, and in compilers and build tools that walk dependency graphs.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Try depth-first search