5. Graph Traversal: Depth-First Search (DFS)

Depth-First Search (DFS) is a traversal algorithm that explores the graph by going as "deep" as possible down one path before backtracking.

5.1 DFS Analogy and Illustration

Imagine exploring a maze with only one path.

• You pick a direction (an edge) and follow it.
• You keep going, taking the first available turn at each junction (visiting the first unvisited neighbor).
• You continue until you hit a dead end (a node with no unvisited neighbors).
• At the dead end, you backtrack to the previous junction and try a different path.

DFS works this way. It is excellent for detecting cycles, topological sorting, and solving puzzles.

Example: We want to trace BFS starting from node 0 on the following graph:

      0
     / \
    1---2
   /     \
  3       4

The traversal order will be 0, 1, 2, 4, 3.

5.2 The Role of std::stack

The LIFO (Last-In, First-Out) nature of a stack is perfect for DFS.

• Recursive DFS: The system's call stack is used implicitly. When you make a recursive call DFSUtil(neighbor), you "push" the new function onto the stack. When you hit a dead end, the function returns, "popping" itself off the stack and automatically "backtracking" to the previous node.
• Iterative DFS: We manually use a std::stack. We push a node, then push its neighbors. The last neighbor pushed is on top, so it will be the first one we explore next, perfectly mimicking the "go deep" behavior of recursion.

5.3 DFS Implementation

5.3.1 Iterative Approach

This approach uses an explicit std::stack and avoids recursion.

void DFS(int s) {
    // 1. Create a visited array, initialized to all false
    std::vector<bool> visited(V, false);
    
    // 2. Create a Stack for DFS
    std::stack<int> stack;

    // 3. Push the source vertex onto the stack
    stack.push(s);

    std::cout << "DFS Traversal (Iterative): ";

    // 4. Loop as long as the stack is not empty
    while (!stack.empty()) {
        // 5. Pop a vertex from the top of the stack
        int u = stack.top();
        stack.pop();

        // 6. If it hasn't been visited yet:
        if (!visited[u]) {
            visited[u] = true;
            std::cout << u << " ";
        }
        
        // 7. Get all neighbors of 'u'
        for (auto& neighbor : adj[u]) {
            // 8. If the neighbor is unvisited, push it
            if (!visited[neighbor]) {
                stack.push(neighbor);
            }
        }
    }
    std::cout << std::endl;
}

Code Explanation:

• Initialize a visited array (all false) and an empty stack.
• Push the starting node s onto the stack.
• While the stack is not empty:
  • Pop a node u from the stack.
  • If u has not been visited:
    • Mark u as visited and print it.
    • Iterate through all neighbors of u.
    • If a neighbor has not been visited, push it onto the stack (to be processed next).

5.3.2 Recursive Approach

This is the most common and intuitive way to implement DFS. It uses a helper function.

// Private helper function for recursive DFS
void DFSUtil(int u, std::vector<bool>& visited) {
    // 1. Mark the current node as visited and print it
    visited[u] = true;
    std::cout << u << " ";

    // 2. Iterate over all neighbors
    for (auto& neighbor : adj[u]) {
        // 3. If a neighbor is unvisited:
        if (!visited[neighbor]) {
            // 4. Make a recursive call to "go deeper"
            DFSUtil(neighbor, visited);
        }
    }
    // 5. When all neighbors are visited, the function returns.
    //    This is the implicit "backtracking" step.
}

// Public wrapper function to start the DFS
void DFSRecursive(int s) {
    // 1. Create a visited array
    std::vector<bool> visited(V, false);
    std::cout << "DFS Traversal (Recursive): ";
    
    // 2. Call the helper function to start the recursion
    DFSUtil(s, visited);
    std::cout << std::endl;
}

Code Explanation:

• The DFSRecursive function initializes the visited array.
• It calls the helper function DFSUtil with the starting node s.
• Inside DFSUtil (the recursive part):
  • Marks the current node u as visited and prints it.
  • Iterates through all neighbors of u.
  • If a neighbor has not been visited, it immediately calls DFSUtil on that neighbor, "going deeper."
  • When a node has no unvisited neighbors, its function call finishes and "backtracks" to the previous node's loop.

5.3.3 Comparison: Iterative vs. Recursive

Both recursive and iterative DFS accomplish the same goal, but they differ in implementation and performance characteristics.

In summary:

• Use Recursive DFS for simplicity and clarity, especially when the graph depth is known to be manageable.
• Use Iterative DFS when you need to avoid stack overflow on very deep graphs or when you need finer control over the traversal.