How Depth First Search (DFS) Works: Step-by-Step Explanation

Imagine you’re exploring a new city with many interconnected roads connected to different places. How would you systematically visit all these places? One way is to pick a starting point and keep going down one path, exploring as far as possible before you have to turn back and try another path. This “go deep first” strategy is the core idea behind Depth First Search (DFS), a fundamental algorithm for exploring graphs. In this article, we’ll explore the detailed steps and various components involved in performing a Depth First Search.

The Core Idea: Go Deep, Then Backtrack

DFS prioritizes depth. When it arrives at a node, it doesn’t immediately look at all its neighbors. Instead, it picks one neighbor and immediately goes to visit it. It continues this “dive” deeper and deeper into the graph along a path. Only when it can’t go any deeper (hits a node with no unvisited neighbors or a node already visited), it goes back and explores other options.

Here’s a simple breakdown of the steps involved in Depth First Search:

1. Start Somewhere: Choose a node in the graph to begin the traversal. Mark this node as visited so you don’t accidentally come back and visit this node again.
2. Go Deeper: Look at the nodes directly connected to your current node (its neighbors). Pick one neighbor that you haven’t visited yet.
3. Move and Repeat: Move to the connected node and mark it as visited. Now, from this new node, repeat Step 2: look for its unvisited neighbors and pick one to move to. Keep doing this, going deeper and deeper along a path.
4. Hit a Dead End? Go Back: If you reach a node which does not have any neighbors or if all its neighbors have already been visited, you can’t go any deeper down this path. So, take one step back to the node you came from.
5. Try a Different Path: From the node you just stepped back to, look again for any other neighbors you haven’t visited yet from this spot.
   • If you find an unvisited neighbor, start going deep again (Go back to Step 3).
   • If there are no unvisited neighbors left even from this node, go back another step (Repeat Step 4).
6. All Done? Keep going back and exploring new paths until you’ve returned to your original starting node and there are no more unexplored paths leading from it. At this point, you’ve visited every node reachable from your starting point using the DFS method.

Key Components Needed for DFS

To perform DFS, we need a few things:

• A Starting Node: We need to choose a node in the graph where our search begins.
• A Way to Track Visited Nodes: We must keep track of the nodes we’ve already visited. This is crucial to avoid getting stuck in infinite loops (if the graph has cycles) and to prevent visiting the same node multiple times unnecessarily. This is often done using a list, set, or boolean array called visited.
• A Mechanism for Backtracking: DFS needs a way to remember the path taken so it can backtrack when it hits a dead end. This is usually achieved using a Stack. A stack follows the Last-In, First-Out (LIFO) principle, meaning the last item added is the first one removed. This perfectly matches the requirement of DFS as it needs to return to the most recently visited node that still has unexplored paths. Alternatively, recursion can also be used, which implicitly uses the system’s call stack.

The DFS Process Step-by-Step (Using a Stack)

Let’s outline the general steps for performing DFS starting from a chosen node startNode in a graph:

1. Initialization:

   • Create a way to keep track of visited nodes (e.g., a set or boolean array called visited). Initially, no nodes are marked as visited.
   • Create a stack and push the startNode onto it.

2. Mark the Start Node as Visited: Mark the startNode as visited.

3. Exploration Loop: While the stack is not empty:

   • Get Current Node: Look at (or “peek” at) the node currently at the top of the stack. Let’s call it currentNode. Don’t remove it yet.
   • Find Unvisited Neighbor: Check the neighbors of currentNode. Is there any neighbor that has not been visited yet?
   • If an Unvisited Neighbor is Found:
     • Choose one such unvisited neighbor (let’s call it nextNode).
     • Mark nextNode as visited.
     • Push nextNode onto the stack. Now nextNode becomes the new currentNode for the next iteration, and we’ll explore from it immediately (going deeper). Stop searching for other neighbors of the old currentNode for now.
   • If No Unvisited Neighbors are Found:
     • This means we’ve explored as far as possible down the current path from currentNode.
     • It’s time to backtrack! Pop currentNode from the stack. The node now at the top (if any) is where we resume exploring alternative paths.

4. Completion: Once the stack becomes empty, it means we have visited all reachable nodes from the startNode. The DFS process for that starting node is complete.

Example Walkthrough