Offensive Security Researcher & Quantum Cryptography Analyst

Topological Sort Algorithm: Working, Explanation, and Dependency Ordering

Abdul Wahab Junaid
topological sort algorithm and working of this algorithm

topological sort algorithm and working of this algorithm

Whenever I’ve had to figure out a valid order to complete a set of tasks with dependencies — like which courses to take first, or in what sequence to compile files that depend on each other — I’ve relied on topological sorting. It’s the algorithm that takes a directed acyclic graph and arranges its nodes into a linear order such that every edge points from an earlier node to a later one. What I like about it is that it doesn’t just solve an abstract graph problem; it directly models scheduling and dependency-resolution problems that show up constantly in real software systems, from build tools to package managers.

History and Background

I trace the idea of topological ordering to foundational work in graph theory from the early-to-mid 20th century, with formal treatment appearing in the work of mathematicians studying partially ordered sets (posets) and directed acyclic graphs. The specific linear-time algorithm using depth-first search is generally attributed to Robert Tarjan, who described it in the early 1970s as part of his broader body of work on graph algorithms, including strongly connected components. The alternative approach using in-degree counting is commonly known as Kahn’s algorithm, published by Arthur B. Kahn in 1962 in a paper about topological sorting of large networks, and it remains the more intuitive of the two approaches for many people, myself included, when first learning the concept.

Problem Statement

I have a directed graph representing tasks and their dependencies, where an edge from node u to node v means task u must be completed before task v. I need to produce a linear ordering of all nodes such that for every directed edge u -> v, u appears before v in the ordering. This is only possible if the graph is a Directed Acyclic Graph (DAG) — if there’s a cycle, no valid ordering can exist, since it would require some task to happen before itself. Topological sort must therefore both produce a valid ordering when possible and detect the impossibility (a cycle) when it isn’t.

Core Concepts

How It Works

I describe both standard approaches, since each has its own intuitive appeal:

Kahn’s algorithm (BFS-based):

  1. I compute the in-degree of every node.
  2. I initialize a queue with all nodes that currently have in-degree zero.
  3. I repeatedly dequeue a node, append it to the result list, and decrement the in-degree of each of its neighbors.
  4. If any neighbor’s in-degree drops to zero, I enqueue it.
  5. If I process all nodes, the result list is a valid topological order; if not all nodes are processed, the graph has a cycle.

DFS-based algorithm:

  1. I perform a standard depth-first search over all nodes.
  2. When the DFS finishes fully exploring a node (i.e., all its descendants have been visited), I push that node onto a stack (or prepend it to a result list).
  3. After the DFS completes for the entire graph, I reverse the stack (or read the result list in reverse) to get the topological order.
  4. I detect cycles by tracking nodes currently in the recursion stack (the “gray” state) — if I revisit a gray node, a cycle exists.

Working Principle

Both approaches rely on the same underlying invariant: a node can only be placed in the ordering once all of its prerequisites have already been placed. Kahn’s algorithm enforces this directly and greedily — a node is only ever added to the queue (and thus eventually to the output) once every one of its incoming edges has been “consumed” by processing its predecessors. The DFS-based approach enforces the same invariant indirectly, through the structure of post-order traversal: a node is only finished (and thus added to the result) after all paths leading out of it, including through its dependents, have been fully explored, which guarantees that anything reachable from it — meaning anything depending on it in the reversed sense — is accounted for before it takes its final position when the list is reversed.

Mathematical Foundation

A topological order exists for a directed graph G = (V, E) if and only if G is acyclic. This is formalized by the following:

$$ \text{Topological order exists} \iff G \text{ contains no directed cycle} $$

For Kahn’s algorithm, if I let S_0 be the set of nodes with in-degree 0, and repeatedly define S_{i+1} as the set of nodes whose in-degree becomes 0 after removing S_i and its outgoing edges, then a topological order exists if and only if:

$$ \bigcup_{i \geq 0} S_i = V $$

meaning every node is eventually reached by this process. If the union falls short of V, the remaining nodes form one or more cycles.

The total complexity of processing every node and every edge exactly once (in either approach) is:

$$ T(|V|, |E|) = O(|V| + |E|) $$

Diagrams

flowchart TD
    A[Compute in-degree for every node] --> B[Enqueue all nodes with in-degree 0]
    B --> C{Queue empty?}
    C -- Yes --> H{All nodes processed?}
    H -- Yes --> I[Valid topological order found]
    H -- No --> J[Cycle detected]
    C -- No --> D[Dequeue node u, append to result]
    D --> E[For each neighbor v of u: decrement in-degree of v]
    E --> F{in-degree of v == 0?}
    F -- Yes --> G[Enqueue v]
    G --> C
    F -- No --> C

Pseudocode

Kahn’s Algorithm:

function topologicalSortKahn(graph):
    inDegree = map of node -> 0 for all nodes
    for each node u in graph:
        for each neighbor v of u:
            inDegree[v] += 1

    queue = all nodes with inDegree == 0
    result = []

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

    if length(result) != number of nodes in graph:
        return "Cycle detected, no valid topological order"
    return result

DFS-based Algorithm:

function topologicalSortDFS(graph):
    visited = set()
    inStack = set()
    result = []
    hasCycle = false

    function dfs(u):
        visited.add(u)
        inStack.add(u)
        for each neighbor v of u:
            if v in inStack:
                hasCycle = true
                return
            if v not in visited:
                dfs(v)
        inStack.remove(u)
        result.prepend(u)   // or push to stack, then reverse later

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

    if hasCycle:
        return "Cycle detected, no valid topological order"
    return result

Step-by-Step Example

Consider a small dependency graph for getting dressed:

Using Kahn’s algorithm:

In-degrees: Underwear = 0, Shirt = 0, Socks = 0, Pants = 1, Jacket = 2, Shoes = 2.

I start with Underwear, Shirt, Socks in the queue (order among equals can vary). I process Underwear, decrementing Pants to 0, so I enqueue Pants. I process Shirt, decrementing Jacket to 1. I process Socks, decrementing Shoes to 1. I process Pants, decrementing Jacket to 0 (enqueue Jacket) and Shoes to 0 (enqueue Shoes). Finally I process Jacket and Shoes.

One valid result: Underwear, Shirt, Socks, Pants, Jacket, Shoes — every dependency is respected.

Time Complexity

Space Complexity

Both approaches require O(|V|) space for auxiliary structures: the in-degree array and queue in Kahn’s algorithm, or the visited/in-stack sets and recursion stack in the DFS-based approach. The adjacency list representation of the graph itself takes O(|V| + |E|) space, and the output ordering takes O(|V|) space.

Correctness Analysis

For Kahn’s algorithm, I argue correctness by induction on the processing order: a node is only ever enqueued once its in-degree reaches zero, which by construction means every predecessor of that node (according to the current graph state) has already been dequeued and placed into the result. This guarantees that at the moment any node is added to the result, all of its prerequisites already appear earlier, satisfying the topological order property. If the graph has a cycle, no node within that cycle can ever reach in-degree zero (since each depends circularly on another within the cycle), so the algorithm correctly fails to include all nodes, signaling a cycle.

For the DFS-based approach, I rely on the classic property of DFS finish times in a DAG: for any edge u -> v, the finish time of u is always later than the finish time of v, because v must be fully explored (finished) before the recursive call on u can return. Reversing the finish-time order therefore guarantees u appears before v, satisfying the topological order property for every edge.

Advantages

Disadvantages

Applications

Implementation in C

#include stdio.h>
#include stdlib.h>

#define MAX_NODES 100

int adj[MAX_NODES][MAX_NODES]; /* adjacency matrix */
int inDegree[MAX_NODES];
int numNodes;

void topologicalSortKahn() {
    int queue[MAX_NODES];
    int front = 0, back = 0;
    int result[MAX_NODES];
    int resultCount = 0;

    int localInDegree[MAX_NODES];
    for (int i = 0; i  numNodes; i++) {
        localInDegree[i] = inDegree[i];
        if (localInDegree[i] == 0) {
            queue[back++] = i; /* enqueue nodes with no prerequisites */
        }
    }

    while (front  back) {
        int u = queue[front++];
        result[resultCount++] = u;

        for (int v = 0; v  numNodes; v++) {
            if (adj[u][v]) {
                localInDegree[v]--;
                if (localInDegree[v] == 0) {
                    queue[back++] = v;
                }
            }
        }
    }

    if (resultCount != numNodes) {
        printf("Cycle detected! No valid topological order exists.\n");
        return;
    }

    printf("Topological order: ");
    for (int i = 0; i  resultCount; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
}

int main() {
    numNodes = 6; /* 0=Underwear,1=Pants,2=Shoes,3=Jacket,4=Shirt,5=Socks */

    for (int i = 0; i  MAX_NODES; i++) {
        inDegree[i] = 0;
        for (int j = 0; j  MAX_NODES; j++) adj[i][j] = 0;
    }

    /* Add edges: u -> v means u must come before v */
    int edges[][2] = {{0,1}, {1,2}, {1,3}, {4,3}, {5,2}};
    int numEdges = 5;

    for (int i = 0; i  numEdges; i++) {
        int u = edges[i][0], v = edges[i][1];
        adj[u][v] = 1;
        inDegree[v]++;
    }

    topologicalSortKahn();
    return 0;
}

Sample Input and Output

Input: Nodes 0..5 representing Underwear, Pants, Shoes, Jacket, Shirt, Socks, with edges Underwear->Pants, Pants->Shoes, Pants->Jacket, Shirt->Jacket, Socks->Shoes.

Output:

Topological order: 0 4 5 1 3 2

(Underwear, Shirt, Socks, Pants, Jacket, Shoes — order among independent nodes may vary by implementation)

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version