The Four Core Patterns of DFS
Understanding DFS Patterns
Depth-First Search can be applied to a wide variety of problems, but most of them follow one of these four core patterns.
Each pattern represents a different way of thinking about and applying DFS to solve problems.
Backtracking Pattern
Cycle Detection Pattern
Topological Sort Pattern
Graph Traversal Pattern
Learning Objective
Understand the core patterns of depth-first search and how they can be applied to solve different types of problems.
The Four Core Patterns of Depth-First Search
While depth-first search can be applied to many different problems, most solutions follow one of these four core patterns. Understanding these patterns will help you recognize when and how to apply DFS to new problems.
Backtracking Pattern
Solve problems by trying different possibilities and backtracking when a solution is not feasible, useful for combinatorial problems.
Examples: N-Queens, Sudoku, Permutations, Combinations
Cycle Detection Pattern
Detect cycles in a graph by keeping track of vertices in the current recursion stack, useful for finding loops in a system.
Examples: Detect cycle in a graph, Course schedule, Deadlock detection
Topological Sort Pattern
Order vertices in a directed acyclic graph such that for every directed edge (u, v), vertex u comes before v, useful for scheduling problems.
Examples: Course prerequisites, Build order, Task scheduling
Graph Traversal Pattern
Explore all vertices and edges in a graph, useful for finding paths, connected components, and more.
Examples: Path finding, Connected components, Maze solving
Backtracking Pattern
Topological Sort Pattern
Choosing the Right Pattern
When faced with a problem that might be solved using depth-first search, ask yourself these questions to identify the most appropriate pattern:
For Backtracking Pattern
"Am I trying to find all possible solutions to a problem? Do I need to explore different possibilities and backtrack when a solution is not feasible?"
For Cycle Detection Pattern
"Do I need to detect cycles or loops in a graph or system? Am I dealing with a problem where cycles would cause issues?"
For Topological Sort Pattern
"Am I dealing with dependencies or prerequisites? Do I need to find an order such that certain tasks are completed before others?"
For Graph Traversal Pattern
"Do I need to explore all vertices and edges in a graph? Am I looking for paths, connected components, or other graph properties?"