Topological Sort is a graph algorithm that arranges elements of a Directed Acyclic Graph (DAG) in a linear order that respects dependencies between them. If task A must be completed before task B, A appears before B in the output.

This chapter covers:

Topological sort answers a single question: In what order should we process a set of elements when some of them depend on others?

It applies to problems that can be modeled as a Directed Acyclic Graph (DAG): a graph with directed edges and no cycles. The "no cycles" requirement matters because a cycle means two elements each depend on the other, so neither can come first, and no valid linear order exists.

The goal is to produce a linear ordering of vertices such that: for every directed edge u → v, vertex u appears before vertex v in the final sequence.

For example, consider this dependency graph:

A valid topological ordering would be: C→B→A→D.

Two properties are worth stating:

Topological sort is used whenever items must be processed in an order that respects dependencies.

Common examples include:

There are two common ways to implement topological sort:

METHOD 1: DFS Approach

DFS explores each path to its deepest point before backtracking. This guarantees that all dependencies of a node are fully processed before the node itself. We record each node after its DFS call finishes, then reverse the order at the end.

We use a stack to collect finished nodes:

DFS-based topological sort can be implemented recursively or iteratively with an explicit stack. We will use the recursive form here.

For this graph, the DFS traversal might visit nodes in the order A → B → C → D. The ordering depends on two details of the algorithm:

The time complexity is O(V + E), since each vertex is visited once and each edge is examined once during the traversal. The space complexity is O(V) for the visited array, the stack of finished nodes, and the recursion stack.

The second approach uses BFS instead of DFS. It is called Kahn's Algorithm.

METHOD 2: BFS Approach - Kahn’s Algorithm

Kahn’s Algorithm is an iterative, queue-based method for topological sorting.

It repeatedly removes nodes with no incoming edges (no unmet dependencies), building a valid order as it goes.

Kahn’s Algorithm is based on the following idea:

If a node has no incoming edges (or prerequisites), it can be processed first. Removing it reduces the indegree of its neighbors; any neighbor for which indegree drops to 0 is processed in the next iteration.

Here’s how it works step-by-step:

Step 1: Compute in-degree for each node

The indegree of a node is the number of incoming edges (or dependencies) pointing to it. A node with indegree 0 has no unmet dependencies, so it is safe to process immediately.

For example, in this graph:

Step 2: Identify Nodes with 0 Indegree

Any node with 0 indegree can be processed first, since it has no dependencies.

Add these ready-to-process nodes to a queue.

Step 3: Process Nodes using BFS

While the queue isn't empty:

This ensures each node is only processed after all its prerequisites have been handled.

At the end, if the result contains fewer than V nodes, the graph isn’t a DAG (there’s a cycle), so no topological order exists.

Here’s how to implement it in code:

The time complexity is O(V + E), as each vertex and edge is processed exactly once during the traversal.

The space complexity is O(V), required for storing the indegree array, result list, and BFS queue.

If all nodes are processed, the result is a valid topological order.

If some nodes remain unprocessed, the graph contains a cycle and no topological order exists.

Kahn's algorithm has two practical differences from the DFS-based approach:

Time Complexity

Both the DFS approach and Kahn's algorithm run in O(V + E). Each vertex is processed exactly once and each edge is examined exactly once. The DFS approach visits every adjacency entry as it traverses the graph, and Kahn's algorithm decrements an in-degree once per edge while draining the queue. Computing the in-degrees in Kahn's algorithm also takes O(V + E), since it initializes V counters and scans every edge once, so this preprocessing step does not change the overall bound.

Space Complexity

Both approaches need O(V + E) space to store the graph as an adjacency list, plus O(V) auxiliary space. The auxiliary space holds the visited array or the in-degree array, the queue or the recursion stack, and the output ordering, each of which grows with the number of vertices. If the input graph storage is excluded from the count, the auxiliary space is O(V).