Topological Sort in C — Kahn’s Algorithm with Cycle Detection

Topological sort orders the vertices of a directed acyclic graph (DAG) so that every edge points forward: if there’s an edge from u to v, then u appears before v in the ordering. It’s the algorithm behind every dependency system you’ve used — build tools compiling files in the right order, package managers resolving installs, course schedulers handling prerequisites. This page implements Kahn’s algorithm in C: the queue-based, in-degree-counting approach that also detects cycles for free — all in tested, warning-free C89.

How Kahn’s Algorithm Works — Step by Step

1. Compute the in-degree of every vertex (how many edges point into it).
2. Put every vertex with in-degree 0 into a queue — these have no prerequisites, so they can go first.
3. Repeatedly dequeue a vertex, append it to the output order, and “remove” its outgoing edges: decrement the in-degree of each neighbor. Any neighbor that drops to in-degree 0 joins the queue.
4. When the queue empties: if you output all n vertices, that’s a valid topological order. If fewer, the leftover vertices form a cycle — no valid ordering exists.

Example trace (6 vertices, edges 5→2, 5→0, 4→0, 4→1, 2→3, 3→1):

Step	Queue	Dequeued	In-degrees hit 0	Order so far
init	4, 5	—	4 and 5 start at 0
1	5	4	—	4
2	0, 2	5	0, 2	4 5
3	2	0	—	4 5 0
4	3	2	3	4 5 0 2
5	1	3	1	4 5 0 2 3
6	—	1	—	4 5 0 2 3 1

C Program for Topological Sort (Kahn’s Algorithm)

#include <stdio.h>

#define MAX_VERTICES 20

int main(void)
{
    int adj[MAX_VERTICES][MAX_VERTICES] = {{0}};
    int indegree[MAX_VERTICES] = {0};
    int queue[MAX_VERTICES];
    int order[MAX_VERTICES];
    int front = 0, rear = 0, count = 0;
    int n, m, i, u, v;

    printf("Enter the number of vertices: ");
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX_VERTICES) {
        printf("Invalid number of vertices.\n");
        return 1;
    }
    printf("Enter the number of edges: ");
    if (scanf("%d", &m) != 1 || m < 0 || m > MAX_VERTICES * MAX_VERTICES) {
        printf("Invalid number of edges.\n");
        return 1;
    }
    printf("Enter each edge as: from to (vertices 0..%d)\n", n - 1);
    for (i = 0; i < m; i++) {
        if (scanf("%d %d", &u, &v) != 2 || u < 0 || u >= n || v < 0 || v >= n) {
            printf("Invalid edge.\n");
            return 1;
        }
        if (!adj[u][v]) {                /* ignore duplicate edges */
            adj[u][v] = 1;
            indegree[v]++;
        }
    }

    /* Kahn's algorithm: start with every vertex that has no prerequisites */
    for (i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    while (front < rear) {
        u = queue[front++];
        order[count++] = u;
        for (v = 0; v < n; v++) {
            if (adj[u][v]) {
                adj[u][v] = 0;
                if (--indegree[v] == 0) {
                    queue[rear++] = v;
                }
            }
        }
    }

    if (count != n) {
        printf("The graph contains a cycle - topological sort impossible.\n");
        return 1;
    }
    printf("Topological order: ");
    for (i = 0; i < count; i++) {
        printf("%d ", order[i]);
    }
    printf("\n");
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra -o toposort toposort.c
./toposort

Sample Input and Output

Test 1 — the 6-vertex DAG traced above:

Enter the number of vertices: 6
Enter the number of edges: 6
Enter each edge as: from to (vertices 0..5)
5 2
5 0
4 0
4 1
2 3
3 1
Topological order: 4 5 0 2 3 1

Test 2 — a graph with a cycle (0→1, 1→2, 2→0):

Enter the number of vertices: 3
Enter the number of edges: 3
Enter each edge as: from to (vertices 0..2)
0 1
1 2
2 0
The graph contains a cycle - topological sort impossible.

Note that a DAG usually has several valid topological orders — 4 5 0 2 3 1 and 5 4 2 0 3 1 both satisfy every edge here. Kahn’s algorithm returns the one determined by its queue order.

Code Explanation

• indegree[v]++ — built while reading edges, so no separate counting pass is needed. Duplicate edges are ignored to keep counts honest.
• queue[] with front/rear — a simple array queue; every vertex enters at most once, so MAX_VERTICES slots are enough.
• adj[u][v] = 0; --indegree[v] — “removing” the processed vertex’s outgoing edges is what may release neighbors into the queue.
• count != n — the built-in cycle detector: vertices trapped in a cycle never reach in-degree 0, never enter the queue, and never get counted. (The 2012 version of this post had no cycle handling at all — and its code didn’t even compile: it called scamf().)

Time and Space Complexity

Aspect	Complexity	Why
Time (adjacency matrix)	O(V²)	each dequeued vertex scans a full matrix row
Time (adjacency list)	O(V + E)	each edge examined exactly once — use lists for big sparse graphs
Space	O(V²) matrix / O(V + E) list	plus O(V) for queue, order, and in-degrees

What This Program Teaches

• In-degree reasoning: “no incoming edges” = “no unmet prerequisites”
• An array-based queue with front/rear indices — no linked list needed when elements enter once
• Cycle detection as a natural by-product of the algorithm, not an extra pass
• Why real-world dependency tools (make, package managers) can report “circular dependency” precisely

Related C Programs

• Breadth-First Search (BFS) in C — Kahn’s algorithm is BFS with in-degrees
• Depth-First Search (DFS) in C — the other way to topo-sort (reverse post-order)
• Kruskal’s Algorithm in C
• Dijkstra’s Algorithm in C

Test yourself: our free C Programming Quiz app for Android has 150+ questions with explanations for every answer.

Recommended Book

The C Programming Language by Kernighan & Ritchie remains the definitive C reference — we’ve solved all of its exercises. Also on Amazon.com.