Topological Sort
Quick reference
| DFS-based topological sort | O(V + E) |
| Kahn's algorithm | O(V + E) |
To get dressed has rules, but not a full order. Socks come before shoes. Underwear comes before pants. But underwear and socks can go on in either order. Nothing forces one before the other. A topological sort is exactly this: an arrangement of items where every dependency comes before the thing that depends on it. Anything with no relationship to each other can go in any order. More than one correct arrangement can exist at the same time.
Only one shape of graph can be arranged this way at all: directed, and with no cycle. This is a DAG, short for "directed acyclic graph". It must be directed, because "before" makes sense only if edges have a direction. An edge from socks to shoes means socks-before-shoes, not the reverse. It must be acyclic, because a cycle breaks the whole premise. If A must come before B, B before C, and C before A, there is no start point. Every candidate for "first" has something behind it that demands to go earlier. No valid order exists, and you must detect this, not ignore it.
Two ways to the same order
structure Graph (adjacency list, directed):
adj: map from node -> list of the nodes it points TO (its dependents)
structure InDegree:
inDegree: map from node -> count of edges that point INTO it
// A node with inDegree 0 has nothing left that it waits on.DFS-based — finish a node, then push it; reverse at the end
function topoSortDFS(nodes, adj):
visited = {}
stack = [] // built in FINISH order, not visit order
function dfs(node):
if node in visited:
return
visited.add(node)
for neighbor in adj[node]:
dfs(neighbor)
stack.push(node) // every dependent is already pushed: node is done
for node in nodes:
dfs(node)
return reverse(stack)Kahn's algorithm — BFS-based, using in-degree
function topoSortKahn(nodes, adj):
inDegree = {node: 0 for node in nodes}
for node in nodes:
for neighbor in adj[node]:
inDegree[neighbor] += 1
queue = Queue()
for node in nodes:
if inDegree[node] == 0: // nothing left that it waits on: safe to start
enqueue(queue, node)
result = []
while queue is not empty:
node = dequeue(queue)
result.append(node)
for neighbor in adj[node]:
inDegree[neighbor] -= 1 // node is done: one less thing that neighbor waits on
if inDegree[neighbor] == 0:
enqueue(queue, neighbor)
return resultBoth approaches are a structured single pass over the graph, with no extra search and no revisit. Kahn's builds and drains an in-degree map one time. The DFS version runs one DFS over every node one time. Neither does more work than a plain traversal already would.
| Operation | Time | Space | Why |
|---|---|---|---|
| DFS-based topological sort | O(V + E) | O(V) | This is the standard DFS traversal cost, plus a stack that holds each node exactly one time. No node is pushed two times. |
| Kahn's algorithm | O(V + E) | O(V) | To build the in-degree counts is O(V + E). Every node enters and leaves the queue exactly one time. Every edge is examined exactly one time to decrement a count. |
Running it on a graph that actually has a cycle
The DFS version still produces some order with no crash. The order is just not valid, because no valid order exists. Kahn's algorithm gives a cleaner signal. If a cycle exists, every node inside that cycle waits forever on another node in the same cycle. So its in-degree never reaches zero and it is never enqueued. result ends up shorter than nodes. A check of len(result) == len(nodes) at the end, not only a return of result, is what turns "silently wrong" into "correctly reports impossible".
Applying this to an undirected graph
"Before" has no meaning without direction. An undirected edge between A and B says that they are connected, not that one comes first. In-degree is not even well-defined on an undirected graph the way that Kahn's algorithm needs it. If a problem gives you undirected edges and asks for an ordering, something earlier is wrong with the setup, not the algorithm.
Assuming there's exactly one valid order
Socks-then-pants-then-shoes and pants-then-socks-then-shoes are both valid if nothing constrains socks relative to pants directly. When Kahn's queue holds more than one node at once, either one can go next. The choice changes the final order without a mistake. A checker for this kind of problem must verify the ordering property (every edge points from earlier to later in the result), not compare against one fixed expected sequence.
Forgetting the DFS version's final reverse
The stack in topoSortDFS() is built in finish order. A node is pushed only after everything that it points to has already finished and been pushed. So the dependents end up below their dependencies on the stack, not above. The raw stack reads dependents-first. It looks like a real ordering (it has the right nodes, but it runs backward), so it is an easy bug to miss until you check it against an actual dependency edge.
Sign in to mark problems done — progress syncs across devices.