Depth-First Search (DFS)

Depth-First Search (DFS) is one of the most fundamental graph traversal algorithms in computer science. The central idea is elegantly simple: starting from a chosen source node, explore as far as possible along each branch of the graph before backtracking to try alternative paths. Imagine navigating a maze by always following the left-hand wall — you commit fully to one direction, going deeper and deeper, and only retreat when you hit a dead end before trying the next corridor. This "go deep first" philosophy gives the algorithm both its name and its distinctive behavior, and it is the root cause of nearly every important property DFS possesses — from cycle detection to topological ordering to connectivity analysis.

DFS applies equally well to trees, directed graphs, and undirected graphs. On a tree there are no cycles to worry about, so DFS simplifies to a familiar recursive traversal. On a general graph, cycles can cause the search to loop forever, so a mechanism for remembering which nodes have already been seen becomes essential. Understanding how that bookkeeping interacts with the traversal order is the key to mastering DFS.

DFS Core Concept and Strategy

At its heart, DFS relies on a last-in, first-out (LIFO) structure to decide which node to visit next. This can be the program's own call stack when DFS is written recursively, or an explicit stack data structure when written iteratively. Either way, the effect is the same: the most recently discovered unvisited neighbor is always the next to be explored, naturally pushing the traversal deeper before it goes wider.

The second pillar of DFS is the visited set (sometimes a boolean array indexed by node id, sometimes a hash set). Before exploring a node, the algorithm checks whether it has already been seen. If it has, processing stops for that branch. If it has not, the node is marked visited and its neighbors are queued for exploration. Without this guard, any cycle in the graph — even a simple edge from node B back to node A — would send the algorithm into an infinite loop.

The precise traversal order produced by DFS depends on the order in which a node's neighbors are stored. Consider a node with neighbors listed as [C, B, D]. DFS will first go toward C, exhausting all of C's descendants, before it ever looks at B or D. If the adjacency list instead stored them as [D, B, C], the traversal would unfold in a completely different sequence even though the graph is identical. This sensitivity to neighbor ordering is worth keeping in mind whenever DFS results are compared between implementations.

Recursive DFS Implementation

The recursive implementation is the most natural expression of the DFS idea. Each function call represents visiting one node; the call stack itself acts as the LIFO structure that tracks the traversal path. The code is compact and mirrors the algorithm's description almost word for word.

def dfs_recursive(graph, node, visited):
    # Base case: if already visited, do nothing
    if node in visited:
        return
    # Mark the node visited and process it
    visited.add(node)
    print(node)   # or append to a result list
    # Recurse on each unvisited neighbor
    for neighbor in graph[node]:
        dfs_recursive(graph, neighbor, visited)

The base case is the visited check. When the algorithm reaches a node it has already processed — which happens when the graph contains a cycle or when multiple paths lead to the same node — the function returns immediately without duplicating work. This single guard is responsible for the guarantee that each node is processed exactly once, giving DFS an overall time complexity of O(V + E) where V is the number of vertices and E is the number of edges.

The recursive call dfs_recursive(graph, neighbor, visited) processes one neighbor at a time. Crucially, the loop does not advance to the next neighbor until the recursive call for the current neighbor has returned completely — meaning the entire subtree rooted at that neighbor has been explored first. This is exactly the "go deep before going wide" behavior that defines DFS.

The primary limitation of recursive DFS is stack overflow. Every active function call occupies a frame on the program's call stack, and most language runtimes cap the call stack at a few thousand frames. On a long linear chain of 100,000 nodes, the recursion depth reaches 100,000 — far beyond the default limit in Python (around 1,000) or Java (roughly 500–1,000 depending on frame size). For small to medium graphs this is rarely a concern, but production systems operating on large or user-supplied graphs usually prefer the iterative version.

Iterative DFS Implementation

The iterative approach replaces the implicit call stack with an explicit one. The logic closely mirrors the recursive version but avoids call-stack limitations and gives the programmer full control over the stack's contents.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()          # LIFO: most recently pushed node
        if node in visited:
            continue
        visited.add(node)
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return visited

Execution proceeds as follows. The start node is pushed onto the stack. The main loop pops the top element, checks whether it was already visited (which can happen because the same node may be pushed multiple times before being popped), marks it visited, processes it, and then pushes all unvisited neighbors. Because the stack is LIFO, the last neighbor pushed will be the first one explored.

There is a subtle but important difference between recursive and iterative DFS regarding traversal order. Consider a node with neighbors [A, B, C]. The recursive version iterates the list in order and recurses on A first, so A is explored entirely before B or C are touched. The iterative version pushes A, B, C onto the stack in that order; when they are popped, C comes off first (LIFO), then B, then A. To make iterative DFS visit neighbors in the same left-to-right order as recursive DFS, push neighbors in reverse order:

for neighbor in reversed(graph[node]):
    if neighbor not in visited:
        stack.append(neighbor)

This is a common source of confusion in interview settings — knowing that the orders can diverge, and why, demonstrates a deep understanding of the algorithm.

DFS Traversal Order and Visited Tracking

The moment a node is marked visited is a design choice with real consequences. In most implementations, nodes are marked as soon as they are first encountered (either at the point of pushing onto the stack or at the start of the recursive call). This ensures no node is processed more than once.

DFS naturally produces two important orderings that are widely used in practice:

• Pre-order: A node is recorded before any of its descendants are explored. This is what the code examples above do — print(node) happens right after marking it visited. Pre-order is useful for creating a copy of a graph or tree, or for simply listing nodes in discovery order.
• Post-order: A node is recorded after all of its descendants have been fully explored. In the recursive version this means placing the recording step after the loop over neighbors. Post-order is the foundation of topological sort — because a node is recorded only after everything reachable from it is recorded, reversing the post-order list gives a valid topological ordering for a DAG.

def dfs_postorder(graph, node, visited, result):
    if node in visited:
        return
    visited.add(node)
    for neighbor in graph[node]:
        dfs_postorder(graph, neighbor, visited, result)
    result.append(node)   # recorded AFTER all descendants

The collection of edges actually traversed by DFS forms a DFS tree (or a DFS forest if the graph is disconnected). Edges in the original graph that are not part of this tree are classified as back edges (pointing to an ancestor in the DFS tree), forward edges (pointing to a descendant), or cross edges (pointing to nodes in a different branch or component). These edge classifications carry algorithmic significance: for example, the presence of any back edge in a directed graph is both necessary and sufficient to conclude the graph contains a cycle.

Handling Disconnected Graphs

A single DFS call from one start node only ever reaches nodes that are reachable from that node — i.e., it explores exactly one connected component. If the graph has isolated nodes or multiple disconnected subgraphs, some nodes will never be reached unless the outer loop restarts DFS from each unvisited node.

def dfs_full(graph):
    visited = set()
    components = []
    for node in graph:
        if node not in visited:
            component = []
            dfs_postorder(graph, node, visited, component)
            components.append(component)
    return components

Every time the outer for loop finds an unvisited node, it means a brand-new connected component has been discovered. The number of times DFS is restarted from an unvisited node is therefore exactly equal to the number of connected components in the graph. This makes the pattern above the standard way to count or enumerate components — a simple, elegant consequence of the visited-set bookkeeping.

Consider the following example graph with three disconnected components:

DFS starts at node 0, visits 0 → 1 → 2, and returns. Node 3 has not been visited, so DFS restarts there and visits 3 → 4. Node 5 has not been visited, so DFS restarts there and immediately finishes. Three restarts, three components: {0,1,2}, {3,4}, and {5}.

Common Use Cases of DFS

DFS is not merely an academic exercise — it is the engine behind a surprisingly wide variety of graph algorithms. Below are the most important applications:

• Cycle detection in undirected graphs: During DFS, if a neighbor of the current node has already been visited and is not the parent through which we arrived, a cycle exists. The parent check is necessary because an undirected edge (u, v) is traversed in both directions; without it, every edge would falsely appear to create a cycle.
• Cycle detection in directed graphs: Maintain a recursion stack (separate from the visited set) tracking all nodes on the current DFS path. If a neighbor is found that is already on the recursion stack, a back edge — and therefore a cycle — has been found. A node is removed from the recursion stack when the DFS call for it returns.
• Topological sorting: On a Directed Acyclic Graph (DAG), run DFS over all nodes and append each node to a result list in post-order. Reversing this list yields a valid topological ordering. This works because a node appears in the result only after all nodes reachable from it (its "dependencies") have already been appended.
• Pathfinding and maze solving: DFS will always find a path between two nodes if one exists, though not necessarily the shortest one. It is the classic algorithm used to solve mazes modeled as grids.
• Strongly Connected Components (SCCs): Algorithms such as Kosaraju's and Tarjan's use one or two DFS passes to decompose a directed graph into its SCCs — maximal subgraphs in which every node is reachable from every other node.
• Graph connectivity and bipartiteness checking: DFS can be used to verify whether a graph is connected (one DFS visits all nodes) and to check for bipartiteness (attempt a two-coloring during DFS; a conflict signals an odd cycle, ruling out bipartiteness).

To concretely illustrate topological sort, consider building a course prerequisite system. Node A must be taken before B, B before C, and A before D:

graph = {
    'A': ['B', 'D'],
    'B': ['C'],
    'C': [],
    'D': [],
}
visited = set()
result = []
for node in graph:
    dfs_postorder(graph, node, visited, result)
print(result[::-1])   # reversed post-order
# Possible output: ['A', 'B', 'D', 'C']  or  ['A', 'D', 'B', 'C']

Both outputs are valid topological orderings: A always appears before B, and B before C. The key guarantee is that every prerequisite appears before the course that depends on it — a direct consequence of the post-order recording rule in DFS.

The table below summarizes the key behavioral differences between recursive and iterative DFS:

Taken together, DFS is a remarkably versatile tool. Its O(V + E) time complexity, intuitive recursive formulation, and deep connections to properties like reachability, ordering, and cycle structure make it one of the first algorithms to reach for when analyzing or processing graph-structured data.