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

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

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': []
}

visited = dfs_recursive(graph, 'A')

A B D E F C

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)

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

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

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

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

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

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

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

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

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

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

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 = {
    'A': ['B'],
    'B': ['A'],
    'C': ['D'],
    'D': ['C'],
    'E': []
}

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

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})")
        
        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)

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

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)

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}