Depth-First Search (DFS)

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(h) auxiliary, where h is the length of the longest path — O(V) in the worst case for both the recursive call stack and the iterative explicit stack. (Storing the graph itself as an adjacency list is a further O(V + E), but that is the input, not the algorithm's overhead.)

Mind the recursion limit. Python caps recursion at 1000 frames by default, so the recursive version raises RecursionError on any graph containing a path longer than that — and a 10,000-node chain or a degenerate tree is not an exotic input. Use the iterative version for graphs whose depth you do not control. Raising sys.setrecursionlimit() is not a real fix, since the underlying C stack can still overflow and crash the interpreter outright.

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.

Edge Classification: The Machinery Behind DFS Applications

Running DFS on a directed graph implicitly sorts every edge into one of four categories, and most of DFS's applications are corollaries of this. Track each vertex's state as white (undiscovered), grey (on the current recursion stack), or black (finished):

• Tree edge — leads to a white vertex. These form the DFS forest.
• Back edge — leads to a grey vertex, i.e. an ancestor on the current stack. A directed graph has a cycle if and only if DFS finds a back edge. That is the entire cycle-detection algorithm.
• Forward edge — leads to a black descendant.
• Cross edge — leads to a black vertex in another subtree.

WHITE, GREY, BLACK = 0, 1, 2

def has_cycle(graph, n):
    """Directed cycle detection via back edges."""
    colour = [WHITE] * n

    def visit(u):
        colour[u] = GREY
        for v in graph[u]:
            if colour[v] == GREY:      # back edge -> cycle
                return True
            if colour[v] == WHITE and visit(v):
                return True
        colour[u] = BLACK
        return False

    return any(colour[u] == WHITE and visit(u) for u in range(n))

Topological sort falls straight out of the same traversal: push each vertex onto a list when it turns black, then reverse the list. Because a vertex finishes only after all its descendants, reverse finishing order is a valid topological order — provided there are no back edges, since a cyclic graph has no topological order at all.

In an undirected graph the classification collapses: only tree and back edges occur, and cycle detection simply means finding an already-visited neighbour that is not the immediate parent.

Two further algorithms build directly on DFS timestamps: Tarjan's and Kosaraju's for strongly connected components, and Tarjan's low-link method for bridges and articulation points.

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