Graph algorithms are the backbone of many real-world systems, from social networks to navigation apps. At their core are traversal techniques that allow us to systematically visit every node and edge in a graph. Among the most fundamental of these is Depth First Search (DFS).

DFS is an intuitive algorithm that, as its name suggests, explores as far as possible along each branch before backtracking. If you’ve ever explored a maze by picking a path and sticking to it until you hit a dead end, then returning to your last choice point, you’ve intuitively performed a DFS.

The Core Idea: Go Deep, Then Backtrack

Imagine you’re exploring a tree, but instead of walking along the branches, you’re literally diving into them. DFS starts at a given node (the “root” for the traversal, even if the graph isn’t a tree) and explores as far as possible along each branch before backtracking. It’s like having a relentless explorer who won’t stop until they’ve hit a dead end, at which point they’ll retrace their steps to the last decision point and try another unexplored path.

This “go deep” behavior is naturally implemented using a stack (either explicitly, or implicitly through recursion). When you visit a node, you push its unvisited neighbors onto the stack. Then, you pop a node from the stack and repeat the process. The last node added to the stack is the first one processed, leading to the “depth-first” exploration.

How DFS Works (Step-by-Step)

1. Start: Pick an arbitrary starting node. Mark it as visited.
2. Explore: For the current node, pick an unvisited neighbor.
3. Recurse/Push: Move to that neighbor, mark it visited, and make it the new current node. Repeat step 2.
4. Backtrack: If the current node has no unvisited neighbors (i.e., you’ve hit a dead end), backtrack to the previous node and try other unvisited neighbors from there.
5. Terminate: Continue until all reachable nodes from the starting node have been visited. If the graph is disconnected, you might need to pick another unvisited starting node to find all components.

Implementing DFS

DFS can be implemented in two primary ways: recursively or iteratively. Both achieve the same result but use different mechanisms for managing the “to-visit” list.

1. Recursive DFS (The Elegant Way)

The recursive approach is often the most concise and elegant. It leverages the call stack of the programming language to manage the backtracking.

Key Components:

• A graph represented, typically as an adjacency list (a dictionary mapping nodes to lists of their neighbors).
• A visited set to keep track of nodes already processed, preventing infinite loops in cyclic graphs and redundant processing.

Let’s set up a simple graph:

A --- B
|     |
C --- D
|
E

Represented as an adjacency list: graph = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D', 'E'], 'D': ['B', 'C'], 'E': ['C']}

Now, the recursive implementation:

# graph_dfs_recursive.py

def dfs_recursive(graph, start_node, visited=None):
    if visited is None:
        visited = set()

    visited.add(start_node)
    print(start_node, end=" ") # Process the node (e.g., print it)

    for neighbor in graph.get(start_node, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# Define our example graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D', 'E'],
    'D': ['B', 'C'],
    'E': ['C']
}

print("DFS Traversal (Recursive, starting from 'A'):")
dfs_recursive(graph, 'A')
print("\n")

# Another example graph
graph2 = {
    '0': ['1', '2'],
    '1': ['2'],
    '2': ['0', '3'],
    '3': ['3']
}

print("DFS Traversal (Recursive, starting from '2' in graph2):")
dfs_recursive(graph2, '2')
print("\n")

DFS Traversal (Recursive, starting from 'A'):
A B D C E 

DFS Traversal (Recursive, starting from '2' in graph2):
2 0 1 3 

Explanation of Output: For the first graph starting at ‘A’:

1. ‘A’ is visited. Neighbors ‘B’, ‘C’. Pick ‘B’.
2. ‘B’ is visited. Neighbors ‘A’, ‘D’. ‘A’ is visited. Pick ‘D’.
3. ‘D’ is visited. Neighbors ‘B’, ‘C’. ‘B’ is visited. Pick ‘C’.
4. ‘C’ is visited. Neighbors ‘A’, ‘D’, ‘E’. ‘A’, ‘D’ are visited. Pick ‘E’.
5. ‘E’ is visited. Neighbors ‘C’. ‘C’ is visited. No unvisited neighbors. Backtrack to ‘C’.
6. From ‘C’, no more unvisited neighbors. Backtrack to ‘D’.
7. From ‘D’, no more unvisited neighbors. Backtrack to ‘B’.
8. From ‘B’, no more unvisited neighbors. Backtrack to ‘A’.
9. From ‘A’, ‘B’ was explored. Now try ‘C’. Oh, ‘C’ is already visited from the ‘D’ path. No new unvisited paths from ‘A’. The traversal path depends on the order of neighbors in the adjacency list. Here, the order is ‘A’ -> ‘B’ -> ‘D’ -> ‘C’ -> ‘E’.

Note: The specific order of visiting nodes in DFS depends on the order of neighbors in your adjacency list. If graph['A'] was ['C', 'B'], the output would be A C D B E. This is a common characteristic of graph traversals – the exact path isn’t strictly defined, only the exploration strategy.

2. Iterative DFS (Using an Explicit Stack)

The iterative approach uses an explicit list (in Python, mimicking a stack with append() and pop()) to manage the nodes to visit. This is useful for avoiding Python’s recursion depth limit for very large or deep graphs.

# graph_dfs_iterative.py

def dfs_iterative(graph, start_node):
    visited = set()
    stack = [start_node] # Initialize stack with the start node

    while stack:
        current_node = stack.pop() # Pop the last added node (LIFO)

        if current_node not in visited:
            visited.add(current_node)
            print(current_node, end=" ") # Process the node

            # Add unvisited neighbors to the stack.
            # Important: Add them in reverse order if you want to mimic
            # the recursive traversal order for graphs where neighbor order matters.
            # This is because stack.pop() will get the *last* element added.
            # If graph[current_node] = ['B', 'C'], and we want to visit 'B' first
            # (as recursive would often do for lexicographical order),
            # then 'B' must be popped last, meaning it's pushed first.
            # Or, more intuitively: push 'C' then 'B', so 'B' is on top.
            
            # Here, we iterate in reverse to ensure neighbors are pushed
            # such that the "first" neighbor (e.g., 'B' if ['B', 'C']) is processed first.
            for neighbor in reversed(graph.get(current_node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)

# Define our example graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D', 'E'],
    'D': ['B', 'C'],
    'E': ['C']
}

print("DFS Traversal (Iterative, starting from 'A'):")
dfs_iterative(graph, 'A')
print("\n")

# Another example graph
graph2 = {
    '0': ['1', '2'],
    '1': ['2'],
    '2': ['0', '3'],
    '3': ['3']
}

print("DFS Traversal (Iterative, starting from '2' in graph2):")
dfs_iterative(graph2, '2')
print("\n")

DFS Traversal (Iterative, starting from 'A'):
A B D C E 

DFS Traversal (Iterative, starting from '2' in graph2):
2 0 1 3 

Note on Neighbor Order: For iterative DFS, the order in which you add neighbors to the stack matters for the specific traversal path. If graph['A'] is ['B', 'C'] and you for neighbor in graph.get(current_node, []), ‘B’ is added first, then ‘C’. When you pop(), ‘C’ comes off first. To mimic the recursive behavior (where ‘B’ is processed first if it’s the first in the list), you need to push neighbors onto the stack in reverse order. My example uses reversed() to achieve this, making the iterative output match the recursive one for a given adjacency list order.

Applications of DFS

DFS is incredibly versatile and forms the basis for many critical graph algorithms.

1. Finding Connected Components

A connected component in an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. DFS is perfect for finding these.

We can iterate through all nodes in the graph. If a node hasn’t been visited yet, it means it belongs to a new, undiscovered connected component. We then start a DFS from that node, visiting all nodes in that component.

# graph_connected_components.py

def dfs_find_component(graph, start_node, visited):
    """Performs DFS to find all nodes in a component."""
    stack = [start_node]
    component_nodes = [] # To store nodes in the current component

    while stack:
        current_node = stack.pop()
        if current_node not in visited:
            visited.add(current_node)
            component_nodes.append(current_node)
            for neighbor in reversed(graph.get(current_node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)
    return sorted(component_nodes) # Return sorted for consistent output

def find_connected_components(graph):
    visited = set()
    components = []
    
    # Iterate through all nodes in the graph
    for node in graph:
        if node not in visited:
            # If a node hasn't been visited, it means we found a new component
            component = dfs_find_component(graph, node, visited)
            components.append(component)
    return components

# Example graph with multiple components
disconnected_graph = {
    'A': ['B'],
    'B': ['A'],
    'C': ['D', 'E'],
    'D': ['C'],
    'E': ['C'],
    'F': [],
    'G': ['H'],
    'H': ['G']
}

components = find_connected_components(disconnected_graph)
print("Connected Components:")
for i, comp in enumerate(components):
    print(f"Component {i+1}: {comp}")

print("\n--- Another disconnected graph ---")
graph_mix = {
    0: [1, 2],
    1: [0],
    2: [0],
    3: [4],
    4: [3],
    5: []
}

components_mix = find_connected_components(graph_mix)
print("Connected Components (Graph Mix):")
for i, comp in enumerate(components_mix):
    print(f"Component {i+1}: {comp}")

Connected Components:
Component 1: ['A', 'B']
Component 2: ['C', 'D', 'E']
Component 3: ['F']
Component 4: ['G', 'H']

--- Another disconnected graph ---
Connected Components (Graph Mix):
Component 1: [0, 1, 2]
Component 2: [3, 4]
Component 3: [5]

2. Cycle Detection

DFS can detect cycles in both directed and undirected graphs.

• Undirected Graphs: A cycle exists if DFS encounters an already visited node that is not the immediate parent of the current node in the DFS tree.
• Directed Graphs: A cycle exists if DFS encounters a node that is currently in the recursion stack (i.e., it’s an ancestor of the current node). This requires an additional state (visiting or recursion_stack set) to distinguish between visited nodes that are part of the current path and those that are not.

3. Topological Sorting

For Directed Acyclic Graphs (DAGs), DFS is the core algorithm for topological sorting, which produces a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v in the ordering. This is useful for task scheduling, build systems, etc.

4. Path Finding

While BFS finds the shortest path in an unweighted graph, DFS can be used to find any path between two nodes. With modifications, it can also find all paths or paths meeting certain criteria (e.g., in backtracking algorithms).

Time and Space Complexity

Let $V$ be the number of vertices (nodes) and $E$ be the number of edges in the graph.

• Time Complexity:

  • Adjacency List: O(V + E). Each vertex and each edge is visited at most a constant number of times. We visit each vertex once and iterate over all its edges once.
  • Adjacency Matrix: O(V^2). For each vertex, we might have to iterate through all V columns to find its neighbors.

• Space Complexity:

  • Adjacency List: O(V) for the visited set and the recursion stack (or explicit stack). In the worst case, for a skewed graph (like a linked list), the stack depth can be V.
  • Adjacency Matrix: O(V) for the visited set and stack.

DFS vs. BFS: When to Choose Which?

Both DFS and BFS are fundamental traversal algorithms, but their different exploration strategies make them suitable for different problems.

Conclusion

Depth First Search is a powerful and essential algorithm in your data structures and algorithms toolkit. Its ability to dive deep into a graph’s structure makes it ideal for problems requiring full path exploration or hierarchical processing. Whether you choose its elegant recursive form or its robust iterative counterpart, understanding DFS is key to tackling a wide range of graph-related computational challenges. Practice with different graph structures, and you’ll soon appreciate its utility and versatility.