Recursive DFS for Graph Traversal

The Philosophy of DFS: Go Deep, then Backtrack

At its heart, Depth-First Search is a simple yet powerful idea. Imagine you are an explorer in a labyrinth. You start at an entrance, pick a passage, and follow it as deep as you can. You keep going, always choosing a new, unexplored turn at every junction. Only when you hit a dead end do you backtrack to the last junction where you had an alternative path, and then explore that one as deeply as possible. You repeat this process until you have mapped out every part of the maze reachable from your starting point.

This "go deep first" strategy is exactly what DFS does. It traverses a graph by exploring as far as possible along each branch before backtracking.

The video below from the Reducible channel provides an excellent, intuitive walkthrough of this process. It frames the algorithm as something you might invent yourself when tasked with exploring a graph.

To visualize this step-by-step, let's look at a simple tree. A tree is a special kind of graph, and its structure makes the DFS traversal path very clear.

The sequence of visits is:

1. Start at 1.
2. Go to a neighbor, 2.
3. From 2, go to a neighbor, 4. Node 4 is a leaf (a dead end).
4. Backtrack to 2.
5. From 2, explore its other neighbor, 5. Node 5 is also a leaf.
6. Backtrack to 2. All of 2's neighbors are explored.
7. Backtrack to 1.
8. From 1, explore its other neighbor, 3. Node 3 is a leaf.
9. The traversal is complete. The final DFS ordering is 1 → 2 → 4 → 5 → 3.

As the Reducible video pointed out, the exact order depends on which neighbor you choose to visit first at each step. If we had chosen to visit 3 before 2 from node 1, the order would have been 1 → 3 → 2 → 4 → 5. Both are valid DFS traversals. In competitive programming, the order is typically determined by the order of edges in your adjacency list.

Implementing DFS with Recursion

The "backtracking" nature of DFS is a strong hint that recursion is a natural way to implement it. When we move from vertex u to an unvisited neighbor v, we are essentially starting a new, smaller DFS from v. Once that recursive call for v fully explores everything reachable from it and returns, we are back at u, ready to explore its next unvisited neighbor.

But there's a critical catch. What happens if the graph has a cycle, for example, an edge from v back to u? If we're not careful, our dfs(u) would call dfs(v), which would then immediately call dfs(u) again, leading to an infinite recursion.

To solve this, we need to keep track of the vertices we have already visited. A simple boolean array, often called visited, is perfect for this. Before we recursively call DFS on a neighbor, we first check if it has already been visited.

The following video segment explains this recursive structure and the necessity of the visited array beautifully.

Now let's translate this logic into C++ code. The structure is remarkably simple and directly follows the logic we've discussed. We will use an adjacency list (vector<vector<int>>) to represent the graph, as established in the previous lesson.

The resource from cp-algorithms.com provides a clean, minimalistic implementation that's perfect for our needs.

Let's break down that C++ code.

// Assume these are defined globally or passed as parameters
vector<vector<int>> adj; // Adjacency list
vector<bool> visited;   // Visited array

void dfs(int u) {
    // 1. Mark the current vertex as visited.
    visited[u] = true;

    // Optional: Process the vertex 'u' upon visiting it.
    // For example, print it to see the traversal order.
    cout << u << " ";

    // 2. Iterate through all neighbors of 'u'.
    for (int v : adj[u]) {
        // 3. If a neighbor 'v' has not been visited,
        //    make a recursive call from 'v'.
        if (!visited[v]) {
            dfs(v);
        }
    }
}

This function is the core of DFS. To perform a traversal on a graph, you would typically set up the adjacency list, initialize the visited array to all false, and then make the first call, e.g., dfs(start_node).

The take U forward channel provides a fantastic, detailed walkthrough of this exact code, tracing its execution on an example graph and showing how the visited array and recursive call stack interact.

A Complete Program for a Single Component

For competitive programming, you'll need a complete program that handles input and output. Here is a standard template for running DFS on a connected graph (or a single connected component) starting from node 1.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> adj;
vector<bool> visited;

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";

    for (int v : adj[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m; // n = number of vertices, m = number of edges
    cin >> n >> m;

    // Resize data structures. Using n+1 for 1-based indexing.
    adj.resize(n + 1);
    visited.resize(n + 1, false);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        // For an undirected graph
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cout << "DFS traversal starting from node 1: ";
    // Start the DFS from a given source, e.g., node 1
    dfs(1);
    cout << endl;

    return 0;
}

This structure is very common. It reads the graph, builds the adjacency list, and then kicks off the traversal. If the graph might be disconnected (i.e., have multiple components), you would wrap the dfs call in a loop:

for (int i = 1; i <= n; ++i) {
    if (!visited[i]) {
        // This will start a new DFS for each unvisited component
        dfs(i);
    }
}

We will explore this specific application for finding connected components in a future lesson.

Complexity Analysis

Understanding the performance of an algorithm is critical.

• Time Complexity: The dfs function is called exactly once for each vertex. Inside each call, we iterate through the neighbors of that vertex. Over the entire execution of the algorithm, each edge (u, v) is considered twice (once from u's adjacency list and once from v's). Therefore, the total time complexity is proportional to the number of vertices plus the number of edges: $O(V+E)$.
• Space Complexity:
  • The adjacency list requires $O(V+E)$ space.
  • The visited array requires $O(V)$ space.
  • The recursion call stack depth can be, in the worst case, $O(V)$ (for a graph that is a single long path).
  • Thus, the total space complexity is $O(V+E)$.

This linear time complexity makes DFS highly efficient and suitable for the large graphs often seen in programming contests.

Conclusion

In this lesson, you've learned the fundamental principles of Depth-First Search and how to implement it using recursion. This is a significant first step into the world of graph algorithms.

Key Takeaways:

• DFS explores deeply: It follows a single path as far as possible before backtracking.
• Recursion is a natural fit: The process of exploring from a neighbor is a recursive subproblem.
• A visited array is essential: It prevents infinite loops in graphs with cycles and ensures each vertex is processed only once.
• The implementation is efficient: With an adjacency list, DFS runs in $O(V+E)$ time and space, making it ideal for typical contest problems.

We've now covered one of the two main pillars of graph traversal. In the next lesson, we will explore its counterpart: Breadth-First Search (BFS). While DFS goes deep, BFS explores wide, level by level. You will learn how this different strategy is implemented iteratively with a queue and how it gives rise to a very important property: finding the shortest path in an unweighted graph.