Depth-First Search is an uninformed search algorithm that explores the deepest available node before considering shallower alternatives. It begins at a starting node and repeatedly moves to an unvisited successor. When no unvisited successor remains, it backtracks to the previous node and tries another branch. DFS can be implemented using an explicit last-in, first-out stack or through recursive function calls. In graph search, a visited set is commonly used to prevent repeatedly exploring cycles. DFS generally requires less frontier memory than BFS because it can store a path and a limited number of unexplored alternatives. However, it is not generally optimal and may fail to find a solution in an infinite-depth search space without depth limits or cycle handling. For a finite graph, graph-search DFS terminates when nodes are properly marked as visited. Its time complexity is O(V + E) for a graph represented with adjacency lists, where V is the number of vertices and E is the number of edges. Its space usage is O(V) in the standard graph-search implementation.
Depth-First Search
Depth-First Search (DFS) explores one branch as deeply as possible before backtracking to explore other branches.
Graph DFS Time Complexity: O(V + E); Auxiliary Space: O(V)
Explanation
Variables
| Symbol | Meaning |
|---|---|
V | The number of vertices in the graph. |
E | The number of edges in the graph. |
Stack | A last-in, first-out data structure used to manage exploration. |
Visited Set | A collection of vertices already visited. |
Example or application
Suppose A connects to B and C, B connects to D, and D connects to E. A DFS beginning at A may follow A → B → D → E before returning to explore C. The exact order depends on the neighbor ordering.
Text
DFS uses a last-in, first-out stack or recursion. It follows one available path deeply, then returns to earlier branching points when it cannot continue.
Key Points
DFS explores deeply before backtracking.
It uses a stack or recursion.
A visited set helps prevent infinite cycling in graph search.
DFS does not generally guarantee the shortest or lowest-cost path.
For adjacency-list graph traversal, its time complexity is O(V + E).
Applications
Cycle detection
Topological sorting in directed acyclic graphs
Finding connected components
Maze exploration
Dependency analysis
Learning Outcomes
Describe the depth-first exploration process.
Explain how backtracking works.
Compare DFS with BFS in memory use and solution guarantees.
Practice Questions
Which data structure is commonly used by DFS?
What does backtracking mean in DFS?
Why is DFS not generally an optimal search algorithm?
Related Concepts
Breadth-First Search
Uninformed Search Strategies
Stack Data Structure
Graph Traversal
Common Mistakes
Assuming DFS always finds the shortest path.
Forgetting to mark visited vertices in cyclic graphs.
Confusing the recursive call stack with a FIFO queue.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Cormen, T. H. et al. Introduction to Algorithms, section on Depth-First Search.
- Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, uninformed search.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning