DFS

Tactic

DFS explores one branch fully before returning to try alternatives. It can be written with recursion or an explicit stack.

The invariant is the visited state and the current path. In graph DFS, visited prevents cycles from causing infinite recursion. In tree DFS, the acyclic structure often makes visited unnecessary.

DFS is strongest when the answer depends on connected regions, paths, finishing times, or recursive substructure. It is not naturally shortest-path by edge count unless you explore every path or add more state.

Value

The value is low overhead exploration. DFS reaches deep structure quickly and stores only the active path plus visited state.

Direct complexity example

Brute force: Start a fresh search from every node without remembering visited nodes: $O(V \cdot (V + E))$ time in a graph.
With this tactic: Mark visited nodes and traverse each edge a bounded number of times: $O(V + E)$ time.
Space: Space is $O(V)$ for visited plus $O(depth)$ stack. In the worst case, depth can be $O(V)$ .

Challenges this solves

connected components
cycle detection
topological sort by finish time
island counting
tree recursion
path existence

When to use it

Use this tactic when these conditions are true:

you need to explore all reachable nodes
depth or path context matters
the graph can be marked visited
recursive decomposition is clear

When not to use it

Reach for a different tactic when these warning signs appear:

the problem asks for shortest unweighted path and BFS gives the first answer by level
recursion depth is unsafe and an iterative stack is not planned
edge weights require Dijkstra or Bellman-Ford
you need level-by-level processing

Terminology clues

These prompt words often point toward this concept:

DFS
depth first
connected component
visited
path exists
island
recursive traversal
finish time

DFS