Depth-first search (DFS), explained

Depth-first search explores like someone walking through a maze who keeps taking the next turn until they hit a dead end, and only then goes back to try another branch.

It uses a stack, either explicitly or through recursion, to remember where to return to.

How it works

• Visit the start node and mark it as seen.
• Move to an unseen neighbour and repeat from there.
• When a node has no unseen neighbours, go back to the previous node.
• Stop when you have backed all the way up to the start with nothing left to visit.

A small example

Take the same edges as the BFS post and start from A:

A-B  A-C  B-D  C-E  D-E

Visit order: A, B, D, E, C

BFS visited B and C first. DFS dived from A to B to D to E before coming back to C.

What to know about its cost

• O(V + E) time.
• Uses O(V) space for the stack.
• The visit order depends on the order neighbours are tried.

Where it works well

• Good for exploring everything, such as finding connected parts.
• The basis for many other algorithms, like topological sorting.

Where it struggles

• Does not find shortest paths.
• Very deep graphs can make the recursion deep.

Try it yourself

Open the Graph Algorithms experiment, enter these edges (A-B, A-C, B-D, C-E, D-E), choose DFS and start from A, and step through it. Then try a different graph and watch how the result changes.

Open the Graph Algorithms experiment