Depth-First Search
Depth-First Search explores a graph by following one path as deep as it goes, then backtracking to try the next. It's how you'd escape a maze, and how computers find paths, cycles and orderings.
How can it be useful to you?When you're exploring something with lots of branches and want to follow one branch all the way to the end before stepping back to try another.
Escaping the Maze
You're in a labyrinth looking for the exit. Pick a path and follow it as far as it goes. Dead end? Walk back to the last junction and try a path you haven't taken. Keep going until you find the exit or run out of paths. Going deep first and backtracking only when stuck is exactly how DFS works.
Climbing the Family Tree
You're tracing your ancestry. You start with your parents, then follow your father's line back as far as the records allow. When the trail goes cold, you backtrack and follow your mother's line as far as it will go. One branch to the end, then the next: that's DFS.
Hunting for a Book
You're in a library and don't know which shelf holds the book you want. You go through one shelf completely, end to end, and only then move to the next. Finishing each section fully before starting another follows the same spirit as DFS.
Summary
Depth-First Search means exploring one branch of a network as deeply as possible before retracing your steps and trying the others. It's a natural fit for problems like escaping a maze or tracing a family tree. Its sibling, breadth-first search, does the opposite: it checks everything close by before venturing further out.
Depth-First Search (DFS) is one of the basic ways to walk through a graph, and it has a simple personality: commit to a path and follow it as far as it goes. Starting from a node, DFS visits a neighbour, then that neighbour's neighbour, and so on, going as deep as possible before backtracking to the last junction with unexplored options. That single habit makes it the natural tool for detecting cycles, topological sorting and solving maze-like problems, in computer science, mathematics and beyond.
DFS connects to several other principles and topics:
Breadth-First Search (BFS): BFS is DFS's cautious sibling. It explores a graph level by level outward from a source vertex, using a queue to track what to visit next, whereas DFS uses a stack (explicitly, or implicitly through recursion). Neither is better in general; each suits different problems (Cormen et al., 2009).
Search Algorithms in Artificial IntelligenceAI systems use DFS to explore search spaces in problem-solving, constraint satisfaction and game playing. Paired with pruning strategies such as alpha-beta pruning in minimax search, it becomes far more efficient (Russell & Norvig, 2021).
Topological SortingDFS can produce a topological ordering of a directed acyclic graph (DAG): a linear order of vertices in which, for every directed edge (u, v), u comes before v. That is exactly what you need to schedule tasks with dependencies or lay out a valid sequence of courses in a curriculum (Cormen et al., 2009).
Connected Components and Strongly Connected ComponentsDFS can find the connected components of an undirected graph and the strongly connected components of a directed one, the subgraphs in which every node can reach every other. Identifying them underpins many kinds of graph analysis (Tarjan, 1972).
From AI search to topological sorting to component analysis, the same go-deep-then-backtrack idea keeps turning up, which is why DFS remains a workhorse across computer science and mathematics.
References
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Russell, S. J., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
- Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146-160.