Topological Sort

Topological Sort

A topological ordering of a directed acyclic graph (DAG) lists nodes such that every edge u → v has u appearing before v.

0 → 1 → 3
↓       ↑
2 ———→
Topological order: [0, 1, 2, 3]

Kahn's Algorithm (BFS-based)

1. Compute in-degree (number of incoming edges) for each node
2. Start with all nodes of in-degree 0 (no dependencies)
3. Repeatedly remove a zero-in-degree node, add to result, and decrease in-degrees of its neighbors

import heapq
from collections import defaultdict

def topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    # Min-heap for deterministic output
    heap = [i for i in range(n) if in_degree[i] == 0]
    heapq.heapify(heap)
    result = []

    while heap:
        node = heapq.heappop(heap)
        result.append(node)
        for nb in graph[node]:
            in_degree[nb] -= 1
            if in_degree[nb] == 0:
                heapq.heappush(heap, nb)

    return result if len(result) == n else []  # [] if cycle

Applications

• Build systems (compile A before B)
• Course prerequisites
• Task scheduling
• Package dependency resolution

Your Task

Implement topological_sort(n, edges) using Kahn's algorithm with a min-heap for deterministic output. Return an empty list if the graph has a cycle.