Depth-First Search

Depth-First Search (DFS) is a traversal algorithm that explores as far as possible down one branch before backtracking. It uses a Stack or recursion.

Concept

Graph:     A --- B
           |     |
           C --- D

DFS from A: A -> B -> D -> C (depth first)

Recursive Implementation

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

    visited.add(vertex)
    order = [vertex]

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

    return order

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

print(dfs_recursive(graph, 'A'))  # ['A', 'B', 'D', 'C']

Iterative Implementation (Stack)

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

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            order.append(vertex)
            # Reverse so the left neighbor is processed first
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

    return order

print(dfs_iterative(graph, 'A'))  # ['A', 'B', 'D', 'C']

DFS for Binary Trees

Preorder (Root, Left, Right)

def preorder(node):
    if not node:
        return []
    return [node.val] + preorder(node.left) + preorder(node.right)

Inorder (Left, Root, Right)

def inorder(node):
    if not node:
        return []
    return inorder(node.left) + [node.val] + inorder(node.right)

Postorder (Left, Right, Root)

def postorder(node):
    if not node:
        return []
    return postorder(node.left) + postorder(node.right) + [node.val]

Cycle Detection

def has_cycle(graph):
    visited = set()
    rec_stack = set()

    def dfs(vertex):
        visited.add(vertex)
        rec_stack.add(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True

        rec_stack.remove(vertex)
        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex):
                return True
    return False

Topological Sort

For a Directed Acyclic Graph (DAG):

def topological_sort(graph):
    visited = set()
    stack = []

    def dfs(vertex):
        visited.add(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(vertex)

    for vertex in graph:
        if vertex not in visited:
            dfs(vertex)

    return stack[::-1]

# Example dependency graph
dep_graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

print(topological_sort(dep_graph))  # ['A', 'C', 'B', 'D'] or similar

Time Complexity

DFS vs BFS

DFS is powerful for recursive traversal. Now let's study sorting algorithms.