Graph Traversal: DFS Explained

Depth-First Search (DFS) explores a graph by plunging as deep as possible down one path before backtracking — the opposite instinct from BFS's level-by-level spread. Picture exploring a maze by always taking the first available turn and following it to a dead end before trying the next option — that's DFS.

Recursive DFS

DFS maps naturally onto recursion: visit the current vertex, then recursively DFS into each unvisited neighbor. The call stack itself does the work of remembering where to backtrack to.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"]
}

def dfs_recursive(graph, vertex, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(vertex)
    order.append(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)

    return order

print(dfs_recursive(graph, "A"))

Output:

['A', 'B', 'D', 'C', 'E']

Compare this to BFS on the same graph, which visited ['A', 'B', 'C', 'D', 'E'] — DFS dives all the way down through B and D before ever backtracking to try C, while BFS insists on finishing an entire level first.

Iterative DFS with an Explicit Stack

Recursion uses the call stack implicitly, but you can make that stack explicit with a stack data structure instead — useful for very deep graphs where recursion could hit Python's recursion limit.

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)

        # Reversed so the first neighbor is processed first (matches recursive order)
        for neighbor in reversed(graph[vertex]):
            if neighbor not in visited:
                stack.append(neighbor)

    return order

print(dfs_iterative(graph, "A"))

Output:

['A', 'B', 'D', 'C', 'E']

You can see this same traversal applied inside a complete program in the Python DFS program, which shows both the recursive and iterative versions side by side.

Complexity and Use Cases

Like BFS, DFS runs in O(V + E) time (every vertex and edge is examined once) with O(V) space in the worst case for the visited set and the call stack or explicit stack.

DFS is the natural choice whenever you need to explore a structure fully rather than find the shortest path: detecting a cycle in a graph, topological sorting (ordering tasks so dependencies come first), finding connected components, and solving maze-style puzzles where you need to try a path to completion before giving up on it — the same depth-first instinct behind backtracking algorithms in general.