Implementing Recursive Depth-First Search with Cycle Detection

In our previous lesson, we explored how to traverse a graph layer by layer using Breadth-First Search (BFS) and a queue, which is the perfect tool for finding the shortest path in unweighted graphs. Now, we'll turn our attention to the other fundamental graph traversal algorithm: Depth-First Search (DFS).

Where BFS cautiously explores all immediate neighbors before moving on, DFS is an adventurous explorer. It picks a path and follows it as deeply as possible, only backtracking when it hits a dead end. This "dive deep, then backtrack" strategy is powered by a stack—or, as you'll see today, the implicit call stack of a recursive function. By the end of this lesson, you will be able to implement recursive DFS and use a crucial mechanism—a visited set—to correctly handle graphs with cycles.

The Philosophy of DFS: Exploring a Maze

Imagine you're in a maze. A good strategy is to follow a single path, marking your trail with chalk. You keep going down the path until you hit a wall. At that point, you backtrack to the last intersection where you had an unexplored option and try that new path. You repeat this until you've explored all paths from the entrance.

This is precisely the intuition behind Depth-First Search.

• Go deep: From your current location (node), pick one unvisited neighbor and immediately move to it.
• Repeat: From that new node, again pick an unvisited neighbor and go deeper.
• Backtrack: When you reach a node with no unvisited neighbors (a dead end), you return to the node you came from and see if it has any other unexplored paths.

The video "Depth First Search (DFS) Explained" from Reducible provides an excellent visualization of this "bold explorer" approach. Watch the first part to build a strong mental model of how DFS explores a graph.

As the video highlights, the order of traversal depends on which neighbor you choose to visit first at each step. In an interview setting, you'd typically be told to visit neighbors in a specific order (e.g., sorted numerically or alphabetically) to get a deterministic result.

The Power of Recursion and the Call Stack

This "go deep and backtrack" behavior maps perfectly to recursion. A recursive function call is like stepping deeper into the maze. When the function returns, it's like backtracking to the previous intersection. The call stack, a fundamental concept in programming that you use every day, naturally provides the LIFO (Last-In, First-Out) behavior needed for DFS.

The video from Coderbyte offers a clear explanation of how the call stack implicitly manages the traversal for us.

The Problem with Cycles

Let's try to sketch out a naive recursive algorithm based on this idea:

// Naive, incorrect DFS
function dfs(node) {
    console.log("Visiting:", node);
    for (const neighbor of getNeighbors(node)) {
        dfs(neighbor);
    }
}

What happens if we run this on a graph with a cycle, like A -> B -> A?

1. dfs('A') is called. It prints "A".
2. It calls dfs('B') for its neighbor.
3. dfs('B') prints "B".
4. It calls dfs('A') for its neighbor.
5. dfs('A') prints "A".
6. It calls dfs('B')... and we have an infinite loop, which will quickly lead to a stack overflow error.

To solve this, we must keep track of the nodes we have already visited, just like leaving chalk marks in the maze. We will not visit a node that already has a mark. This is the central purpose of the visited set.

The Reducible video also demonstrates this exact problem and introduces the visited set as the solution.

Implementing Recursive DFS in TypeScript

Now, let's put it all together into a correct and robust implementation. We'll use a Set for our visited tracker, as it provides constant-time add and has operations.

Our structure will consist of a main dfs function that initializes the process and a recursive traverse helper function that contains the core logic.

function dfs<T extends string | number>(
    adjacencyList: Map<T, T[]>,
    startNode: T
): T[] {
    const visited = new Set<T>();
    const result: T[] = [];

    // The recursive helper function
    function traverse(vertex: T) {
        // Base Case: If the vertex has been visited, do nothing.
        if (visited.has(vertex)) {
            return;
        }

        // 1. Mark the vertex as visited.
        visited.add(vertex);
        // 2. Add it to our result list.
        result.push(vertex);

        // 3. Recursive Step: For each neighbor, call traverse.
        const neighbors = adjacencyList.get(vertex) || [];
        for (const neighbor of neighbors) {
            traverse(neighbor);
        }
    }

    // Start the traversal from the given start node.
    traverse(startNode);

    return result;
}

// Example usage:
const adjList = new Map<string, string[]>();
adjList.set('A', ['B', 'C']);
adjList.set('B', ['A', 'D']);
adjList.set('C', ['A', 'E']);
adjList.set('D', ['B', 'E', 'F']);
adjList.set('E', ['C', 'D', 'F']);
adjList.set('F', ['D', 'E']);

const traversalOrder = dfs(adjList, 'A');
console.log(traversalOrder); // e.g., ['A', 'B', 'D', 'E', 'C', 'F']

This implementation, based on the pattern in the "JavaScript for Implementing Depth First Search" article, correctly handles cycles and explores the entire connected component starting from startNode.

The animation below shows this process on a directed graph. The orange nodes represent nodes currently in the recursion stack (the "path" you're on), while red is the single node being processed. Green nodes are unvisited. Notice how the traversal dives deep and how an edge pointing to an orange or red node would indicate a cycle.

Complexity

Understanding the performance of your algorithms is critical. Fortunately, the analysis for DFS is straightforward and identical to BFS.

• Time Complexity: O(V + E)

  • V is the number of vertices, and E is the number of edges.
  • Each vertex is visited exactly once because of the visited set. This accounts for the O(V) part.
  • When we visit a vertex, we iterate through its list of neighbors. Over the entire traversal, we will have looked at every edge exactly once (or twice for an undirected graph). This accounts for the O(E) part.

• Space Complexity: O(V) or more precisely O(H)

  • The visited set can store up to V vertices.
  • The recursion call stack will go as deep as the longest path from the start node, which we denote as H (height or max depth). In the worst case (a long, straight-line graph), H can be equal to V. This is why stack overflow is a risk for extremely deep graphs.

The VisuAlgo resource provides a concise summary of this complexity analysis.

Conclusion

You have now learned the second major graph traversal algorithm, Depth-First Search. While BFS uses a queue to explore level by level, DFS uses a stack (often the implicit call stack) to explore as deeply as possible before backtracking.

Key Takeaways:

• DFS explores depth-first, following a path to its end before backtracking.
• Recursion is a natural way to implement DFS, using the call stack to manage the traversal order.
• A visited set is essential to prevent infinite loops when traversing graphs that contain cycles.
• The time complexity is O(V + E), and the space complexity is proportional to the maximum depth of the recursion, O(H).

In our next lesson, we will put this new skill to practical use. We'll tackle a common interview problem: counting the number of connected components in a grid. You will see how treating adjacent cells in a grid as graph neighbors allows you to apply DFS (or BFS) to solve a whole new class of problems.