Depth-First Search
Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking, using a stack (either explicit or via recursion) to track the path. It is fundamental in computer science for solving problems involving connected components, cycle detection, and pathfinding. DFS is widely used in topological sorting, maze generation, and solving puzzles like Sudoku.
DFS vs BFS Comparison
| Property | DFS | BFS |
|---|---|---|
| Data Structure | Stack (or recursion) | Queue |
| Time Complexity | O(V + E) | O(V + E) |
| Space Complexity | O(V) worst case | O(V) worst case |
| Completeness | Not complete (infinite graphs) | Complete |
| Optimal Path | No | Yes (unweighted) |
| Use Case | Topological sort, cycles | Shortest path (unweighted) |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Topological Sort
Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u → v), vertex u appears before vertex v in the ordering. It is only possible for DAGs — graphs with cycles cannot be topologically sorted. Topological sort is essential in task scheduling, build systems (e.g., Makefile dependency resolution), course prerequisite ordering, and instruction scheduling in compilers.
Backtracking
Backtracking is an algorithmic technique for solving constraint satisfaction and combinatorial problems by incrementally building a solution and abandoning (backtracking from) a partial solution as soon as it is determined to violate the problem constraints, then trying the next possibility. It is essentially a depth-first search through the space of candidate solutions, pruning branches that cannot lead to a valid solution. Backtracking is used to solve N-Queens, Sudoku, crossword puzzles, subset-sum, and graph coloring problems.
Recursion
Recursion is a programming and mathematical technique in which a function calls itself with a smaller or simpler version of the original problem, progressing toward one or more base cases that terminate the chain of calls. Every recursive solution requires a base case (stopping condition) and a recursive case (self-referential reduction). Recursion is fundamental to tree traversal, divide-and-conquer algorithms, backtracking, and functional programming.
From English "depth" (Old English deopth, meaning how deep something extends) and "search" (Old French cerchier). The algorithm was formalized by Charles Pierre Trémaux in the 19th century for maze solving, and later rigorously studied in the context of graph theory.