Step 0 / 0 · Comparisons: 0 · Swaps: 0
How this algorithm works
How it works
- Push the start node onto a stack.
- Pop the top node off the stack; if it's already visited, skip it and pop again.
- Otherwise, mark it visited and record it as the next node in visit order.
- Push all of its unvisited neighbors onto the stack.
- Repeat popping until the stack is empty.
- Because the stack is last-in-first-out, the traversal dives deep into the most recently discovered branch before backtracking to try others.
Key concepts
- Stack-based (LIFO) traversal — implementable iteratively or via recursion
- Dives deep along one path before backtracking
- Useful for detecting cycles and computing topological order
- O(V+E) — every node and edge is examined at most once
When to use it
Cycle detection, topological sorting, connected-component analysis, maze/puzzle solving, and any problem where exploring one path fully before trying alternatives is natural (e.g. backtracking search).
Did you know
DFS is the traversal strategy behind solving mazes 'by hand' — always follow a passage as far as it goes, and only backtrack at a dead end.