Graph Traversal: Depth-First Search (DFS)

1. The Core Idea: The Adventurous Explorer

Where BFS explores broadly, like ripples in a pond, DFS behaves like an explorer in a maze. It picks a path and follows it to the very end. Only when it hits a dead end (or a previously visited location) does it backtrack to the last junction and try a different, unexplored path.

This "go deep, then backtrack" strategy is the essence of DFS. The following video provides an excellent intuitive introduction to this concept.

The key takeaways from the video are:

• Depth-first exploration: Always move to an unvisited neighbor if one is available.
• Backtracking: When you reach a vertex with no unvisited neighbors, you return to the vertex from which you came and try another path.
• Order dependency: The specific DFS path depends on the order in which you decide to visit neighbors at each junction.

2. Implementing DFS

Because of its backtracking nature, DFS can be implemented very naturally using recursion. However, understanding the iterative approach with an explicit stack is also valuable, as it draws a direct parallel to BFS's use of a queue.

The Recursive Approach

Recursion is the most common and often most elegant way to write DFS. A recursive function that calls itself for each unvisited neighbor perfectly models the "go deep" behavior. The act of returning from a function call is the "backtrack" step. The program's call stack implicitly manages the traversal state for us.

Just as with BFS, a critical component is a visited array or set. This prevents the algorithm from re-visiting nodes and getting caught in an infinite loop if the graph contains cycles.

This image beautifully connects the recursive code, the graph, and the state of the call stack during a DFS traversal.

For a detailed walkthrough of the implementation, the next video explains the logic line by line, linking it directly to the recursive function calls.

The recursive pseudocode is simple and powerful:

DFS(graph, vertex, visited):
  mark vertex as visited
  // process vertex here (e.g., add to a list)

  for each neighbor of vertex:
    if neighbor has not been visited:
      DFS(graph, neighbor, visited)

The Iterative Approach

To implement DFS iteratively, we simply replace the implicit call stack of recursion with an explicit Stack data structure. This makes its relationship to BFS very clear:

• BFS uses a Queue (First-In, First-Out), leading to a level-by-level search.
• DFS uses a Stack (Last-In, First-Out), leading to a depth-first search.

The algorithm works as follows:

1. Initialize a stack and push the starting vertex onto it.
2. While the stack is not empty:
   a. Pop a vertex from the top of the stack. Let's call it current.
   b. If current has not been visited:
   i. Mark current as visited and process it.
   ii. Get all adjacent neighbors of current.
   iii. Push each unvisited neighbor onto the stack.

The Reducible video you watched earlier also contains a clear segment explaining this iterative process.

For a quick textual reference on the algorithm and code in multiple languages, the Programiz article on DFS is a useful resource.

3. Complexity Analysis

One of the most interesting aspects of DFS is that its performance characteristics are identical to BFS, even though its behavior is completely different.

• Time Complexity: $O(|V|+|E|)$

  • Each vertex is visited exactly once (pushed onto the stack or passed to a recursive call). This accounts for the $O(|V|)$ term.
  • When we visit a vertex, we iterate through its adjacency list. Over the entire execution of the algorithm, we examine every edge in the graph once (for directed graphs) or twice (for undirected graphs). This accounts for the $O(|E|)$ term.
  • Therefore, the total time complexity is $O(|V|+|E|)$.

• Space Complexity: $O(|V|)$

  • The visited array requires $O(|V|)$ space.
  • The stack (either the implicit call stack for recursion or an explicit one) is the other main consumer of space. In the worst-case scenario, such as a graph that is a single long chain, the stack might need to hold all $|V|$ vertices at once. Thus, the space complexity is $O(|V|)$.

For a more detailed breakdown of this analysis, especially considering different graph representations, the following article provides a thorough explanation.

Conclusion

In this lesson, we have thoroughly examined Depth-First Search, the "deep" counterpart to BFS. We've seen how its strategy of exploring as far as possible before backtracking can be elegantly implemented using recursion.

Key Takeaways:

• DFS explores a graph by going as deep as possible down a path before backtracking.
• It is most naturally implemented recursively, where the call stack manages the traversal state. It can also be implemented iteratively with an explicit stack.
• A visited set is crucial to avoid infinite loops in graphs with cycles.
• Despite its different traversal order, DFS has the same time complexity as BFS: $O(|V|+|E|)$.
• The space complexity is $O(|V|)$, dominated by the visited set and the maximum depth of the recursion stack.

Preview of the Next Lesson:

Now that you have both BFS and DFS in your algorithmic toolkit, we can start applying them to solve specific problems. In our next lesson, we will focus on cycle detection. We will explore how both DFS and BFS can be adapted to determine if a graph contains a cycle, and we will see why the properties of DFS make it particularly well-suited for this task.