Depth-First Search

Graph traversal algorithm that explores as far as possible along each branch before backtracking, using stack-based or recursive implementation.

Family: Planning Algorithms Status: ✅ Complete

Need Help Understanding This Algorithm?

🤖 Ask ChatGPT about Depth-First Search

Overview

Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible

along each branch before backtracking. It uses a stack (either explicit or implicit through recursion) to keep track of the current path, making it memory-efficient for deep graphs.

DFS is particularly useful for problems involving backtracking, cycle detection, topological sorting, and finding strongly connected components. While it doesn't guarantee shortest paths, it's efficient in terms of memory usage and can handle very deep graphs.

Mathematical Formulation¶

🧮 Ask ChatGPT about Mathematical Formulation

Mathematical Properties

Stack-based Traversal

S = {current_path}, explore deepest unvisited neighbor

Always explore the deepest unvisited node first

Backtracking

When no unvisited neighbors, backtrack to previous node

Return to most recent node with unvisited neighbors

Path Exploration

P = {v₁, v₂, ..., vₖ} where (vᵢ, vᵢ₊₁) ∈ E

Explores complete paths before backtracking

Memory Efficiency

Space = O(depth) vs BFS O(breadth)

Memory usage proportional to maximum depth

Key Properties¶

🔑 Ask ChatGPT about Key Properties

Memory Efficient

Uses O(depth) space instead of O(breadth)
Path Exploration

Explores complete paths before backtracking
Backtracking

Natural support for backtracking problems
Not Optimal

Doesn't guarantee shortest paths

Implementation Approaches¶

💻 Ask ChatGPT about Implementation

Recursive DFS

Natural recursive implementation using function call stack

Complexity:

Time: O(V + E)
Space: O(V)

Advantages

Memory efficient for deep graphs
Natural backtracking support
Good for cycle detection
Simple recursive implementation
Explores complete paths

Disadvantages

Not optimal for shortest paths
May get stuck in deep paths
Recursive version has stack overflow risk
Doesn't guarantee finding shortest solution

Use Cases & Applications¶

🌍 Ask ChatGPT about Applications

Application Categories

Backtracking Problems

N-queens: N-queens
Sudoku solver: Sudoku solver
maze generation: maze generation

Graph Analysis

cycle detection: cycle detection
topological sorting: topological sorting
strongly connected components: strongly connected components

Tree Traversal

pre-order traversal: pre-order traversal
in-order traversal: in-order traversal
post-order traversal: post-order traversal

Path Finding

maze solving: maze solving
puzzle solving: puzzle solving
game AI: game AI

Educational Value

Understanding recursion and backtracking: Understanding recursion and backtracking
Stack data structure concepts: Stack data structure concepts
Graph traversal strategies: Graph traversal strategies
Memory vs time trade-offs: Memory vs time trade-offs

References & Further Reading¶

:material-book: Core Textbooks

:material-file-document:

Interactive Learning

Try implementing the different approaches yourself! This progression will give you deep insight into the algorithm's principles and applications.

Pro Tip: Start with the simplest implementation and gradually work your way up to more complex variants.

Need More Help? Ask ChatGPT!

🧒 Explain Simply 📝 Practice Problems 🔀 Compare Algorithms 🐛 Debug Help

Related Algorithms in Planning Algorithms:

M* - Multi-agent pathfinding algorithm that finds collision-free paths for multiple agents by resolving conflicts and coordinating their movements.
A* Search - Optimal pathfinding algorithm that uses heuristics to efficiently find the shortest path from start to goal in weighted graphs.
Breadth-First Search - Graph traversal algorithm that explores all nodes at the current depth level before moving to the next level, guaranteeing shortest path in unweighted graphs.