Offensive Security Researcher & Quantum Cryptography Analyst

Topological Sort Algorithm: Detailed Explanation and Implementation in C

Abdul Wahab Junaid
Topological Sort: Detailed Explanation and Implementation in C

Whenever I’m dealing with tasks that depend on each other — course prerequisites, build systems, spreadsheet formula evaluation — I end up needing a topological sort. It’s the algorithm that takes a directed acyclic graph and lines up its vertices in an order that respects every dependency: if there’s an edge from u to v, u always comes before v in the final ordering. It’s one of those algorithms that feels almost too simple once it clicks, but it quietly powers a huge amount of real infrastructure.

History and Background

Topological sorting has its roots in order theory and combinatorics, formalized well before computers existed, as mathematicians studied partial orders and their linear extensions. In computer science, it was popularized through the development of scheduling theory and compiler design in the 1960s and 70s, where dependency resolution became a practical necessity. Arthur Kahn’s 1962 paper “Topological sorting of large networks” introduced what’s now called Kahn’s Algorithm, one of the two standard approaches still taught today, the other being the DFS-based method that emerges naturally from depth-first traversal’s finish-time ordering, popularized through Tarjan’s work on DFS applications.

Problem Statement

Given a Directed Acyclic Graph (DAG) G = (V, E), find a linear ordering of all vertices such that for every directed edge (u, v), vertex u appears before vertex v in the ordering. If the graph contains a cycle, no valid topological order exists.

Core Concepts

How It Works

There are two standard methods:

Kahn’s Algorithm (BFS-based):

  1. Compute in-degree for every vertex.
  2. Add all vertices with in-degree 0 to a queue.
  3. Repeatedly remove a vertex from the queue, append it to the result, and decrement the in-degree of its neighbors.
  4. If a neighbor’s in-degree drops to 0, add it to the queue.
  5. If the result contains all vertices at the end, it’s a valid topological order; if not, the graph has a cycle.

DFS-based Algorithm:

  1. Run DFS on the graph.
  2. Every time a vertex finishes (all its neighbors have been fully explored), push it onto a stack.
  3. Once DFS completes, popping the stack gives the topological order.

Working Principle

Kahn’s Algorithm works on the intuitive idea that any vertex with no unmet dependencies (in-degree 0) is safe to place next in the order. Removing it and decrementing its neighbors’ in-degrees simulates “satisfying” those dependencies, which may unlock new vertices to become in-degree 0 candidates. This process mirrors exactly how real dependency resolution works, like a package manager installing packages in the right order.

The DFS-based method relies on a subtler but equally powerful idea: in a DAG, a vertex finishes (in DFS terms) only after all vertices reachable from it have finished. That means the vertex that finishes last is guaranteed to have no dependencies pointing to it from unfinished vertices, so reversing the finish-time order yields a valid topological order.

Mathematical Foundation

The key theorem is: a directed graph G has a topological ordering if and only if G is acyclic.

Proof sketch (necessity): if G has a cycle v₁ → v₂ → … → vₖ → v₁, then any proposed ordering would require v₁ before v₂ before … before vₖ before v₁, which is a contradiction since a vertex cannot come before itself.

Proof sketch (sufficiency, via DFS): in a DAG, define f(v) as the DFS finish time of v. For every edge (u, v), it must be that f(u) > f(v), because at the moment u finishes, v must already be finished (v cannot still be “in progress,” since that would create a back edge and imply a cycle). Sorting vertices by decreasing finish time therefore always respects every edge direction.

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

for both Kahn’s and the DFS-based approach, since both are built directly on top of either BFS-like queue processing or a single DFS traversal.

Diagrams

flowchart TD
    A[Compute in-degree of every vertex] --> B[Enqueue all vertices with in-degree 0]
    B --> C{Queue empty?}
    C -- No --> D[Dequeue vertex u, add to result]
    D --> E[Decrement in-degree of each neighbor of u]
    E --> F{Neighbor in-degree becomes 0?}
    F -- Yes --> G[Enqueue that neighbor]
    F -- No --> C
    G --> C
    C -- Yes --> H{Result contains all vertices?}
    H -- Yes --> I[Valid topological order found]
    H -- No --> J[Cycle detected, no valid order]

Pseudocode

TOPOLOGICAL-SORT-KAHN(G):
    for each vertex v in G.V:
        inDegree[v] = 0
    for each edge (u, v) in G.E:
        inDegree[v] = inDegree[v] + 1

    Q = empty queue
    for each vertex v in G.V:
        if inDegree[v] == 0:
            enqueue(Q, v)

    result = empty list
    while Q is not empty:
        u = dequeue(Q)
        append(result, u)
        for each v in G.adj[u]:
            inDegree[v] = inDegree[v] - 1
            if inDegree[v] == 0:
                enqueue(Q, v)

    if length(result) != |G.V|:
        error "graph has a cycle"
    return result

Step-by-Step Example

Take a course-prerequisite DAG:

1 -> 2
1 -> 3
2 -> 4
3 -> 4
4 -> 5

In-degrees: 1→0, 2→1, 3→1, 4→2, 5→1.

  1. Queue starts with vertex 1 (only in-degree 0). Result: [1]
  2. Process 1, decrement 2 and 3’s in-degrees to 0 each. Queue: [2, 3]
  3. Process 2, decrement 4’s in-degree to 1. Result: [1, 2]
  4. Process 3, decrement 4’s in-degree to 0. Queue: [4]. Result: [1, 2, 3]
  5. Process 4, decrement 5’s in-degree to 0. Queue: [5]. Result: [1, 2, 3, 4]
  6. Process 5. Result: [1, 2, 3, 4, 5]

Final topological order: 1, 2, 3, 4, 5 (note: 2 and 3 could have swapped order too — topological sort isn’t always unique).

Time Complexity

Space Complexity

Correctness Analysis

For Kahn’s algorithm, correctness follows from the invariant that a vertex is only added to the result once every vertex that must precede it has already been added (since its in-degree only reaches 0 after all its predecessors are processed). If the graph is acyclic, every vertex will eventually reach in-degree 0, and the algorithm terminates with a full ordering. If the graph has a cycle, the vertices within that cycle can never reach in-degree 0 (each depends on another within the same cycle), so the algorithm terminates with fewer than |V| vertices in the result — this is also how it doubles as a cycle detector.

For the DFS-based approach, correctness follows directly from the finish-time argument in the Mathematical Foundation section: because f(u) > f(v) for every edge (u,v) in a DAG, reverse-finish-time order always respects all edges.

Advantages

Disadvantages

Applications

Implementation in C

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

#define MAX_V 100

typedef struct {
    int adj[MAX_V][MAX_V];
    int V;
} Graph;

void initGraph(Graph *g, int v) {
    g->V = v;
    for (int i = 0; i < v; i++)
        for (int j = 0; j < v; j++)
            g->adj[i][j] = 0;
}

void addEdge(Graph *g, int u, int v) {
    g->adj[u][v] = 1;
}

void topologicalSortKahn(Graph *g) {
    int inDegree[MAX_V] = {0};
    int queue[MAX_V], front = 0, rear = 0;
    int result[MAX_V], count = 0;

    for (int u = 0; u < g->V; u++)
        for (int v = 0; v < g->V; v++)
            if (g->adj[u][v])
                inDegree[v]++;

    for (int v = 0; v < g->V; v++)
        if (inDegree[v] == 0)
            queue[rear++] = v;

    while (front < rear) {
        int u = queue[front++];
        result[count++] = u;

        for (int v = 0; v < g->V; v++) {
            if (g->adj[u][v]) {
                inDegree[v]--;
                if (inDegree[v] == 0)
                    queue[rear++] = v;
            }
        }
    }

    if (count != g->V) {
        printf("Graph has a cycle, no valid topological order.\n");
        return;
    }

    printf("Topological Order: ");
    for (int i = 0; i < count; i++)
        printf("%d ", result[i]);
    printf("\n");
}

int main(void) {
    Graph g;
    initGraph(&g, 5); /* vertices 0..4, matching 1..5 from the example */

    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 2, 3);
    addEdge(&g, 3, 4);

    topologicalSortKahn(&g);

    return 0;
}

Sample Input and Output

Input: DAG with edges (0,1), (0,2), (1,3), (2,3), (3,4).

Output:

Topological Order: 0 1 2 3 4

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version