Topological Sort

Graphs O(V + E) O(V)

Linear ordering of a DAG's nodes so every edge points forward — Kahn's algorithm peels off in-degree-0 nodes.

1/23

Count in-degrees (badge under each node).

InvariantEvery node emitted so far has had all of its prerequisites emitted before it.

currentfrontiervisitedtree edge

topological-sort.c

#define V 6
 
void topoSort(int graph[V][V]) {
    int indeg[V] = {0};
    for (int u = 0; u < V; u++)
        for (int v = 0; v < V; v++)
            if (graph[u][v]) indeg[v]++;
 
    int queue[V], front = 0, rear = 0;
    for (int v = 0; v < V; v++)
        if (indeg[v] == 0) queue[rear++] = v;
 
    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (int v = 0; v < V; v++) {
            if (graph[u][v] && --indeg[v] == 0)
                queue[rear++] = v;
        }
    }
 
    if (rear < V)
        printf("\ncycle: %d node(s) never reached in-degree 0", V - rear);
}

How Topological Sort works

Repeatedly peel off a node with no incoming edges and delete its outgoing edges (Kahn's algorithm). If the queue runs dry before all nodes are output, the graph has a cycle.

When to use it

Ordering tasks under dependencies: build systems, course prerequisites, spreadsheet evaluation.