Topological sort

A topological ordering (or topological sort) of a directed graph is a linear ordering of its vertices such that for every arc u → v, vertex u appears before v in the list. A finite directed graph admits a topological ordering if and only if it is a DAG — if there is a directed cycle, no ordering can respect all edges.

1) Definition

An ordering (v0, v1, …, vn−1) is topological if whenever (vi, vj) is an edge, then i < j in that sequence. The ordering is usually not unique: many valid orders may exist for the same DAG.

2) Existence

• Has topological sort ⇔ DAG. If the graph has a directed cycle, every vertex on the cycle would need to come both before and after itself—impossible.
• Algorithms below either produce an order or detect that fewer than |V| vertices were output, which implies a cycle.

📊 Real‑life examples of topological sorting

These are informal “human” graphs: each row is a DAG if there are no contradictory dependencies. Multiple valid topological orders may exist; the last column shows one acceptable sequence.

🧠 How to read this

• Tasks / nodes — the activities or items you schedule.
• Dependency — what must finish (or be satisfied) before the next step.
• Topological order — one valid linear sequence that respects every dependency (no forward edge goes right‑to‑left in that list).

4) Example DAG

Same diamond as DAG fundamentals—vertices 0 … 4, arcs 0→1, 0→2, 1→3, 2→3, 3→4:

    0 --> 1 --\
    |       \--> 3 --> 4
    '--> 2 --/

5) Kahn's algorithm

Repeatedly remove a vertex with indegree 0 (a source in the remaining graph), append it to the output, and subtract one from the indegree of each of its neighbors. Use a queue for ready vertices. If you output |V| vertices, you have a topological order; if the queue empties early, a cycle exists.

6) C — Kahn (adjacency matrix)

#include <stdio.h>
#include <string.h>

#define V 5
static int adj[V][V];
static int indeg[V];

/* Returns count of vertices written to out[]; V means success (DAG). */
int topo_kahn(int out[V]) {
    memset(indeg, 0, sizeof indeg);
    for (int u = 0; u < V; u++)
        for (int v = 0; v < V; v++)
            indeg[v] += adj[u][v];

    int q[V], qh = 0, qt = 0;
    for (int i = 0; i < V; i++)
        if (indeg[i] == 0) q[qt++] = i;

    int pos = 0;
    while (qh < qt) {
        int u = q[qh++];
        out[pos++] = u;
        for (int v = 0; v < V; v++) {
            if (!adj[u][v]) continue;
            if (--indeg[v] == 0) q[qt++] = v;
        }
    }
    return pos;
}

int main(void) {
    adj[0][1] = adj[0][2] = 1;
    adj[1][3] = adj[2][3] = 1;
    adj[3][4] = 1;
    int order[V];
    int n = topo_kahn(order);
    if (n != V) {
        printf("cycle (or error)\n");
        return 1;
    }
    for (int i = 0; i < V; i++)
        printf("%d%c", order[i], i + 1 < V ? ' ' : '\n');
    return 0;
}

7) DFS — reverse finishing times

Run DFS from every unvisited vertex. When you finish a vertex (all outgoing DFS edges explored), append it—or fill an array from the end backward. Reading that list left‑to‑right yields a topological order. This is the same traversal structure as directed cycle detection; you must skip edges that would revisit a gray vertex.

8) C — DFS topological sort

#include <stdio.h>
#include <string.h>

#define V 5
static int adj[V][V];
static int color[V];   /* 0 white, 1 gray, 2 black */
static int topo[V];
static int ti;         /* next slot from the right */

static int dfs_topo(int u) {
    color[u] = 1;
    for (int v = 0; v < V; v++) {
        if (!adj[u][v]) continue;
        if (color[v] == 1) return 0;   /* cycle */
        if (color[v] == 0 && !dfs_topo(v)) return 0;
    }
    color[u] = 2;
    topo[--ti] = u;
    return 1;
}

int main(void) {
    adj[0][1] = adj[0][2] = 1;
    adj[1][3] = adj[2][3] = 1;
    adj[3][4] = 1;
    memset(color, 0, sizeof color);
    ti = V;
    for (int i = 0; i < V; i++)
        if (color[i] == 0 && !dfs_topo(i))
            return 1;   /* not a DAG */
    for (int i = 0; i < V; i++)
        printf("%d%c", topo[i], i + 1 < V ? ' ' : '\n');
    return 0;
}

9) Complexity

Both approaches visit each vertex and edge a constant number of times: O(V + E) time with adjacency lists; with a dense V × V matrix as written, scanning rows is O(V²). Extra space O(V) for queues, colors, or the output array.

10) Trace — Kahn on the diamond

Queue processes smallest index first among newly ready vertices (implementation detail).

11) Trace — DFS order (one valid result)

DFS from 0, neighbors increasing: path 0→1→3→4, then branch 2. Finishing times last‑to‑first stored in topo[] yield: