Overview

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure, which can be explicitly implemented or implicitly managed via recursive function calls. The algorithm begins at a specified starting node, marks it as visited, and explores its first unvisited neighbor. This process continues recursively, diving deeper into the graph until a dead-end (node with no unvisited neighbors) is reached. At this point, the algorithm backtracks to explore alternative paths.

DFS has numerous applications in computer science. It is widely used in pathfinding problems, such as navigating a maze or solving puzzles. It is also essential for cycle detection in graphs, topological sorting for dependency resolution, and connected component analysis to identify distinct subgraphs. In artificial intelligence, DFS is employed for exhaustive state-space searches, such as solving n-queens problems or traversing decision trees.

How It Works

DFS works by:

1. Starting at a specified node and marking it as visited
2. Exploring the first unvisited neighbor
3. Recursively applying DFS to that neighbor
4. Backtracking when no unvisited neighbors remain
5. Continuing until all reachable nodes are visited

The "depth-first" nature means the algorithm goes as deep as possible before exploring other branches, creating a path that goes from the root to a leaf before backtracking.

DFS Algorithm Pseudocode

DFS(node):
    if node is NULL:
        return
    mark node as visited
    for each neighbor in node.children:
        if neighbor is not visited:
            DFS(neighbor)
                

Implementation

Recursive Implementation

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start)  # Process node
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    
    return visited
                

Iterative Implementation (Using Stack)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            print(node)  # Process node
            
            # Add neighbors to stack (reverse order to maintain DFS order)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return visited
                

Complexity Analysis

• Time Complexity: O(V + E) - where V is the number of vertices and E is the number of edges. Each vertex and edge is visited once.
• Space Complexity:
  • O(V) for recursive implementations (stack overhead)
  • O(V) for iterative implementations (explicit stack)
  • O(E) for adjacency list storage

Common Trends in Graph Problems where DFS is Applied

• Recursive Nature: Many problems can be solved by breaking them into smaller subproblems, making recursion a natural fit.
• State Tracking: Keep track of visited nodes, current path, or accumulated values for problems like finding paths or sums.
• Base Cases: Clearly define when traversal should stop, such as when reaching a leaf node or a visited node.
• Backtracking: Undo changes made during a path when exploring other possibilities, especially in puzzles or pathfinding problems.
• Cycle Detection: Use techniques like recursion stacks for detecting cycles in directed graphs.

DFS Framework

• Start at the root or specified node and mark it as visited.
• Use recursion or a stack to explore neighbors or children.
• Implement clear base cases to handle stopping conditions.
• Track necessary state, like visited nodes or current path.
• Use backtracking when exploring all possible solutions is required.

Applications

• Pathfinding: Finding paths in mazes or graphs
• Cycle Detection: Detecting cycles in directed and undirected graphs
• Topological Sorting: Ordering nodes based on dependencies
• Connected Components: Finding all nodes reachable from a starting node
• Tree/Graph Traversal: Exploring tree structures
• Puzzle Solving: Solving problems like n-queens, sudoku

Popular LeetCode Questions Using DFS

                    
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)

        return 1 + max(left, right)
                    
                    

                    
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return root.val == targetSum
        
        left = self.hasPathSum(root.left, targetSum - root.val)
        right = self.hasPathSum(root.right, targetSum - root.val)

        return left or right
                    
                    

Related Algorithms

Explore other graph algorithms:

• Breadth-First Search (BFS) - Level-by-level traversal
• Back to Graph Algorithms Overview