Implementing DFS: Recursive & Iterative Approaches

1. The Core Idea: Diving Deep Before Going Wide

The principle behind DFS is simple yet powerful:

1. Start at a given source node.
2. Pick one of its neighbors and immediately move to it.
3. From that new node, pick one of its neighbors and move again.
4. Continue this process, going deeper and deeper into the graph, until you reach a node with no unvisited neighbors (a "dead end").
5. At the dead end, you backtrack to the previous node and try its next unvisited neighbor.

This process naturally lends itself to two implementation styles: recursion, where the call stack handles backtracking for us, and iteration, where we use an explicit Stack to manage the nodes to visit.

To build a strong mental model of this process, let's watch a short conceptual overview.

2. Recursive DFS: The Natural Approach

Given your background with programming and recursion, you'll see that it's a very elegant way to express DFS. The function call stack implicitly keeps track of the path we've taken, making backtracking automatic when a function call returns.

The algorithm for a recursive DFS is straightforward:

1. Define a helper function, say dfsUtil(node, visited, adj, result).
2. In this function, first, mark the current node as visited.
3. Add the node to your traversal result list.
4. Iterate through all the neighbors of the current node.
5. If a neighbor has not been visited, make a recursive call: dfsUtil(neighbor, ...).

Let's see this translated into Java.

Complete Recursive Implementation

Here is a full, runnable example. Note the main dfs method that handles initialization and the case of disconnected graphs by looping through all vertices. This is a crucial detail for interview problems, as you can't assume a graph is a single connected component.

import java.util.ArrayList;
import java.util.List;

public class DFSRecursive {

    // Main DFS function that handles disconnected components
    public static List<Integer> dfsTraversal(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        List<Integer> result = new ArrayList<>();

        // Loop through all vertices in case the graph is disconnected
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfsUtil(i, visited, adj, result);
            }
        }
        return result;
    }

    // Recursive helper function
    private static void dfsUtil(int u, boolean[] visited, ArrayList<ArrayList<Integer>> adj, List<Integer> result) {
        // Mark the current node as visited and add it to the result
        visited[u] = true;
        result.add(u);

        // Recur for all the vertices adjacent to this vertex
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                dfsUtil(v, visited, adj, result);
            }
        }
    }

    public static void main(String[] args) {
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Example from the image at the start
        adj.get(0).add(1);
        adj.get(1).add(0);

        adj.get(0).add(2);
        adj.get(2).add(0);

        adj.get(1).add(3);
        adj.get(3).add(1);
        
        adj.get(2).add(4);
        adj.get(4).add(2);

        System.out.println("DFS Traversal (Recursive):");
        List<Integer> traversal = dfsTraversal(V, adj);
        System.out.println(traversal); // Example Output: [0, 1, 3, 2, 4]
    }
}

3. Iterative DFS: Using an Explicit Stack

While recursion is elegant, it can lead to a StackOverflowError if the graph is very deep. An iterative approach using an explicit Stack data structure avoids this and gives you more control. It perfectly mimics what the recursive call stack does behind the scenes.

The algorithm for iterative DFS is:

1. Create a Stack and push the starting node onto it.
2. Create a visited array/set.
3. Loop as long as the stack is not empty:
   a. Pop a node u from the stack.
   b. If u has already been visited, continue to the next iteration.
   c. Mark u as visited and add it to the result.
   d. Iterate through the neighbors of u and push all unvisited neighbors onto the stack.

This process is demonstrated very clearly in the following video.

Complete Iterative Implementation

Here is the full Java code for an iterative DFS. This example uses a HashSet for the visited tracker, which is also a common and effective approach.

import java.util.*;

public class DFSIterative {

    public static List<Integer> dfsTraversal(int V, ArrayList<ArrayList<Integer>> adj, int startNode) {
        List<Integer> result = new ArrayList<>();
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();

        stack.push(startNode);

        while (!stack.isEmpty()) {
            int u = stack.pop();

            // If we've already visited this node, skip it.
            // This is important because a node can be pushed to the stack multiple times
            // by different parents before it gets processed.
            if (visited.contains(u)) {
                continue;
            }

            visited.add(u);
            result.add(u);

            // Get all adjacent vertices of the popped vertex u.
            // Push them to the stack if they haven't been visited.
            // Note: Pushing in this order means we'll visit neighbors in reverse
            // order of the adjacency list. For traversal, this is fine.
            ArrayList<Integer> neighbors = adj.get(u);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int v = neighbors.get(i);
                if (!visited.contains(v)) {
                    stack.push(v);
                }
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        adj.get(0).add(1);
        adj.get(1).add(0);

        adj.get(0).add(2);
        adj.get(2).add(0);

        adj.get(1).add(3);
        adj.get(3).add(1);
        
        adj.get(2).add(4);
        adj.get(4).add(2);
        
        System.out.println("DFS Traversal (Iterative):");
        // Note: For a disconnected graph, you'd need an outer loop like the recursive version.
        List<Integer> traversal = dfsTraversal(V, adj, 0);
        System.out.println(traversal); // Example Output: [0, 1, 3, 2, 4]
    }
}

4. Complexity Analysis

For both the recursive and iterative versions, the complexity is the same and is a crucial point for interviews.

• Time Complexity: O(V + E)

  • V is the number of vertices, and E is the number of edges.
  • Each vertex is visited (pushed/popped or entered in a recursive call) exactly once. This accounts for the O(V) part.
  • We iterate through the adjacency list of every vertex. Since the sum of the lengths of all adjacency lists is 2*E for an undirected graph (or E for a directed one), we examine each edge. This accounts for the O(E) part.

• Space Complexity: O(V)

  • The visited array/set requires O(V) space.
  • The recursion call stack (for recursive DFS) or the explicit Stack (for iterative DFS) in the worst case can hold up to V vertices. This happens in a graph that is a single long chain. So, the auxiliary space is O(V).

Conclusion

You have now implemented the two most fundamental graph traversal algorithms: BFS and DFS. Understanding their differences is key to knowing when to apply them.

Key Takeaways:

• DFS explores a graph by going as deep as possible down a path before backtracking.
• It can be implemented recursively, where the call stack manages backtracking, or iteratively, using an explicit Stack.
• The time complexity is O(V + E), and space complexity is O(V), similar to BFS.
• The specific traversal path depends on the order of neighbors in the adjacency list.
• Handling disconnected graphs requires an outer loop to ensure all vertices are visited.

Preview of the Next Lesson:
Now that we have mastered BFS and DFS traversals, we can start applying them to solve classic graph problems. In our next lesson, we will use these new skills to detect a cycle in an undirected graph. You'll see how the properties of both traversal methods can be cleverly used to identify back edges, which are the tell-tale sign of a cycle.