What DFS Solves
Given a graph G = (V, E), Depth-First Search (DFS) explores the graph by going as deep as possible along each branch before backtracking.
Unlike BFS, DFS is not distance-oriented. It is oriented toward structure. It reveals global properties of graphs, such as cycles, strongly connected components, and topological ordering.
Reference: the presentation follows the classic treatment in
Introduction to Algorithms (CLRS).
Parts
- Part 1 — Graph Model & Problem Setting
- Part 2 — The Core Idea (Deep Exploration + Backtracking)
- Part 3 — The Algorithm (CLRS Pseudocode)
- Part 4 — Structural Properties & Discovery Times
- Part 5 — Edge Classification
- Part 6 — Applications I (Cycles & Topological Sorting)
- Part 7 — Applications II (SCC & Advanced Structures)
- Part 8 — DFS vs BFS