Depth-first search (DFS)
Explores a graph by following one path as deep as it can, then going back to the last fork. The stack on screen is that path.
- time O(V + E)
- space O(V)
- uses a stack
What do these mean?
- Vertex: a point of the graph, drawn here as a circle with a letter.
- Edge: a line that joins two vertices. Here you can walk along it both ways.
- Neighbours: the vertices joined to a vertex by an edge. They are looked at in alphabetical order.
- Queue: first in, first out. BFS always takes the vertex that has waited longest.
- Stack: last in, first out. DFS always goes on from the vertex it reached last.
- V and E: the number of vertices and edges. O(V + E) means each vertex and each edge is handled a fixed number of times.
- on the stack
- current
- done
- search tree edge
- skipped edge
Start from A. Press play or step through the search.
Space: play or pause. Left and right arrows: step. Home and End: jump.
Try this: Pick the graph with cycles. Each dashed edge leads back to a vertex that is already on the stack or done: that edge closes a cycle.
How it works
DFS calls itself on the first neighbour it has not seen yet, then on that vertex’s first new neighbour, and so on. When a vertex has no new neighbours left, its call ends and DFS goes back one step to try the next neighbour there. The open calls form a stack, which is always the path from the start to the current vertex. The number next to a vertex is the order in which it was visited.
When it is a good choice
Use DFS to find out what can be reached at all, to find cycles, to walk through a maze or to put tasks that depend on each other in order. It does not find the shortest way.