What is Topological Sort?
Graph Algorithms·3 min read·code in python
A topological sort puts the nodes of a directed acyclic graph in an order where every edge points forward: if A must happen before B, A comes first. It is the order you would do tasks in when some tasks depend on others, and it exists only when the graph has no cycle.
The intuition: what can I start right now?
Think of course prerequisites. You cannot take Algorithms before Data Structures. Look at everything with nothing left to wait for, take one, and cross it off the lists of the courses that were waiting on it. Repeat.
That is the whole algorithm. Each node keeps a count of how many things must come before it, its in-degree. Nodes at zero are ready; finishing one lowers the count of its neighbours, which may free them.
Kahn's algorithm, with a queue
Count the in-degree of every node. Put every node with in-degree zero in a queue. Pop one, append it to the order, and for each neighbour drop its in-degree by one; when a neighbour hits zero, push it.
When the queue empties, compare the length of the order with the number of nodes. If it is short, the nodes left over sit in a cycle, waiting on each other forever, and no valid order exists. That check is free, which is why Kahn's algorithm is also the standard way to detect a cycle in a directed graph.
The DFS version, and which to pick
The other way is depth-first search: visit a node, recurse into its neighbours, and push the node onto a stack once its subtree is finished. Reversing that stack gives a topological order, because a node is only placed after everything it points to.
Kahn's version reads more like the problem, gives cycle detection in one line, and avoids deep recursion. The DFS version is shorter and fits when you already traverse the graph for something else.
The code
from collections import deque
def topological_sort(n, edges): # nodes are 0..n-1, edges are (before, after)
graph = [[] for _ in range(n)]
in_degree = [0] * n
for a, b in edges:
graph[a].append(b) # a must come before b
in_degree[b] += 1
ready = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while ready:
node = ready.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1 # one dependency less
if in_degree[nxt] == 0:
ready.append(nxt)
return order if len(order) == n else [] # short means a cycleRun it in the browser IDE, free on the platform. Open the IDE
Complexity
| Time | O(V + E) for both Kahn's algorithm and the DFS version. |
|---|---|
| Space | O(V) for the in-degree array and the queue, plus O(V + E) for the graph itself. |
A graph usually has many valid orders. Interviewers accept any of them unless the question asks for a particular one, for example the lexicographically smallest, which needs a heap instead of a queue.
When to use it
- Task or build order: compile units, migrations, CI steps, spreadsheet cells.
- Course schedule problems: can every course be taken, and in what order.
- Dependency resolution between packages or modules.
- Detecting a cycle in a directed graph, as a by-product of the same pass.
Watch out for
- Undirected graphs: there is no before and after, so there is no topological order.
- Graphs with a cycle: no order exists, and the algorithm must say so instead of returning a partial list.
- Expecting one answer: several orders are usually valid.
- Shortest paths: use BFS or Dijkstra; a topological order only fixes the sequence.
Topological Sort: questions we get
What is the time complexity of topological sort?
O(V + E). Every node enters the queue once and every edge is looked at once, in both Kahn's algorithm and the DFS version.
What happens if the graph has a cycle?
No topological order exists. In Kahn's algorithm the queue empties while nodes remain, so the result is shorter than the number of nodes, which is how you detect the cycle.
Kahn's algorithm or the DFS version?
Kahn's reads like the problem and detects cycles with one comparison. DFS is shorter and natural if you are already traversing, but watch the recursion depth on large graphs.
Is the topological order unique?
Usually not. It is unique only when at every step exactly one node has in-degree zero, which means the graph is a single chain.
Related concepts
Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.
Talk to mentor