What Is a Topological Order? The Concept Every DAG Problem Needs
- Topological order arranges directed graph nodes so every edge points from an earlier node to a later one in the sequence
- A valid ordering exists if and only if the graph is a DAG; any cycle makes it impossible
- Kahn's algorithm uses in-degree counts and BFS; if the result is shorter than the node count, a cycle exists
- DFS postorder appends nodes in reverse finish order; the
in_stackflag is what catches cycles - Both algorithms run in O(V + E) time and O(V) space, which is also the theoretical floor
- Multiple valid orderings exist for most graphs; all correct orderings are equally valid
- Reach for topological sort whenever a problem gives "X must come before Y" constraints on a directed graph
You can't put on your shoes before your socks. That's the whole idea.
Topological order is a way of arranging the nodes in a directed graph so every edge points in the same direction through the sequence: from earlier to later. If there's a directed edge from A to B, A appears before B. Every time.
Simple concept. Surprisingly many people blank on it mid-interview.
The Socks-and-Shoes Problem
Imagine getting dressed in the morning. Some steps have to happen before others:
- Underwear before pants
- Socks before shoes
- Shirt before jacket
Others are independent. You can put on your left shoe before your right, or your shirt before your underwear. The dependencies don't care. The algorithm doesn't care either.
Draw this as a directed graph. Each item of clothing is a node. Each "must come before" relationship is a directed edge. A valid topological order is any sequence that respects every edge.
The key insight: topological order is not unique. There are many valid sequences. All of them are correct, as long as no edge is violated.
A valid DAG on the left. The three-node cycle on the right has no valid ordering. A must come before B, B before C, and C before A. Good luck with that.
What the Definition Actually Says
Given a directed graph G = (V, E), a topological order is a linear sequence of all vertices such that for every directed edge (u, v), vertex u appears before vertex v in the sequence.
That's it. No tricks.
For the socks-and-shoes graph, both of these are valid orderings:
underwear → pants → socks → shoes → shirt → jacket
underwear → socks → shirt → pants → shoes → jacket
Both respect all the dependencies, and neither is more "correct" than the other. Multiple valid orderings are the norm, not an edge case.
Why Cycles Break Everything
Add one dependency that creates a cycle. Say a graph where A depends on B, B depends on C, and C depends on A.
Now try to build a valid sequence. A must come before B. B must come before C. C must come before A. But A can't come before B if A also has to come after C.
You've seen this before. You probably called it a circular import, a deadlock, or "that build system issue that cost me an afternoon." Same thing. Just a cycle.
There is no valid topological order for any graph that contains a cycle. The ordering exists if and only if the graph is a directed acyclic graph (a DAG). This is the core theorem behind every cycle-detection problem in interviews.
LeetCode 207, Course Schedule, is exactly this: given course prerequisites as a directed graph, determine if you can complete all courses. The answer is yes if and only if the graph is a DAG. Detecting a cycle is the same problem as determining whether a topological order exists.
How to Find a Topological Order
Two algorithms dominate interviews. Both run in O(V + E) time.
Kahn's Algorithm (BFS)
Count how many edges point into each node. This is the in-degree. Every node with in-degree 0 has no prerequisites, so it can go first.
from collections import deque def topological_sort(graph, num_nodes): in_degree = [0] * num_nodes for node in range(num_nodes): for neighbor in graph[node]: in_degree[neighbor] += 1 queue = deque([node for node in range(num_nodes) if in_degree[node] == 0]) order = [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return order if len(order) == num_nodes else [] # empty list = cycle detected
Each time you process a node, you decrement the in-degree of its neighbors. When a neighbor hits zero, it's ready. If you finish and the result is shorter than the total node count, a cycle exists. This is the whole cycle detection mechanism. One comparison at the end, zero extra bookkeeping.
DFS Postorder
Run a DFS. When you finish processing a node (all its descendants are done), prepend it to the result. Because you add nodes in reverse finish order, the sequence you get is a valid topological order.
def topological_sort_dfs(graph, num_nodes): visited = [False] * num_nodes in_stack = [False] * num_nodes # for cycle detection order = [] has_cycle = [False] def dfs(node): if has_cycle[0]: return in_stack[node] = True visited[node] = True for neighbor in graph[node]: if in_stack[neighbor]: has_cycle[0] = True return if not visited[neighbor]: dfs(neighbor) in_stack[node] = False order.append(node) for node in range(num_nodes): if not visited[node]: dfs(node) return [] if has_cycle[0] else order[::-1]
The in_stack array is what catches cycles. A back edge in a directed graph (an edge pointing to a node already on the current recursion stack) means you've found a cycle. Miss this flag and your DFS silently returns wrong answers on cyclic inputs.
Every interview candidate who forgets it gets the same wrong answer on the same test case. Don't be that candidate.
Unvisited, in-stack, and done. The back edge (gray to blue) is the cycle signal. Miss it and your algorithm happily produces garbage.
Both Algorithms Are O(V + E). Here's Why.
| Algorithm | Time | Space |
|---|---|---|
| Kahn's (BFS) | O(V + E) | O(V) |
| DFS postorder | O(V + E) | O(V) |
The O(V + E) time comes from visiting every vertex and every edge exactly once. The O(V) space comes from the queue or stack, the visited array, and for Kahn's, the in-degree array.
This is also optimal. You need to read every edge at least once to determine the ordering, so O(V + E) is the floor. There's no cleverer version hiding somewhere.
Where This Shows Up in Interviews
Topological order is the right tool when a problem involves:
- Dependencies between tasks (do X before Y)
- Prerequisites for items (take course A before B)
- Build order for components
- Determining if a configuration is even possible
Whenever the problem says "ordering" and gives you a directed graph or a list of (X must come before Y) constraints, think topological sort first.
Classic problems:
- Course Schedule (LeetCode 207): detect if a valid order exists (cycle detection)
- Course Schedule II (LeetCode 210): return the actual ordering
- Alien Dictionary (LeetCode 269): infer character order from sorted word list, then topological sort
- Find All Possible Recipes (LeetCode 2115): ingredients as dependencies
A common mistake: candidates reach for DFS without tracking the "currently in stack" set and miss the cycle detection. The in_stack array (or coloring nodes white/gray/black) is what separates a correct DFS-based topological sort from one that silently returns wrong answers on cyclic inputs.
Practice your topological sort answers out loud before the interview. Knowing the algorithm is the easy part. Explaining why in_stack[node] = False has to happen after the loop, not before it, is where candidates lose points. SpaceComplexity runs voice-based mock interviews with rubric feedback that will catch exactly these gaps before a real interviewer does.
Three Questions to Ask When You See a Graph Problem
- Is the graph directed? Topological order only applies to directed graphs. Undirected graphs have no defined "flow" direction.
- Could it have cycles? If yes, you need cycle detection. A cycle means no valid topological order exists.
- Do I need the actual sequence, or just whether one exists? LeetCode 207 needs only yes/no. LeetCode 210 needs the actual order. Kahn's gives you both naturally.
Answering these three questions before you write a line of code is usually enough to pick the right approach.
For a deeper look at both algorithms with complexity proofs, see Topological Sort Algorithm. For the interview-specific patterns and common bugs, What Is Topological Sort covers the four failure modes in detail. If you're deciding between topological sort and plain DFS, Topological Sort vs DFS draws the line clearly. Since topological order only exists on DAGs, What Is a Directed Acyclic Graph fills in the underlying concept.