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.

Historical Origins in Maze-Solving

The idea of depth-first search predates computer science by nearly a century. The algorithm's essential mechanic, go as deep as you can along one path, back up when you hit a dead end, remember where you have been, was formalised by the French mathematician Charles Pierre Trémaux in the 1880s as a systematic method for solving mazes. Trémaux's algorithm, still taught in recreational mathematics courses, involves marking each junction and each corridor as you traverse it, with a simple rule for deciding which direction to go next based on whether the mark count is zero, one, or two. Follow the rules and you will find the exit if one exists, and the marks you leave behind constitute a proof of correctness, you will never walk down the same corridor more than twice in each direction.

The algorithm was rediscovered and formalised in the computer-science sense by John Hopcroft and Robert Tarjan in a 1973 paper "Algorithm 447: Efficient Algorithms for Graph Manipulation." Hopcroft and Tarjan's contribution was not the traversal itself, that was well-known, but the observation that DFS's structural properties enable a whole family of algorithms that had previously required more complex techniques. They showed how DFS could compute strongly connected components, biconnected components, planarity testing, and more, all in linear time O(V + E). Their paper and the subsequent work it inspired earned Hopcroft and Tarjan the Turing Award in 1986.

Tarjan's later single-scan SCC algorithm (1972) and the two-pass Kosaraju algorithm (unpublished but well-known) are both variations on DFS-plus-postorder-numbering, and they are among the most beautiful algorithms in the field, a single traversal of the graph, combined with a stack and some counter arithmetic, computes structural properties that would otherwise take much more work to determine.

DFS Edge Classification

A DFS traversal implicitly partitions the edges of the graph into four categories, and understanding this partition is what makes DFS-based algorithms possible.

• Tree edges: edges that lead to unvisited vertices when traversed, the edges that form the DFS tree. Every visited vertex except the source has exactly one tree edge leading to it.
• Back edges: edges (u, v) where v is an ancestor of u in the DFS tree, that is, v is currently on the recursion stack. The presence of a back edge is the definition of a cycle in the graph: any back edge closes a cycle consisting of the back edge itself and the tree-edge path from v down to u. Cycle detection in a directed graph reduces to detecting a back edge during DFS.
• Forward edges: edges (u, v) where v is a descendant of u in the DFS tree but not directly connected by a tree edge (a "shortcut" down the tree). Only possible in directed graphs.
• Cross edges: edges (u, v) where u and v have no ancestor-descendant relationship in the DFS tree, e.g. they are in different subtrees. Also only in directed graphs.

The classification is easy to compute during the traversal itself: maintain a "colour" for each vertex (WHITE = not yet visited, GRAY = on the recursion stack, BLACK = finished), and classify each edge when it is examined:

• WHITE target ⇒ tree edge
• GRAY target ⇒ back edge
• BLACK target and discovery time of target > discovery time of source ⇒ forward edge
• BLACK target and discovery time of target < discovery time of source ⇒ cross edge

Note that an undirected graph's DFS has only tree and back edges, there are no forward or cross edges, because every edge in an undirected graph is traversed in both directions during DFS and one of the traversals establishes the tree edge.

Algorithms Built on DFS

A remarkable number of important graph algorithms are essentially "run DFS and record some extra bookkeeping." Understanding this reduces a whole family of problems to variations of the same underlying template.

Topological Sort

Ordering the vertices of a directed acyclic graph so that every edge points from an earlier vertex to a later one. The DFS-based algorithm is elegantly simple: run DFS, and when a vertex finishes (its DFS call returns), prepend it to a list. The reversed finish order is a valid topological order. If DFS ever finds a back edge, the graph has a cycle and no topological order exists. Build systems (make, Bazel, Cargo's dependency resolver) use this algorithm to determine the order to compile files. Python's graphlib.TopologicalSorter and Java's TopologicalSort in various libraries all use DFS internally.

Strongly Connected Components

A strongly connected component (SCC) of a directed graph is a maximal set of vertices such that every vertex in the set is reachable from every other. SCCs partition the vertices; the "SCC graph" (with SCCs as super-nodes) is a DAG. Tarjan's 1972 algorithm computes all SCCs in a single DFS pass by tracking a "lowlink" value per vertex, the smallest discovery time reachable from that vertex via any combination of tree, back, and cross edges. When a vertex's DFS call finishes with lowlink equal to its own discovery time, all vertices currently on an auxiliary stack above it form an SCC. Kosaraju's alternative algorithm uses two DFS passes on the graph and its transpose. Both are O(V + E).

Biconnected Components and Bridges

An articulation point is a vertex whose removal disconnects the graph; a bridge is an edge whose removal does. These are critical failure points in a network: a single-router path from one subnet to another passes through an articulation point. Tarjan's DFS-based algorithm for finding all articulation points and bridges runs in a single pass by tracking discovery times and lowlink values, the same machinery as SCC computation, in a different arrangement.

Bipartite Testing and 2-Colouring

A graph is bipartite (2-colourable) if and only if it contains no odd-length cycle. DFS can colour the graph alternately as it descends, and if it ever tries to give a vertex a colour different from one it already has, the graph is not bipartite. This is O(V + E) and the standard method for testing bipartiteness in practice.

Cycle Detection in Directed Graphs

As mentioned above: a directed graph has a cycle if and only if DFS finds a back edge. In an undirected graph, DFS finds a cycle when it encounters a visited vertex that is not its parent. Both variations are O(V + E).

When DFS Beats BFS (and Vice Versa)

DFS and BFS have identical time and space complexity (O(V + E) and O(V)) but very different behaviour, and choosing between them is a real engineering decision.

• Use DFS when the answer is defined by structure or reachability, topological sort, cycle detection, connected components, SCC, bridges, maze paths. Anything where you want to visit "everything reachable" without caring about how far things are.
• Use BFS when distance matters, shortest path in an unweighted graph, level-order tree traversal, "find the closest" problems. BFS's frontier expansion gives it the shortest-path property that DFS does not.
• DFS uses less memory on average. DFS's stack depth is O(diameter); BFS's queue can hold O(width). For trees these are usually about the same order; for wide flat graphs BFS uses much more memory; for narrow deep graphs DFS uses much more.
• DFS can be written recursively. This is a real advantage for code clarity when the problem has a natural recursive shape, but a real disadvantage when the graph is deep enough to overflow the call stack. Python's default recursion limit of 1000 makes recursive DFS unsuitable for large linear chains, use the iterative version with an explicit stack when the graph might be deep.

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