Topological Sort · Kahn's BFS

Order tasks so every prerequisite comes first. Kahn's idea: repeatedly grab whatever has no remaining dependencies (indegree 0), output it, and relax its neighbors.

Concept

The idea

Compute each node's indegree (incoming edges). Any node with indegree 0 has no unmet prerequisites, so it's safe to place next. Remove it, decrement its neighbors, repeat.

Cycle detection built in

Seed a queue with all indegree-0 nodes
Pop → append to order → relax neighbors
Neighbor hitting indegree 0 joins the queue
If order size < V, a cycle blocked some nodes

Interactive

Build the order

Waiting In queue (indeg 0) Processing Placed in order

Queue: empty

slowfast

Step 0

Placed

Queue size

Processing

–

Valid DAG?

Implementation

C++

vector<int> topoSort(int n, vector<vector<int>>& adj) {
    vector<int> indeg(n, 0);
    for (int u = 0; u < n; u++)
        for (int v : adj[u]) indeg[v]++;

    queue<int> q;
    for (int i = 0; i < n; i++)
        if (indeg[i] == 0) q.push(i);   // no prerequisites

    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indeg[v] == 0) q.push(v);  // now unblocked
    }

    if (order.size() != n) return {};  // cycle → no valid order
    return order;
}

Complexity

Time

O(V + E)

One pass to build indegrees, one pass processing each node and edge.

Space

O(V)

Indegree array plus the queue and output order.

Cycle check

size < V

If fewer than V nodes come out, some were stuck in a cycle.

Notes

Kahn's = BFS flavor of topo sort. It naturally detects cycles: a cycle keeps indegrees above 0 forever, so those nodes never enqueue.
The order isn't unique. Any node with indegree 0 is fair game, using a min-heap instead of a queue gives the lexicographically smallest order.
Course Schedule II wants the actual order; Course Schedule I only asks "is it possible" (cycle check).
Only works on directed graphs. Topological order is meaningless for undirected ones.
DFS-based topo sort is the alternative: push nodes on finish, then reverse.