Topological Sort: Ordering a Directed Acyclic Graph

June 2026 · 30 min read

Given a set of tasks where some must be completed before others, how do you find a valid execution order? This is exactly the problem that Topological Sort solves. It takes a Directed Acyclic Graph (DAG) and produces a linear ordering of its vertices such that for every directed edge u→v, vertex u appears before vertex v. In this post we’ll explore two classic algorithms — Kahn’s BFS approach and the DFS approach — with step-by-step visual walkthroughs, an interactive animation, C++ implementations, and competitive programming applications.

What Is Topological Sorting?

A topological ordering of a directed graph is a linear sequence of all its vertices such that if there is an edge from vertex u to vertex v, then u appears before v in the ordering. This ordering is only possible when the graph has no directed cycles — that is, the graph must be a DAG (Directed Acyclic Graph).

Consider this DAG with 7 nodes representing course prerequisites:

Edges: 0→1, 0→2, 1→3, 1→4, 2→4, 2→5, 3→6, 4→6, 5→6. One valid topological ordering is [0, 1, 2, 3, 4, 5, 6]. Another is [0, 2, 5, 1, 4, 3, 6]. Both respect all edge directions.

Real-World Examples

• Build systems: Compiling source files in dependency order (e.g., Makefiles). A file must be compiled only after all files it depends on are compiled.
• Task scheduling: Ordering tasks so that every task runs after its prerequisites are complete.
• Course prerequisites: Planning a semester schedule where each course is taken only after its prerequisites.
• Package managers: Installing packages in the right order so that dependencies are satisfied (e.g., apt, npm).
• Spreadsheet evaluation: Computing cell values in an order that respects formula dependencies.

Formal Properties

DAG Theorem

Proof sketch (⇒): If a topological ordering exists, suppose there is a cycle v₁→v₂→…→v_k→v₁. Then f(v₁) < f(v₂) < … < f(v_k) < f(v₁), a contradiction. So no cycle exists — it must be a DAG.

Proof sketch (⇐): Every DAG has at least one vertex with in-degree 0 (otherwise, following predecessors from any vertex would eventually revisit a vertex, creating a cycle). Remove this vertex, and the remaining graph is still a DAG. Repeat until all vertices are removed. The removal order is a valid topological ordering.

Uniqueness

A topological ordering is unique if and only if there is a Hamiltonian path in the DAG — that is, a directed path that visits every vertex exactly once. Equivalently, at every step of Kahn’s algorithm there is exactly one vertex with in-degree 0. If at any point there are multiple vertices with in-degree 0, multiple valid orderings exist.

Key Observations

• Every DAG has at least one topological ordering.
• A DAG with n vertices can have up to n! topological orderings (e.g., a graph with no edges).
• The first vertex in every topological ordering has in-degree 0.
• The last vertex in every topological ordering has out-degree 0.

Kahn’s Algorithm (BFS-Based)

Kahn’s algorithm (1962) takes the constructive proof above and turns it into an efficient algorithm. It repeatedly finds vertices with in-degree 0 (no remaining prerequisites), removes them from the graph, and adds them to the result.

Step-by-Step Walkthrough

Let’s trace Kahn’s algorithm on our 7-node DAG. We track the in-degree array, queue, and result at each step.

DFS-Based Topological Sort

The DFS approach uses a simple observation: in a DFS traversal of a DAG, a node finishes (all its descendants are fully explored) after all nodes reachable from it have finished. If we record nodes in reverse post-order (push to a stack when a node finishes, then reverse), we get a valid topological ordering.

Step-by-Step Walkthrough

Let’s trace DFS topological sort on the same graph, starting from node 0.

Both orderings — [0, 1, 2, 3, 4, 5, 6] from Kahn’s and [0, 2, 5, 1, 4, 3, 6] from DFS — are valid. They differ because the algorithms break ties differently.

Kahn’s vs DFS: Comparison

Interactive Animation

Step through Kahn’s algorithm at your own pace, or press Play to watch it unfold automatically. The animation shows the queue, in-degree array, and result building up in real time.

Detecting Cycles (Is Topological Sort Possible?)

Topological sort is only defined for DAGs. If the graph has a cycle, no valid ordering exists. Both algorithms can detect this:

Via Kahn’s Algorithm

If the final result contains fewer than V vertices, there is a cycle. This is because nodes in a cycle never reach in-degree 0 — they form a deadlock where each node is waiting for another node in the cycle.

Via DFS

During DFS, use a three-color scheme: white (unvisited), gray (in current recursion stack), black (finished). If DFS encounters a gray node, that is a back edge, which means a cycle exists.

All Topological Orderings

Sometimes we need to count or enumerate all valid topological orderings of a DAG. This can be done with backtracking: at each step, pick any node with in-degree 0, add it to the current ordering, reduce in-degrees, and recurse. When backtracking, undo the in-degree changes.

For our example graph, the valid topological orderings include:

• [0, 1, 2, 3, 4, 5, 6]
• [0, 1, 2, 3, 5, 4, 6]
• [0, 1, 2, 5, 3, 4, 6]
• [0, 2, 1, 3, 4, 5, 6]
• [0, 2, 1, 3, 5, 4, 6]
• [0, 2, 1, 5, 3, 4, 6]
• [0, 2, 1, 5, 4, 3, 6]
• [0, 1, 3, 2, 4, 5, 6]
• …and more

Lexicographically Smallest Topological Sort

A common competitive programming variant asks for the lexicographically smallest topological ordering. The trick is simple: replace the queue in Kahn’s algorithm with a min-heap (priority queue). At each step, we always pick the smallest-numbered available node.

For our example, this produces [0, 1, 2, 3, 4, 5, 6] — the lexicographically smallest valid ordering. The time complexity is O((V + E) log V) due to heap operations.

C++ Implementation

Kahn’s Algorithm (BFS)

#include <bits/stdc++.h>
using namespace std;

vector<int> kahnTopoSort(int V, vector<vector<int>>& adj) {
    vector<int> indegree(V, 0);
    for (int u = 0; u < V; u++)
        for (int v : adj[u])
            indegree[v]++;

    queue<int> q;
    for (int i = 0; i < V; i++)
        if (indegree[i] == 0)
            q.push(i);

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

    if ((int)result.size() != V) {
        // Graph has a cycle — no topological ordering
        return {};
    }
    return result;
}

int main() {
    int V = 7;
    vector<vector<int>> adj(V);
    adj[0] = {1, 2};
    adj[1] = {3, 4};
    adj[2] = {4, 5};
    adj[3] = {6};
    adj[4] = {6};
    adj[5] = {6};

    vector<int> order = kahnTopoSort(V, adj);
    if (order.empty()) {
        cout << "Cycle detected!" << endl;
    } else {
        for (int v : order) cout << v << " ";
        cout << endl;
    }
    return 0;
}
// Output: 0 1 2 3 4 5 6

DFS-Based Topological Sort

#include <bits/stdc++.h>
using namespace std;

enum Color { WHITE, GRAY, BLACK };

bool dfs(int u, vector<vector<int>>& adj,
         vector<Color>& color, vector<int>& stk) {
    color[u] = GRAY;
    for (int v : adj[u]) {
        if (color[v] == GRAY) return false; // cycle
        if (color[v] == WHITE)
            if (!dfs(v, adj, color, stk)) return false;
    }
    color[u] = BLACK;
    stk.push_back(u);
    return true;
}

vector<int> dfsTopoSort(int V, vector<vector<int>>& adj) {
    vector<Color> color(V, WHITE);
    vector<int> stk;

    for (int i = 0; i < V; i++)
        if (color[i] == WHITE)
            if (!dfs(i, adj, color, stk))
                return {}; // cycle detected

    reverse(stk.begin(), stk.end());
    return stk;
}

int main() {
    int V = 7;
    vector<vector<int>> adj(V);
    adj[0] = {1, 2};
    adj[1] = {3, 4};
    adj[2] = {4, 5};
    adj[3] = {6};
    adj[4] = {6};
    adj[5] = {6};

    vector<int> order = dfsTopoSort(V, adj);
    if (order.empty()) {
        cout << "Cycle detected!" << endl;
    } else {
        for (int v : order) cout << v << " ";
        cout << endl;
    }
    return 0;
}
// Output: 0 2 5 1 4 3 6

Lexicographically Smallest Ordering

#include <bits/stdc++.h>
using namespace std;

vector<int> lexTopoSort(int V, vector<vector<int>>& adj) {
    vector<int> indegree(V, 0);
    for (int u = 0; u < V; u++)
        for (int v : adj[u])
            indegree[v]++;

    // Min-heap instead of regular queue
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < V; i++)
        if (indegree[i] == 0)
            pq.push(i);

    vector<int> result;
    while (!pq.empty()) {
        int u = pq.top(); pq.pop();
        result.push_back(u);
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0)
                pq.push(v);
        }
    }

    if ((int)result.size() != V) return {};
    return result;
}

int main() {
    int V = 7;
    vector<vector<int>> adj(V);
    adj[0] = {1, 2};
    adj[1] = {3, 4};
    adj[2] = {4, 5};
    adj[3] = {6};
    adj[4] = {6};
    adj[5] = {6};

    vector<int> order = lexTopoSort(V, adj);
    for (int v : order) cout << v << " ";
    cout << endl;
    return 0;
}
// Output: 0 1 2 3 4 5 6

Applications in Competitive Programming

More Patterns

• Shortest paths in a DAG: Relax edges in topological order — O(V + E), beating Dijkstra for DAGs with negative weights.
• Number of paths: Count paths from source to each node by summing path counts of predecessors in topological order.
• Parallel job scheduling: The minimum number of “rounds” to complete all tasks is the length of the longest path in the DAG (critical path method). Kahn’s naturally gives layers.
• Build order: Determine compilation order for source files with dependencies (like Make, Bazel, Gradle).

Practice Problems

Summary

Let’s recap the key takeaways:

1. Topological Sort produces a linear ordering of vertices in a DAG such that every edge goes from earlier to later in the ordering.
2. Kahn’s Algorithm (BFS) uses in-degree counting and a queue to peel off source nodes layer by layer. It naturally detects cycles and is easy to modify for lexicographic ordering.
3. DFS-based approach records nodes in reverse post-order. It integrates well with DP on DAGs and is the foundation of SCC algorithms.
4. Both algorithms run in O(V + E) time and space.
5. For lexicographically smallest ordering, use Kahn’s with a min-heap — O((V + E) log V).
6. To enumerate all orderings, use backtracking with in-degree tracking (exponential, only for small graphs).