✦ScienexySCIENCE KNOWLEDGE LIBRARY
Science reference · SCI-CS-003-035

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

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.

Variables

SymbolMeaning

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