Graphs

Topological Sort

TimeO(V + E) SpaceO(V + E)

Think of getting dressed. You must put on underwear before pants, socks before shoes, and shirt before jacket. Topological sort finds a valid order that respects all these dependencies — any sequence where every prerequisite comes before the thing that depends on it.

When to use it: Task scheduling with dependencies, course prerequisite ordering, build system dependency resolution, or any problem on a directed acyclic graph (DAG) that requires a valid ordering.

Key insight: A node with no incoming edges (in-degree 0) has no unmet dependencies and can go next. Remove it, decrement its neighbors’ in-degrees, and repeat. This is Kahn’s algorithm.

Common trap: Forgetting to check for cycles. If the output has fewer nodes than the graph, a cycle exists and no valid topological order is possible.

# Kahn's algorithm (BFS-based)
function topologicalSort(graph, numNodes):
    inDegree = {node: 0 for node in graph}

    for node in graph:
        for neighbor in graph[node]:
            inDegree[neighbor] = inDegree[neighbor] + 1

    queue = [node for node in graph if inDegree[node] == 0]
    result = []

    while queue is not empty:
        node = queue.dequeue()
        result.append(node)

        for neighbor in graph[node]:
            inDegree[neighbor] = inDegree[neighbor] - 1
            if inDegree[neighbor] == 0:
                queue.enqueue(neighbor)

    if length(result) != numNodes:
        return error("Cycle detected — no valid ordering")

    return result

# DFS-based topological sort
function topologicalSortDFS(graph):
    visited = set()
    stack = []

    function dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)              # add AFTER processing all children

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

    return reverse(stack)               # reverse of finishing order

from collections import deque, defaultdict


def topological_sort_kahn(num_nodes: int, edges: list[tuple[int, int]]) -> list[int]:
    """
    Kahn's algorithm (BFS). edges: [(prerequisite, dependent), ...]
    Returns topological order or empty list if cycle detected.
    """
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque(i for i in range(num_nodes) if in_degree[i] == 0)
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != num_nodes:
        return []  # cycle detected

    return result


def topological_sort_dfs(num_nodes: int, edges: list[tuple[int, int]]) -> list[int]:
    """DFS-based topological sort."""
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    visited = set()
    stack = []

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

    for i in range(num_nodes):
        if i not in visited:
            dfs(i)

    return stack[::-1]


def can_finish_courses(num_courses: int, prerequisites: list[list[int]]) -> bool:
    """Can all courses be completed? (Cycle detection via topo sort.)"""
    edges = [(pre, course) for course, pre in prerequisites]
    return len(topological_sort_kahn(num_courses, edges)) == num_courses

Problem: There are n courses labeled 0 to n-1. Some courses have prerequisites. Return an ordering of courses you should take to finish all courses.

How would you approach this?

Answer: This is topological sort (Kahn's algorithm). Build a directed graph from prerequisite to course. Start with courses that have no prerequisites (in-degree 0), process them, reduce neighbors' in-degrees, and repeat. The processing order is a valid course schedule.

Problem: Given a list of tasks with dependencies, determine if all tasks can be completed and, if so, return a valid execution order.

How would you approach this?

Answer: This is topological sort. Model tasks as nodes and dependencies as directed edges. If the topological sort includes all nodes, the tasks can be completed in that order. If not, there's a circular dependency.

Time: O(V + E) because we compute in-degrees in O(E), process each vertex once (O(V)), and examine each edge once when decrementing in-degrees (O(E)).

Space: O(V + E) for the adjacency list (O(V + E)), the in-degree array (O(V)), and the queue (O(V) in the worst case).