Depth-First Search

Go Deep, Then Backtrack

1:00

How DFS explores a graph by going as deep as possible before backtracking — including the recursive and iterative implementations, the visited set, O(V+E) complexity, and key applications.

By the end, you can

Trace a DFS by hand on a small graph, including correctly applying the visited set and the order in which neighbors are explored.
Explain why a visited set is needed on graphs but not on trees.
Write both the recursive and iterative versions of DFS and explain the relationship between the implicit call stack and the explicit stack.
Derive the O(V+E) time and O(V) space bounds.
Name at least three problems DFS solves and describe how DFS is applied to each.
Distinguish pre-order from post-order processing and state which is needed for topological sort.
Explain when to prefer the iterative DFS over the recursive version.
Explain why DFS does not guarantee shortest paths and which algorithm to use instead.

Up next in Searching & Sorting