Blog Posts
Exploring Depth First Search (DFS) Algorithm
November 15, 2025
Depth First Search (DFS) is one of the fundamental algorithms every aspiring programmer should master, especially those preparing for the USA Computing Olympiad (USACO) or anyone passionate about problem-solving . In many coding problems, we face an unknown space made up of connected points, e.g., web pages, users, lines of code, or moves in a game. To understand how these points relate, we need an efficient way to explore and navigate the network. This is where DFS comes in. DFS is a simple yet incredibly powerful algorithm designed to explore and analyze tree or graph structures. It's used in a wide range of applications, from pathfinding and scheduling to puzzle-solving and game logic. Think of it like exploring a maze: you keep moving forward until you reach a dead end, then backtrack and try a new path. That's the essence of DFS, diving deep into one direction before stepping back to uncover every possibility.
DFS is all about exploring one path as far as possible before turning back. Imagine diving deep into a tunnel until you hit a dead end, then retracing your steps to explore the other tunnels you passed.
But DFS isn't just theoretical but appears everywhere in computer science and real-world applications. Although at the surface, it seems only viable for path-finding or maze solving, it is capable of detecting cycles in graphs, performing topological sorting for scheduling tasks, solving puzzles like Sudoku or the N-Queens problem, and finding connected components in networks.
In short, DFS is like the ultimate explorer, simple, systematic, and surprisingly powerful. However, it is important to note that recursive DFS can sometimes lead to a stack overflow when the graph is very deep (e.g., over 100,000 nodes). The iterative version may avoid this issue by managing the stack manually.
- Start at a node (e.g., the root or any chosen vertex).
- Mark it as visited.
- Visit an adjacent unvisited node (e.g., go deeper).
- If no unvisited neighbors remain, backtrack to the previous node.
- Repeat until all nodes have been visited, or until a specific goal has been achieved.
There are two main ways to write DFS: (1) Recursively, where the function keeps calling itself using the system's call stack; (2) Iteratively, where you use your own stack to keep track of where to go next.
(Example: finding all possible paths from node 0 to node 5)
DFS in Python
There are 9 paths from node 0 to node 5
Learning DFS is a simple algorithm on the surface, but once you explore the nooks and crannies of all of its possible uses, it is a basic building block that helps with other algorithms and more than just a path algorithm. DFS also serves as the foundation for many advanced algorithms in computer science. Whether you're working on a graph problem, solving a tricky puzzle, or tackling a USACO challenge, DFS shows how elegant recursion can be!
DFS goes deep before it goes wide, following one path all the way down before backtracking to explore others. However, keep in mind that recursive DFS can sometimes lead to a stack overflow when the graph is very deep (e.g., over 100,000 nodes). The iterative version may avoid this issue by managing the stack manually.