Learn Topological Sort Algorithm

Topological Sort is an algorithm that orders the vertices of a directed acyclic graph (DAG) into a linear sequence so that every directed edge u→v means u appears before v in the order.

In practice, this sorting resolves dependencies in graphs. For example, scheduling tasks with prerequisites, arranging course requirements, or determining build order for software modules. Because it considers edge directions, topological sort finds a valid sequence that respects all constraints in the DAG.

In the following sections, we will see how to compute a topological ordering using algorithmic methods. Specifically, we will examine both the Depth-First based and Kahn’s Breadth-first Search (BFS) approaches for topological sort, along with their pseudocode and complexity.

These methods will show how each vertex is placed only after all its prerequisites, ensuring the dependency graph is correctly linearised.

Key Takeaways

What Is Topological Sort?

Topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge (u → v), vertex u comes before v in the ordering. This definition implies a strict dependency order:

If there is an edge indicating “u must come before v,” then in the topologically sorted list, u precedes v.

In concise terms, topological sort arranges all nodes so that each node appears after all nodes that have edges pointing to it. Topological ordering is only possible when the graph has no cycles. In fact, a valid topological order exists if and only if the graph is acyclic.

If any directed cycle is present, then no linear ordering can satisfy all edge directions. For example, u→v→w→u.

Thus, topological sort requires a DAG and immediately detects impossible cases. If the graph is acyclic, there is guaranteed to be at least one topological ordering. When a graph is a DAG, there may be multiple valid topological orders. In other words, the ordering is not necessarily unique.

Any arrangement that respects all edge directions is acceptable. For example, if two nodes have no path between them, they can appear in either order. All such valid sequences are considered topological sorts of the graph.

Topological Sort in Directed Acyclic Graphs (DAGs)

A topological sort operates on a directed acyclic graph (DAG). Here, vertices can represent tasks or entities, and directed edges encode precedence constraints. The goal is to list all vertices so that every edge (dependency) points from an earlier vertex to a later one.

By definition, a topological ordering exists if and only if the graph has no directed cycles. Each cycle would create a mutual dependency loop that cannot be linearly ordered.

To illustrate, imagine a simple DAG with edges A→B and A→C. Valid topological orders include [A, B, C] and [A, C, B] – in both, A comes before B and C. However, if there were an edge back from B to A (forming a cycle A→B→A), no ordering would satisfy both constraints, so that topological sort would fail. In general, topological sort is widely used in dependency resolution problems.

For example, building software modules where some modules depend on others, scheduling university courses with prerequisites, or ordering tasks in project management are all modeled as topological sorts on a graph. In each case, performing the topological sort ensures that a task (vertex) appears only after all its prerequisites.

Applications of Topological Sort

Topological Sort is especially useful whenever one task must be completed before another. It helps convert a dependency-based graph into a clear execution order, making it highly practical in real-world systems where sequencing matters.

Some of the most common applications of the topological sort algorithm include:

1. Task Scheduling

Determines the correct order of tasks when some tasks depend on others. It also helps identify which tasks can run in parallel and which must wait.

2. Build Order in Software Development

Ensures that source files, libraries, or modules are compiled only after all their dependencies are resolved, preventing build-time errors.

3. Course Prerequisite Ordering

Organizes courses so that foundational subjects are completed before advanced ones, maintaining a valid academic progression.

4. Dependency Resolution in Systems

Used in package managers and data pipelines to resolve dependencies and execute processes in the correct sequence.

5. Workflow Management

Helps structure complex workflows in areas like data engineering, CI/CD pipelines, and project planning.

How Does Topological Sort Work?

Topological Sort works by arranging the vertices of a Directed Acyclic Graph (DAG) so that every directed edge goes from an earlier vertex to a later one. In practice, that means the algorithm always respects dependencies.

A node is placed in the ordering only after the nodes it depends on have been handled. A graph can be topologically sorted only if it has no directed cycles.
There are two standard ways to build the ordering. The topological sort DFS approach uses depth-first traversal and records a node after all of its outgoing neighbors have been processed; the topological sort BFS approach uses Kahn’s algorithm, which repeatedly removes nodes with in-degree 0 and updates their neighbors. Both methods produce a valid ordering for a DAG.

Kahn’s Algorithm for Topological Sort

Kahn’s Algorithm is the BFS-based method for topological sort. It begins by counting the number of incoming edges for each node, then repeatedly selects nodes that have no prerequisites. This is the most direct way to build a valid order because every removed node is guaranteed to be safe to place next.

Here’s a step-by-step breakdown of Kahn’s Algorithm.

1. Compute the in-degree of every vertex
2. Add every vertex with in-degree 0 to a queue
3. Remove one vertex from the queue and append it to the topological order
4. For each outgoing edge from that vertex, decrement the in-degree of the neighbor
5. If any neighbor’s in-degree becomes 0, add it to the queue
6. Repeat until the queue becomes empty
7. If all vertices were processed, the result is a valid topological ordering; otherwise, a cycle exists

Why Topological Sort Does Not Work for Cyclic Graphs?

Topological Sort fails on cyclic graphs because a cycle creates a circular dependency. If one node must come before the next node in the cycle, and the last node must come before the first, no linear order can satisfy all constraints at once. In other words, a topological ordering exists only for DAGs, not for graphs with directed cycles.

For Kahn’s Algorithm, the failure is visible immediately. Every node in a directed cycle has at least one incoming edge from another node in the same cycle, so no node in the cycle can start with an in-degree of 0.

If the graph contains only cyclic dependencies, the queue never gets a starting node, and the algorithm stops before producing a full ordering.

Example cycle: A → B → C → A

Since no node has an in-degree of 0, Kahn’s Algorithm cannot begin. That is exactly why cyclic graphs do not have a valid topological order.

Topological Sort Example Using Kahn’s Algorithm

Consider this DAG:

• A → C
• B → C
• C → D
• D → E

This graph has no cycles, so Topological Sort is possible. Using Kahn’s Algorithm, we first calculate in-degrees, then process nodes with in-degree 0. The order is not always unique, but it must always respect every dependency edge.

Now apply Kahn’s Algorithm step by step:

1. Start with the zero in-degree nodes: A and B
2. Remove A, then reduce C’s in-degree from 2 to 1
3. Remove B, then reduce C’s in-degree from 1 to 0
4. Add C to the queue and remove it next
5. Reduce D’s in-degree from 1 to 0, then remove D
6. Reduce E’s in-degree from 1 to 0, then remove E
7. One valid topological order is A, B, C, D, E. Another valid order could be B, A, C, D, E

Also Read: Find the Order of Characters From an Alien Dictionary Problem

Topological Sort Algorithm

Topological Sort is a dependency-ordering algorithm for a directed acyclic graph (DAG). It produces a linear ordering of vertices such that for every directed edge u → v, vertex u appears before vertex v. A valid topological order exists only when the graph has no directed cycles.

At a high level, the logic is simple.

Find a way to place all nodes so that every prerequisite comes before the node that depends on it. The two standard approaches are topological sort DFS, which pushes a node after exploring all of its outgoing neighbors, and topological sort BFS, which uses Kahn’s algorithm to repeatedly remove nodes with in-degree 0.

Both approaches run in linear time, O(V + E), because each vertex and edge is processed a constant number of times.

Topological Sort Pseudocode

Before looking at implementation details, it helps to understand the structure of the topological sort pseudocode itself. Process every node in a way that respects its dependencies, then place it in the ordering only when its prerequisites have already been handled.

The DFS version builds the order in reverse finishing-time order, while the BFS version follows Kahn’s algorithm and removes zero-in-degree vertices one by one.

TopologicalSort_DFS(graph):

visited = set()
stack   = empty stack
for each vertex v in the graph:
    if v not in visited:
        DFS(v)
return stack reversed

DFS(v):
    Mark v as visited
    for each neighbor n of v:
        if n not in visited:
            DFS(n)
    push v onto stack

TopologicalSort_Kahn(graph):
    inDegree = array of size V initialized to 0
    queue    = empty queue
    order    = empty list
    for each edge u -> v in graph:
        inDegree[v]++
    for each vertex v:
        if inDegree[v] == 0:
            enqueue(queue, v)
    while queue is not empty:
        u = dequeue(queue)
        append u to order
        for each neighbor n of u:
            inDegree[n]--
            if inDegree[n] == 0:
                enqueue(queue, n)
    if length(order) != V:
        report "graph has a cycle."
    else:
        return order

Topological Sort Code

To better understand how the topological sort algorithm works in practice, it is useful to look at a concrete implementation. Writing code helps translate the conceptual steps, like managing degrees and processing dependencies, into an executable form.

The following examples demonstrate how topological sorting can be implemented using a queue-based approach, making the dependency resolution process explicit and easy to follow.

Java

import java.util.*;

public class TopologicalSortKahn {
    public static List<Integer> topologicalSort(int vertices, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            graph.add(new ArrayList<>());
        }
        int[] indegree = new int[vertices];
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            graph.get(u).add(v);
            indegree[v]++;
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < vertices; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        List<Integer> order = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int neighbor : graph.get(node)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        if (order.size() != vertices) {
            throw new IllegalArgumentException("Graph contains a cycle; topological sort is not possible.");
        }
        return order;
    }

    public static void main(String[] args) {
        int vertices = 6;
        int[][] edges = {
            {5, 2}, {5, 0}, {4, 0}, {4, 1}, {2, 3}, {3, 1}
        };
        List<Integer> result = topologicalSort(vertices, edges);
        System.out.println(result);
    }

Python

from collections import deque

def topological_sort(vertices, edges):
    graph    = [[] for _ in range(vertices)]
    indegree = [0] * vertices
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    queue = deque()
    for node in range(vertices):
        if indegree[node] == 0:
            queue.append(node)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    if len(order) != vertices:
        raise ValueError("Graph contains a cycle; topological sort is not possible.")
    return order

if __name__ == "__main__":
    vertices = 6
    edges    = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
    print(topological_sort(vertices, edges))

Example Output

For the sample graph above, one valid output is:

[4, 5, 2, 0, 3, 1]

Another valid ordering may also exist, because a DAG can have more than one correct topological order. The only rule is that every directed edge must still go from left to right in the final sequence.

Topological Sort Complexity

Topological Sort complexity describes how the algorithm’s running time and extra memory use grow as the graph gets larger. For the standard implementations on a Directed Acyclic Graph (DAG), the key result is that both DFS-based topological sort and Kahn’s BFS-based topological sort process each vertex and each edge a constant number of times.

So, the overall time complexity is linear in the size of the graph.

Topological Sort Time Complexity

The time complexity of Topological Sort is O(V + E), where V is the number of vertices and E is the number of edges. In a DFS-based approach, each vertex is visited once, and each directed edge is explored once during traversal.

In Kahn’s algorithm, you first compute in-degrees, then repeatedly remove zero in-degree nodes and update their neighbors, which still touches each vertex and edge a constant number of times.

A simple real-world example is a course prerequisite graph. If a curriculum has 100 courses and 250 prerequisite links, the algorithm does not compare every course with every other course. It only processes the 100 courses and the 250 prerequisite relationships, which is exactly why the runtime scales as O(V + E), not O(V²).

Topological Sort Space Complexity

The space complexity of Topological Sort is typically O(V) for the algorithm’s extra working memory. In DFS-based topological sort, this comes from the visited structure and the recursion stack.

In Kahn’s algorithm, this comes from the queue, the in-degree array, and the output list. If you also count the adjacency-list graph storage itself, the full representation of the graph uses O(V + E) space, but that is the graph’s storage cost, not the algorithm’s extra auxiliary memory.

A practical way to picture this is with a build system. The graph stores modules and dependency links, while the algorithm keeps only the currently relevant modules in memory. The recursion path for DFS or the zero-in-degree queue for Kahn’s algorithm.

That is why space usage stays linear in the number of vertices rather than exploding with the number of possible node pairs.

Strengths and Weaknesses of Topological Sort

Topological Sort is strongest when a problem can be modeled as dependencies in a Directed Acyclic Graph (DAG). It gives a valid linear order for tasks, builds, courses, and other prerequisite-driven workflows, and it does so efficiently in O(V + E) time for standard DFS- and BFS-based implementations.

It is also practical in build systems and dependency-resolution tools, including Make-like workflows, because it helps ensure prerequisites are processed before dependent items.

Its main limitation is that it only works on DAGs. If the graph contains a directed cycle, no valid topological ordering exists because the dependencies become circular.

Topological Sort also does not always return a unique order; when multiple vertices have no incoming edges, several valid sequences may exist. For very large graphs, the algorithm is still linear, but the graph storage and traversal overhead can become heavy in practice because the adjacency structure itself uses memory proportional to the graph size.

Take Your Topological Sort Skills Further

Understanding Topological Sort is just one part of mastering graph algorithms and dependency-based problem solving. To truly apply concepts like the topological sort algorithm, topological sort DFS, and topological sort BFS in real scenarios, you need structured practice, expert guidance, and real-world problem exposure.

The Software Engineering Interview Prep course by Interview Kickstart is designed to help you build exactly that level of confidence and depth.

• Comprehensive DSA training: Strengthen your understanding of graph algorithms, including complex dependency problems like topological sort graph scenarios.
• 1:1 mentorship and coaching: Get personalized help to improve your problem-solving approach and implementation skills.
• Mock interviews with industry experts: Practice applying concepts like topological sort in real interview-like environments.
• End-to-end career support: Resume building, LinkedIn optimization, and behavioral interview prep.

If you’re serious about mastering algorithms and applying them effectively, consider this as your next step.

Conclusion

Topological Sort is a core graph technique for turning dependency-heavy problems into a valid linear order. It works only on directed acyclic graphs (DAGs), and it is especially useful in task scheduling, software build order, course prerequisite ordering, and other dependency-resolution workflows.

In practice, the two standard implementations are the DFS-based approach and Kahn’s BFS-based algorithm, both of which run in linear time relative to the graph size. If a cycle exists, no valid topological ordering is possible.

For practical use, think of Topological Sort as the method you reach for when one step must happen before another. That is why it fits build systems, package dependency resolution, and scheduled pipelines so well.

FAQs: Topological Sort

Q1. Is topological sort DFS or BFS?

A topological sort can be performed using both DFS and BFS. The DFS-based method adds nodes after exploring their descendants, while the BFS-based method uses Kahn’s algorithm to remove nodes with in-degree 0 repeatedly.

Q2. Is topological sort a greedy algorithm?

Not in the classic sense. Topological Sort is mainly a graph ordering algorithm. Kahn’s algorithm makes locally valid choices by picking nodes with no incoming edges, but it is usually described as a dependency-resolution method rather than a standard greedy algorithm.

Q3. Why use BFS instead of DFS?

BFS, through Kahn’s algorithm, is often preferred when you want an iterative approach that is easier to trace and naturally detects cycles using in-degree counts. It is especially useful when you want to process nodes level by level as dependencies become available.

Q4. Why is topological sort useful?

Topological Sort is useful for problems with prerequisites and dependency chains, such as task scheduling, build order, course prerequisite ordering, and dependency resolution in software systems. It helps ensure every item appears only after the items it depends on.

Q5. Can topological sort have multiple valid orders?

Yes, Topological Sort can produce multiple valid orderings. If at any step there are multiple nodes with no incoming edges (in-degree 0), the algorithm can choose any of them next. As long as all dependency constraints are satisfied, each resulting sequence is a correct topological ordering.

References

1. Software Developers, Quality Assurance Analysts, and Testers
2. CompTIA Tech Jobs Report

Related Articles:

• Tree Traversal: Inorder, Preorder, Postorder, and Level-order
• DFS Traversal of a Tree Using Recursion
• Difference Between Recursion and Iteration