Depth-First Search (DFS)

Math for CS · Axiom Academy

LESSON Depth-First Search (DFS) Recursive exploration, edge classification, cycle detection, and topological sort Depth-First Search explores a graph by going as deep as possible along each branch before backtracking. Think of navigating a maze: follow a corridor until you hit a dead end, then retrace your steps and try the next unexplored turn. DFS Strategy: From the current vertex, pick an unvisited neighbor and immediately recurse into it. Only when all neighbors of a vertex are visited do we return to the previous vertex (backtrack). DFS naturally maps to recursion (the call stack acts as the implicit stack) or an explicit stack data structure. Unlike BFS, DFS does not find shortest paths, but it reveals deep structural properties of the graph. — when is first discovered (turned GRAY) — when is fully explored (turned BLACK) Parenthesis Theorem: For any two vertices and , the intervals and are either entirely disjoint or one is entirely contained within the other. DFS classifies every edge in the graph based on the colors and timestamps: Cycle Detection Theorem: A directed graph has a cycle if and only if DFS discovers a back edge . For undirected graphs, any edge to a non-parent visited vertex indicates a cycle. A topological sort of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every edge , vertex appears before .

This is the written version of the interactive lesson above. See the full Math for CS course.