NOTE

Depth-First Search

Recursive or explicit-stack DFS for graphs/trees, visitation state, cycle handling, and complexity.

Data Structures & AlgorithmsCreated 03/08/2021Updated 09/15/20261 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

Depth-first search explores one branch deeply before backtracking. It can use recursion or an explicit stack.

For graphs, maintain visited/state information to avoid revisiting nodes indefinitely and to support cycle/topological/SCC-style reasoning where needed.

With adjacency lists, full traversal is O(V+E). Recursive DFS can overflow the call stack on very deep graphs; use an explicit stack when depth is unbounded.