DFS

Depth-First Search (DFS) is a graph traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking. In trees, DFS visits nodes in a preorder fashion. In general graphs, DFS uses a visited set to avoid revisiting nodes and to handle cycles.

Implementation can be recursive or iterative with an explicit stack. A typical recursive version visits a node, marks it as visited, then recursively visits each unvisited neighbor. An iterative version uses a stack: push the start node, then while the stack is not empty, pop a node, if it has not been visited, mark it and push its neighbors.

Time complexity is O(V+E) with an adjacency list representation, since each vertex and edge is considered once. Space complexity is O(V) in the worst case due to the recursion stack or an explicit stack, plus O(V) for the visited marker.

DFS is used for several tasks, including detecting cycles, computing connected components in undirected graphs, and performing topological sorts in directed acyclic graphs. It also enables backtracking search in puzzles, mazes, and constraint problems. Because DFS explores deep paths before backtracking, it does not generally yield the shortest path between nodes in unweighted graphs; breadth-first search is typically used when shortest paths are required.

Variants include processing all components by starting DFS from every unvisited node in graphs with multiple components, and adapting the approach for directed graphs to suit tasks like topological sorting or reachability analysis.