Depth-First Search (DFS)

overview

Summary

depth_first_search explores as far as possible along a branch before backtracking. It uses a stack, either an explicit stack or recursion. Mark nodes as visited to avoid repeats. It works on a graph or tree. Order depends on neighbor listing. Key idea: go deep, then backtracking. Typical outputs include a dfs_order and parent relationships. Complexity: time_complexity O(V+E), space_complexity O(V) for visited and stack depth. DFS can detect cycles and build connected_components.