Depth-First Search
Go as deep as possible before backtracking; the recursion stack is the frontier.
Pop 0: new, so visit it as number 1. Its adjacency list: 1, 2. Push the unvisited ones, 1, 2, so that 1 is on top.
What you will see
DESCEND along an edge -> dead end -> BACKTRACK; the call stack grows and shrinks beside the graph.
Cost
| Best | O(V + E) |
|---|---|
| Average | O(V + E) |
| Worst | O(V + E) |
| Space | O(V) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Vertices announce name, neighbours and state (in queue, visited, current); each step announces which vertex is processed and which neighbours are discovered.
Reduced motion: Frontier and visited changes are crossfades; the traversal edge is emphasized without a travelling token.
Variants
- Recursive DFS Implicit call stack.
- Iterative DFS Explicit stack; visiting order differs slightly.
Leads to
Topics that need this one first.
Taught by the same lesson
BFS and DFS covers these too, in the same run.