Graphs

Graph DFS

TimeO(V + E) SpaceO(V)

Think of exploring a cave system. You pick a tunnel and follow it as far as it goes. When you hit a dead end, you backtrack to the last fork and try a different tunnel. You keep doing this until you’ve mapped every reachable chamber.

When to use it: Detecting cycles, finding connected components, topological sorting, checking bipartiteness, finding strongly connected components, or any problem requiring full graph exploration.

Key insight: DFS naturally tracks a path from the start to the current node. This makes it ideal for path-based problems, cycle detection (back edges), and problems that need to process nodes after all their descendants.

Common trap: Not distinguishing between “currently being explored” and “fully explored” nodes. For cycle detection in directed graphs, you need three states: unvisited, in-progress, and complete.

# Basic graph DFS
function dfs(graph, node, visited):
    visited.add(node)
    process(node)

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

# Cycle detection in a directed graph
function hasCycle(graph):
    WHITE = 0   # unvisited
    GRAY = 1    # in current path (being explored)
    BLACK = 2   # fully explored

    color = {node: WHITE for node in graph}

    function dfsVisit(node):
        color[node] = GRAY              # start exploring

        for neighbor in graph[node]:
            if color[neighbor] == GRAY:
                return true             # back edge = cycle
            if color[neighbor] == WHITE:
                if dfsVisit(neighbor):
                    return true

        color[node] = BLACK             # done exploring
        return false

    for node in graph:
        if color[node] == WHITE:
            if dfsVisit(node):
                return true

    return false

def dfs_recursive(graph: dict[int, list[int]], start: int) -> list[int]:
    """Return all nodes reachable from start."""
    visited = set()
    result = []

    def dfs(node: int) -> None:
        visited.add(node)
        result.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)
    return result


def dfs_iterative(graph: dict[int, list[int]], start: int) -> list[int]:
    """Iterative DFS using explicit stack."""
    visited = set()
    stack = [start]
    result = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        result.append(node)

        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                stack.append(neighbor)

    return result


def has_cycle_directed(graph: dict[int, list[int]]) -> bool:
    """Detect cycle in a directed graph using 3-color DFS."""
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}

    def dfs(node: int) -> bool:
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color.get(neighbor, WHITE) == GRAY:
                return True
            if color.get(neighbor, WHITE) == WHITE and dfs(neighbor):
                return True
        color[node] = BLACK
        return False

    return any(dfs(node) for node in graph if color[node] == WHITE)


def connected_components(graph: dict[int, list[int]]) -> list[list[int]]:
    """Find all connected components in an undirected graph."""
    visited = set()
    components = []

    for node in graph:
        if node not in visited:
            component = []
            stack = [node]
            while stack:
                n = stack.pop()
                if n in visited:
                    continue
                visited.add(n)
                component.append(n)
                for neighbor in graph.get(n, []):
                    if neighbor not in visited:
                        stack.append(neighbor)
            components.append(component)

    return components

Problem: Given a directed graph representing course prerequisites, determine if it is possible to finish all courses (i.e., no circular dependencies).

How would you approach this?

Answer: This is cycle detection in a directed graph using DFS. Use the three-color scheme: if DFS encounters a GRAY (in-progress) node, there's a cycle and courses cannot all be completed. If no back edges are found, the schedule is valid.

Problem: Given an undirected graph, count how many connected components it has.

How would you approach this?

Answer: This is graph DFS for connected components. Start DFS from any unvisited node, marking all reachable nodes as visited (one component). Repeat from the next unvisited node. The number of DFS starts equals the number of components.

Time: O(V + E) where V is the number of vertices and E is the number of edges. Each vertex is visited once, and each edge is examined once (directed) or twice (undirected).

Space: O(V) for the visited set and the recursion stack (or explicit stack). In the worst case, the recursion depth equals V (a graph shaped like a long chain).