Topological Sort

How Topological Sort Works — Plain English and Algorithm

Topological sort answers: 'Given a set of tasks with dependencies, what order should I do them?' If task B depends on task A, then A must appear before B in the output. The algorithm only works on a Directed Acyclic Graph (DAG) — a cycle would mean A depends on B which depends on A, making a valid ordering impossible.

Kahn's algorithm (BFS-based) works by repeatedly removing nodes that have no remaining prerequisites: 1. Compute the in-degree (number of incoming edges) for every node. 2. Enqueue all nodes with in-degree 0 — they have no prerequisites. 3. While the queue is non-empty, dequeue a node and add it to the result. 4. For each neighbour of that node, decrement its in-degree by 1 (the prerequisite is now satisfied). 5. If a neighbour's in-degree reaches 0, enqueue it. 6. If the result length equals the total number of nodes, the sort succeeded. Otherwise, a cycle exists.

Worked example: nodes A, B, C, D with edges A->C, B->C, C->D. In-degrees: A=0, B=0, C=2, D=1. Queue starts with [A, B]. Step 1: dequeue A, result=[A]. Decrement C's in-degree to 1. C not ready yet. Step 2: dequeue B, result=[A,B]. Decrement C's in-degree to 0. Enqueue C. Step 3: dequeue C, result=[A,B,C]. Decrement D's in-degree to 0. Enqueue D. Step 4: dequeue D, result=[A,B,C,D]. Done. Result length 4 == 4 nodes, no cycle.

Both A and B have no prerequisites, so either can come first — multiple valid orderings often exist.

Kahn's Algorithm — BFS Approach

Kahn's algorithm uses in-degrees to process nodes in dependency order. It naturally detects cycles: if the result list is shorter than the total node count, at least one cycle prevented some nodes from ever reaching in-degree 0. This makes it the preferred approach when cycle detection is also required.

# Package: io.thecodeforge.python.dsa

from collections import deque, defaultdict

def topological_sort_kahn(graph, nodes):
    """
    Kahn's algorithm: process nodes with in-degree 0 first.
    Returns sorted order or empty list if cycle detected.
    """
    in_degree = defaultdict(int)
    for node in nodes:
        in_degree[node] = in_degree.get(node, 0)
    for node in graph:
        for neighbour in graph[node]:
            in_degree[neighbour] += 1

    # Start with all nodes that have no dependencies
    queue = deque([n for n in nodes if in_degree[n] == 0])
    result = []

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

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

    # If result doesn't contain all nodes, there's a cycle
    return result if len(result) == len(nodes) else []

# Build system example: A → C, B → C, C → D
graph = {'A': ['C'], 'B': ['C'], 'C': ['D'], 'D': []}
nodes = ['A', 'B', 'C', 'D']
print(topological_sort_kahn(graph, nodes))  # ['A', 'B', 'C', 'D'] or ['B', 'A', 'C', 'D']

# Course prerequisite example
courses = {
    'Algorithms':  ['Advanced Algorithms'],
    'Data Structures': ['Algorithms'],
    'Math': ['Data Structures', 'Algorithms'],
    'Advanced Algorithms': []
}
course_nodes = list(courses.keys())
print(topological_sort_kahn(courses, course_nodes))

DFS-Based Topological Sort

DFS-based topological sort uses post-order processing: when DFS finishes exploring all neighbors of a node (i.e., when it backtracks from the node), the node is pushed onto a stack. After all nodes have been fully explored, the stack is reversed to give the topological order. The key insight is that a node appears after all the nodes it depends on because DFS fully explores dependencies before marking a node as finished. Implementation: for each unvisited node, run DFS; when the DFS for a node completes, prepend it to the result list (or push to a stack, then reverse). Cycle detection is built-in: if DFS encounters a node in the current recursion path (gray node), a cycle exists and topological sort is impossible.

def topological_sort_dfs(graph, nodes):
    visited  = set()
    in_stack = set()  # for cycle detection
    result   = []
    has_cycle = [False]

    def dfs(node):
        if has_cycle[0]: return
        in_stack.add(node)
        visited.add(node)

        for neighbour in graph.get(node, []):
            if neighbour in in_stack:  # back edge = cycle
                has_cycle[0] = True
                return
            if neighbour not in visited:
                dfs(neighbour)

        in_stack.discard(node)
        result.append(node)  # add AFTER all descendants processed

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

    if has_cycle[0]:
        return []  # cycle detected
    return result[::-1]  # reverse for topological order

graph = {'A': ['C'], 'B': ['C'], 'C': ['D'], 'D': []}
print(topological_sort_dfs(graph, ['A', 'B', 'C', 'D']))
# ['A', 'B', 'C', 'D'] — or ['B', 'A', 'C', 'D']

# Cycle detection
cyclic = {'A': ['B'], 'B': ['C'], 'C': ['A']}
print(topological_sort_dfs(cyclic, ['A', 'B', 'C']))  # []

Frequently Asked Questions