How to Implement Depth First Search (DFS) Algorithm for Graphs in Python

Depth First Search explores a graph by traversing as deep as possible along each branch before backtracking. It's fundamental for pathfinding, cycle detection, topological sorting, and connected component analysis.

Graph Representation

DFS typically operates on an adjacency list:

# Adjacency list representation
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

Recursive Implementation

The recursive approach uses the call stack implicitly:

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)
    
    return visited

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

# Usage
visited = dfs_recursive(graph, 'A')

Output:

A B D E F C

With return path tracking:

def dfs_with_path(graph, start, target, path=None, visited=None):
    """Find a path from start to target using DFS."""
    if path is None:
        path = []
    if visited is None:
        visited = set()
    
    path = path + [start]
    visited.add(start)
    
    if start == target:
        return path
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            result = dfs_with_path(graph, neighbor, target, path, visited)
            if result:
                return result
    
    return None

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

path = dfs_with_path(graph, 'A', 'F')
print(path)

Output:

['A', 'B', 'E', 'F']

Iterative Implementation

Using an explicit stack prevents recursion limit issues:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    result = []
    
    while stack:
        node = stack.pop()
        
        if node not in visited:
            visited.add(node)
            result.append(node)
            
            # Add neighbors in reverse order for left-to-right traversal
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result

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

order = dfs_iterative(graph, 'A')
print(order)

Output:

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

tip

Reversing neighbors when pushing to the stack ensures the traversal order matches the recursive version, processing neighbors left-to-right.

Finding All Paths

Discover all possible paths between two nodes:

def find_all_paths(graph, start, end, path=None):
    """Find all paths from start to end."""
    if path is None:
        path = []
    
    path = path + [start]
    
    if start == end:
        return [path]
    
    if start not in graph:
        return []
    
    paths = []
    for neighbor in graph[start]:
        if neighbor not in path:  # Avoid cycles
            new_paths = find_all_paths(graph, neighbor, end, path)
            paths.extend(new_paths)
    
    return paths

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

all_paths = find_all_paths(graph, 'A', 'F')
for p in all_paths:
    print(' -> '.join(p))

Output:

A -> B -> E -> F
A -> C -> F

Cycle Detection

Detect cycles in a directed graph:

def has_cycle(graph):
    """Detect if directed graph has a cycle using DFS."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    
    def dfs(node):
        color[node] = GRAY  # Currently being processed
        
        for neighbor in graph[node]:
            if color[neighbor] == GRAY:  # Back edge found
                return True
            if color[neighbor] == WHITE:
                if dfs(neighbor):
                    return True
        
        color[node] = BLACK  # Fully processed
        return False
    
    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    
    return False

# Graph with cycle
cyclic_graph = {
    'A': ['B'],
    'B': ['C'],
    'C': ['A']  # Creates cycle
}

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

print(has_cycle(cyclic_graph))  # True
print(has_cycle(graph))         # False

Topological Sort

Order nodes so all edges point forward:

def topological_sort(graph):
    """Return topologically sorted order of nodes."""
    visited = set()
    result = []
    
    def dfs(node):
        visited.add(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        
        result.append(node)
    
    for node in graph:
        if node not in visited:
            dfs(node)
    
    return result[::-1]  # Reverse for correct order

# Task dependencies
tasks = {
    'build': ['test'],
    'test': ['deploy'],
    'deploy': [],
    'lint': ['build'],
    'install': ['lint', 'build']
}

order = topological_sort(tasks)
print(order)  # ['install', 'lint', 'build', 'test', 'deploy']

Connected Components

Find all connected components in an undirected graph:

def find_connected_components(graph):
    """Find all connected components."""
    visited = set()
    components = []
    
    def dfs(node, component):
        visited.add(node)
        component.append(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, component)
    
    for node in graph:
        if node not in visited:
            component = []
            dfs(node, component)
            components.append(component)
    
    return components

# Disconnected graph
disconnected = {
    'A': ['B'],
    'B': ['A'],
    'C': ['D'],
    'D': ['C'],
    'E': []
}

components = find_connected_components(disconnected)
print(components)  # [['A', 'B'], ['C', 'D'], ['E']]

DFS on Grid/Matrix

Navigate a 2D grid:

def dfs_grid(grid, start_row, start_col):
    """DFS on a 2D grid."""
    rows, cols = len(grid), len(grid[0])
    visited = set()
    
    def dfs(r, c):
        if (r < 0 or r >= rows or 
            c < 0 or c >= cols or
            (r, c) in visited or
            grid[r][c] == 0):  # 0 = blocked
            return
        
        visited.add((r, c))
        print(f"Visiting: ({r}, {c})")
        
        # Explore 4 directions
        dfs(r + 1, c)  # Down
        dfs(r - 1, c)  # Up
        dfs(r, c + 1)  # Right
        dfs(r, c - 1)  # Left
    
    dfs(start_row, start_col)
    return visited

grid = [
    [1, 1, 0, 1],
    [1, 1, 1, 0],
    [0, 1, 1, 1]
]

visited = dfs_grid(grid, 0, 0)

Output:

Visiting: (0, 0)
Visiting: (1, 0)
Visiting: (1, 1)
Visiting: (2, 1)
Visiting: (2, 2)
Visiting: (1, 2)
Visiting: (2, 3)
Visiting: (0, 1)

warning

For very deep graphs or large grids, the recursive approach may hit Python's recursion limit (default ~1000). Use the iterative version or increase the limit with sys.setrecursionlimit().

Pre-order and Post-order Traversal

Track entry and exit times:

def dfs_with_timestamps(graph, start):
    """DFS with pre-order and post-order timestamps."""
    visited = set()
    time = [0]
    pre_order = {}
    post_order = {}
    
    def dfs(node):
        visited.add(node)
        time[0] += 1
        pre_order[node] = time[0]
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        
        time[0] += 1
        post_order[node] = time[0]
    
    dfs(start)
    return pre_order, post_order

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

pre, post = dfs_with_timestamps(graph, 'A')
print("Pre-order:", pre)
print("Post-order:", post)

Output:

Pre-order: {'A': 1, 'B': 2, 'D': 3, 'E': 5, 'F': 6, 'C': 10}
Post-order: {'D': 4, 'F': 7, 'E': 8, 'B': 9, 'C': 11, 'A': 12}

Implementation Comparison

Feature	Recursive	Iterative
Memory	Call stack	Explicit stack
Depth limit	~1000 (default)	Limited by RAM
Code complexity	Simpler	More verbose
Debugging	Stack traces	Manual tracking
Performance	Slightly slower	Slightly faster

Use the recursive implementation for readable code and moderate graph sizes. Switch to iterative for production systems handling deep or potentially cyclic graphs where stack overflow is a concern.