Introduction to DFS
Depth First Search is a fundamental graph traversal algorithm where we explore a path as deep as possible before backtracking and trying another path.
Unlike BFS, which moves level by level, DFS dives deep into a branch, then unwinds and explores the next one.
DFS shows up in a wide range of problems, including:
- Finding a path between two nodes
- Detecting cycles in a graph
- Counting connected components
- Performing topological sorting on DAGs
- Solving grid-based search problems (like islands, mazes, word search)
In this chapter, I’ll break down:
- what DFS is?
- how it works step by step?
- Two ways to implement it in code
What is Depth First Search?
DFS is a powerful search algorithm for traversing a tree or graph data structure.
A simple way to think about DFS is to visualize yourself inside a maze trying to reach the exit:
- Pick a direction and start walking.
- Keep going until you can’t move further.
- If you hit a dead end, backtrack to the last point of choice.
- Try a different path and repeat.
DFS works on any structure that can be represented as nodes and edges like trees tries, graphs and 2D grids.
To prevent infinite loops, DFS marks nodes as visited so they aren’t processed more than once.
Lets apply DFS to this graph starting from node A.
- Start at A, visit B
- From B, go deeper to D
- D has no neighbors so we hit a dead end. Backtrack to B
- From B, visit E
- E has no neighbors, backtrack to B. Since we have visited all of B’s neighbors, backtrack to A
- From A, visit C
- From C, visit F
- F has no neighbors so backtrack to C, then back to A
How to Implement DFS?
DFS can be implemented in two ways:
- Recursively - where the function call stack implicitly handles the backtracking
- Iteratively - where we use an explicit stack data structure to simulate recursion
Both approaches achieve the same result, but they differ in how they manage backtracking and memory usage.
Lets first look at the recursive approach:
- Choose a Starting Point
- Keep track of visited nodes using a boolean array
- Visit the current node and mark it as visited.
- Perform the required operation on the current node (for example.. print it).
- Iterate through all its neighbors and If a neighbor is unvisited, visit it recursively.
The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
This is because each node is processed exactly once and each edge is examined at most twice in an undirected graph (once from each endpoint) and exactly once in a directed graph.
The space complexity is O(V) since we are using a visited array of size V and in the worst case, recursion stack can grow up to the number of nodes.
For Example: If the graph is structured like a linked list, the recursion depth can reach O(V).
This can lead to stack overflow in large graphs.
That’s why it’s better to use an iterative approach if memory or running into stack overflow is a concern.
Lets see how to implement DFS iteratively using a stack:
- Create a boolean array (
visited[]) to track visited nodes and prevent cycles. - Initialize an empty stack.
- Push the start node onto the stack to begin the DFS process
- while the stack is not empty:
- pop the top node from the stack
- if it’s not visited, mark it as visited and process it.
- Iterate through it’s adjacent nodes in the reverse order and push all unvisited neighbors onto the stack.
- Why reverse order? It’s because stack is last in first out
- so reversing the order ensures that the first node gets processed first.
- Continue until all nodes are visited.
Similar to the recursive approach, the time and space complexity of this approach are both O(n).