Trees, graphs and optimization
Depth-first search
Explore a branch while preserving traversal state.
Understand the problem
DFS marks a vertex before exploring neighbors. For disconnected graphs, start a traversal from every unvisited vertex. Recursive implementations use the call stack; iterative versions use an explicit stack.
Make it concrete
Count islands by starting a flood fill at each unvisited land cell. Each cell is processed once.
Trade-offs and pitfalls
Recursive depth may exceed runtime limits on long chains.
Check your understanding
Write an iterative connected-components traversal.
Practice this topic