DFS — Explained with Examples

DFS (Depth-First Search) is a graph traversal algorithm that explores as far as possible along each branch before backtracking.

DFS uses a stack (explicitly or via recursion) to track the traversal path. It goes deep into one branch before exploring alternatives. For trees, DFS supports three traversal orders: preorder (root, left, right), inorder (left, root, right — yields sorted order in BSTs), and postorder (left, right, root). Time complexity is O(V + E).

Think of DFS like exploring a cave system. You pick a tunnel and follow it until it ends or loops back, marking your path as you go. When you hit a dead end, you backtrack to the last junction and try the next tunnel. You systematically explore every passage.

DFS is used for topological sorting, detecting cycles in graphs, solving mazes, finding connected components, and tree traversals. Its recursive implementation is elegant but risks stack overflow on deep graphs.

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=" ")

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

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

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=" ")
            stack.extend(reversed(graph[node]))

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

dfs_recursive(graph, 'A')  # Output: A B D E F C

DFS uses less memory than BFS on wide graphs but does not guarantee shortest paths. Choose DFS when exploring complete pathways or when memory is constrained.

BFS, Tree, Graph, Recursion, Backtracking

Backtracking with DFS