How to Implement Depth-First Search (DFS) Using Recursion

What are the steps to implement Depth-First Search (DFS) using recursion in programming?

Depth-First Search (DFS) is a fundamental algorithm used for traversing or searching tree and graph data structures. It explores as far as possible along each branch before backing up. DFS can be implemented using recursion, making it an elegant solution for problems with tree-like structures.

def dfs(node, visited):
    if node not in visited:
        print(node)  # Process the node (e.g., print it)
        visited.add(node)  # Mark the node as visited
        for neighbor in node.neighbors:  # Iterate through each neighbor
            dfs(neighbor, visited)  # Recursive call for the neighbor

Solutions

• Define the base case for the recursive function that processes nodes.
• Use a helper function that takes a node and a visited set as parameters to track visited nodes.
• For each unvisited neighbor of the current node, recursively call the DFS function on that neighbor.

Mistake: Forgetting to mark nodes as visited, leading to infinite recursion.

Solution: Always add the node to the visited set at the beginning of the function.

Mistake: Not handling edge cases, such as empty graphs or isolated nodes.

Solution: Implement checks for empty inputs and ensure your recursive function can handle them.