DFS Algorithm: Pseudocode and Explanation

Depth First Search, or DFS, is a popular algorithm used to explore or search through data structures like trees and graphs. Think of it like exploring a maze: you go down one path as far as possible before backtracking and trying another. Understanding the pseudocode, which is like a simplified, human-readable version of the code, helps grasp the core logic before diving into specific programming languages. This article breaks down the pseudocode for DFS.

The Core Idea Behind DFS

Before looking at the code structure, let’s quickly refresh the main idea of DFS:

1. Start at a chosen node.
2. Explore as far as possible along one path before hitting a dead end or a previously visited node.
3. Backtrack to the last point where there was an unexplored path and take that path.
4. Repeat by exploring the next available path from the point you backtracked to.

We can implement this idea using either recursion (which uses the program’s internal call stack) or iteration (using an explicit stack data structure).

DFS Pseudocode: The Recursive Way

One of the most intuitive ways to implement DFS is through recursion. Imagine recursion as a process where a function calls itself to solve smaller, identical versions of the main problem. You can learn more about recursion here: Recursion Technique and Recursive Functions.

Here’s how the recursive DFS pseudocode looks:

// Main DFS function that initiates the search
function DFS_Main(graph, startNode):
  // Create a set or boolean array to keep track of visited nodes
  visited = new set()

  // Call the recursive helper function to start the traversal
  DFS_Recursive(graph, startNode, visited)

// Recursive helper function
// graph: Represents the graph (e.g., using an adjacency list)
// node: The current node being visited
// visited: The set/array tracking visited nodes
function DFS_Recursive(graph, node, visited):
  // 1. Mark the current node as visited
  add node to visited

  // 2. Process the current node (e.g., print it, check it)
  process(node)

  // 3. Explore neighbors
  for each neighbor adjacent to node in graph:
    // 4. If the neighbor hasn't been visited yet...
    if neighbor is not in visited:
      // 5. ...recursively call DFS on the neighbor
      DFS_Recursive(graph, neighbor, visited)

Explanation:

1. DFS_Main: This sets up the process. It creates a way to track visited nodes (visited) and then calls the helper function DFS_Recursive starting from the startNode. If the graph might be disconnected (have separate parts), you might need to loop through all nodes and call DFS_Recursive if a node hasn’t been visited yet.
2. DFS_Recursive: This is where the main logic happens.
   • It first marks the current node as visited.
   • It then “processes” the node (this could mean printing its value, adding it to a list, etc., depending on the problem).
   • It looks at all the neighbor nodes connected to the current node.
   • For each neighbor, it checks if it has already been visited.
   • If a neighbor is unvisited, it makes a recursive call to DFS_Recursive with the neighbor as the new current node. This is the “go deeper” step.
   • When a node has no unvisited neighbors, the function finishes for that node, and the process backtracks to the previous node’s loop to check its other neighbors.

DFS Pseudocode: The Iterative Way (Using a Stack)

While recursion is elegant, it can sometimes lead to issues if the graph is very deep (causing too many function calls). An alternative is to use an iterative approach with a data structure called a Stack. A stack works like a pile of plates – you add (push) to the top and remove (pop) from the top (Last-In, First-Out).

// Iterative DFS function
// graph: Represents the graph
// startNode: The node where the search begins
function DFS_Iterative(graph, startNode):
  // 1. Create a set or boolean array to track visited nodes
  visited = new set()

  // 2. Create a stack and add the starting node to it
  stack = new Stack()
  stack.push(startNode)

  // 3. Loop while the stack is not empty
  while stack is not empty:
    // 4. Remove the top node from the stack
    node = stack.pop()

    // 5. Check if the node has already been visited (important!)
    //    If yes, skip the rest and continue to the next iteration
    if node is in visited:
      continue

    // 6. Mark the node as visited
    add node to visited

    // 7. Process the node
    process(node)

    // 8. Add all unvisited neighbors to the stack
    //    Note: Neighbors might be added in reverse order depending on
    //    how you iterate, affecting the exact traversal path.
    for each neighbor adjacent to node in graph:
      if neighbor is not in visited:
        stack.push(neighbor)

Explanation:

1. Initialize a visited set and a stack.
2. Push the startNode onto the stack.
3. The main loop continues as long as there are nodes in the stack.
4. Inside the loop, pop a node from the stack. This is the node we’ll explore next.
5. Crucially, check if this popped node is already in the visited set. Why? Because a node might be added to the stack multiple times if it’s a neighbor of several nodes. We only want to process it the first time we pop it. If it’s visited, we continue to the next loop iteration.
6. If the node hasn’t been visited, mark it as visited.
7. process the node.
8. Find all neighbors of the current node. For each neighbor that hasn’t been visited yet, push it onto the stack. These neighbors will be explored in future iterations.

Key Components Explained

• Visited Set/Array: This is essential. It prevents the algorithm from going in circles (infinite loops in cyclic graphs) and avoids processing the same node multiple times, making the algorithm efficient.
• Graph Representation: The graph in the pseudocode usually refers to an adjacency list (preferred for sparse graphs) or an adjacency matrix (simpler for dense graphs), which tells us which nodes are connected.
• Stack (Iterative Version): This data structure perfectly models the “backtracking” nature of DFS. When we finish exploring from one node, the stack naturally gives us the previous node we need to return to.

Understanding this pseudocode gives you a solid foundation for implementing DFS in any programming language. It clearly outlines the logic of exploring deeply, tracking visited nodes, and backtracking when necessary.

What’s Next?

Now that you have a grasp of the DFS pseudocode, you can explore further:

• See DFS in Action with Code: Look at how DFS is implemented in specific programming languages like Python, Java, C++, or JavaScript.
• Analyze DFS Performance: Understand how efficient DFS is in terms of time (O(V + E)) and memory usage.
• Discover DFS Uses: Learn about the various problems DFS can solve, such as finding paths, detecting cycles, and topological sorting.
• Visualize DFS: See animations and visualizations that can help solidify your understanding of how DFS explores a graph.
• Avoid Common Pitfalls: Learn about frequent errors made when implementing DFS and how to prevent them.