Depth-First Search

Explore as deep as possible along each branch before backtracking, using the call stack or an explicit stack.

Explore as deep as possible along each branch before backtracking, using the call stack or an explicit stack.

Every node currently on the recursion stack lies on the active path from the source to the current node — they form a single root-to-current chain.

The call stack naturally tracks the current exploration path without extra auxiliary storage.

Marking nodes visited before recursing prevents infinite loops in cyclic graphs.