Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Depth-First Search

Also Known As DFS
Graph Algorithm

Depth first search is an algorithm for traversing or searching tree and graph data structures. Starting at a chosen root node, it explores as far as possible along each branch before backtracking, typically using a stack, explicit or via recursion, to track the path and visited nodes. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/

Facts
Origin Year
1972 1
Maze-solving precursors date to the 19th century (Tremaux's algorithm), but DFS was formalized as an algorithmic technique for graph problems by Robert Tarjan's 1972 paper Depth-First Search and Linear Graph Algorithms.
Core Principle
Explores each branch to full depth before backtracking, in contrast with breadth first search; the underlying strategy was investigated in the nineteenth century by French mathematician Charles Pierre Tremaux as a maze solving method, predating its formalization in computer science. 1
Classification
Design Technique
Backtracking 1
Time Complexity
Time Complexity (category)
Linear Time -- O(n) 2
Connections

Associated With

Stack, Concepts
Source Wikipedia: Depth-First Search

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia: Depth-First Search

Uses Design Technique

Backtracking, Concepts
Sources
1. Wikipedia: Depth-First Search
Wikimedia Foundation
  • Opening paragraph
    explores as far as possible along each branch before backtracking
  • History note, Tremaux
    A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes.
  • Introduction
    depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
  • History section
  • In Field: Algorithms and Complexity Theory
  • Associated With: Stack, Opening paragraph, on stack-based traversal
  • In Group: Graph Traversal and Connectivity Algorithms, Lead section
    algorithm for traversing or searching tree or graph data structures
View the Source
2. Depth-First Search (Wikipedia)
Wikipedia infobox: time complexity linear
Quote, Wikipedia infobox: time complexity linear
linear
View the Source
Wikidata: Depth-First Search
Wikidata Q816319, class allow-list match (w-wdresolver-0926)View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.