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.
- O(V + E)
- space O(V)
- stack
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.
Stack: last in, first out. DFS always goes on from the vertex it reached last.
Other terms on this page
- 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.
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.