🧭Depth-First Search

NEW

Also known as: DFS

A graph traversal strategy that explores as far as possible along a branch before backtracking.

DESCRIPTION

Depth-First Search systematically traverses vertices by descending along edges until dead ends, then backtracking to explore unexplored paths. It can be implemented recursively or with an explicit stack. DFS underpins algorithms for topological sort, cycle detection, connected components, and finding strongly connected components. Its time complexity is linear in vertices plus edges, making it efficient for large sparse graphs.

ALTERNATIVE DEFINITIONS

Wikipedia

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.

Frames DFS broadly for both trees and general graphs.

Source

Princeton Algorithms

To visit a vertex, mark it and recursively visit all unmarked vertices adjacent to it.

Emphasizes the recursive marking approach characteristic of DFS.

Source

CP-Algorithms

Depth First Search (DFS) is an algorithm for traversing or searching graph data structures by exploring as far as possible along each branch before backtracking.

Adds the backtracking behavior explicitly central to DFS.

Source

RELATED TERMS

Graph Stack Recursion Backtracking Topological Sort Spanning Tree Tarjan’s Algorithm Strongly Connected Components Traversal

COMPETING TERMS

Breadth-First Search

RELATIONS

• Broader: Search

KNOWLEDGE AREAS

Software Engineering Mathematics

TARGET AUDIENCE

Software Developer Software Architect Full Stack Developer AI Engineer Data Scientist

EXTERNAL SOURCES

• Wikipedia - Depth-first search
• Princeton Algorithms - DFS theory and code
• CP-Algorithms - DFS explanation and patterns
• Wikipedia - General DFS overview

TOP QUESTIONS

What are typical uses of Depth-First Search?

DFS is used for topological sorting, cycle detection, connected components, and finding articulation points and bridges in graphs.

Category: Example

How does recursion relate to Depth-First Search?

DFS can be implemented recursively, where the call stack mirrors the traversal stack, or iteratively with an explicit stack.

Category: Concept

What is the time complexity of Depth-First Search?

DFS runs in O(V + E) on an adjacency list representation, visiting each vertex and edge a constant number of times.

Category: Requirements

How does DFS compare to Breadth-First Search?

DFS explores deep paths first, while BFS explores neighbors level by level. BFS finds shortest paths in unweighted graphs; DFS does not guarantee that.

Category: Comparison

When is DFS preferable?

Use DFS for tasks requiring exhaustive path exploration or when recursion simplifies logic, such as backtracking and component discovery.

Category: Best practices

What are common DFS pitfalls?

Forgetting to mark visited nodes causes infinite loops; recursion depth can overflow on large graphs without tailored stack limits.

Category: Mistakes

Does DFS work on directed graphs?

Yes. DFS on directed graphs supports algorithms like topological sort and strongly connected components.

Category: Concept

How do you detect cycles with DFS?

Track a recursion stack or colors; encountering a gray (in-progress) node indicates a back edge and a cycle.

Category: How-to

What data structure underpins DFS?

A stack, either implicitly via recursion or explicitly, underpins the depth-first traversal order.

Category: Concept