Topological Sort (Kahn's Algorithm) Algorithm Tutorial

Topological Sort (Kahn's Algorithm)

Topological Sort arranges vertices of a directed acyclic graph (DAG) so every edge goes from earlier to later in the ordering. Kahn's Algorithm uses BFS, repeatedly removing vertices with no incoming edges.

A topological ordering only exists for DAGs. If the graph has a cycle, no valid ordering exists.

function kahnTopologicalSort(graph, n):
    inDegree = array of size n, initialized to 0
    for each edge (u, v):
        inDegree[v] = inDegree[v] + 1

    queue = min-priority queue
    for v from 0 to n - 1:
        if inDegree[v] == 0:
            queue.push(v)

    result = empty list
    while queue is not empty:
        u = queue.pop()
        result.append(u)
        for each neighbor v of u:
            inDegree[v] = inDegree[v] - 1
            if inDegree[v] == 0:
                queue.push(v)

    if length of result != n:
        return -1
    return result

Cycle detection: If your result has fewer than $n$ vertices, the graph has a cycle.

Lexicographically smallest: Use a min-priority queue to always pick the smallest available vertex.

Applications: You use topological sort for build systems (Make, Gradle), course prerequisites, task scheduling, and dependency resolution.

Time complexity: $O(V + E)$ for the algorithm, $O((V + E) \log V)$ with priority queue.

Space complexity: $O(V)$ for in-degree array and queue.