1. Graph Model
Depth-First Search (DFS) operates on a graph formally defined as
- V — the set of vertices
- E — the set of edges
Graphs may be:
- Directed
- Undirected
DFS works in both cases and allows the algorithm to explore the structure of the graph starting from a given vertex.
2. The Exploration Problem
Given a graph G = (V,E) and a starting vertex s ∈ V, the goal is to explore all vertices reachable from s.
DFS performs this exploration by following a path as deep as possible before returning and exploring alternative paths.
3. Structure of the Exploration
DFS explores the graph by following a single path until no further unvisited vertices can be reached.
When that happens, the algorithm returns to the previous vertex and continues exploring other unexplored edges.
4. Reachability
A vertex v is said to be reachable from s if there exists a path from s to v.
DFS discovers exactly the set of vertices reachable from the source.
5. Why DFS Matters
Depth-First Search is one of the fundamental graph traversal algorithms.
It serves as the foundation for several important algorithms in computer science.
- Cycle detection
- Topological sorting in DAGs
- Strongly connected components
- Structural analysis of graphs
Next: Part 2 — The Core Idea (Deep Exploration + Backtracking)
Now that we defined the graph model and the exploration problem, we can study the central idea behind DFS: how the algorithm explores paths deeply before returning.