Graph AlgosAlgorithmaka topological ordering, linear ordering of a DAG, dependency ordering

Topological Sort

Order the vertices of a directed acyclic graph so that every edge points forward; exists iff the graph has no cycle.

▶ VisualizePattern: Breadth-First SearchPractice (2)
Progress

Overview

A topological order of a directed graph is a sequence of all vertices such that for every edge u → v, u appears before v. It is the formal version of "do the prerequisites first". A graph has a topological order if and only if it is a DAG (Directed Acyclic Graph) — a single directed cycle makes the requirement impossible, since some vertex on the cycle would have to precede itself.

Two linear-time algorithms produce it. Kahn's Algorithm repeatedly removes vertices with in-degree zero (a BFS-flavoured, queue-based approach that also detects cycles by counting how many vertices were output). DFS Topological Sort runs a DFS and reverses the finish order (post-order), detecting cycles with a "currently on the recursion path" marker.

A DAG can have many valid orders; which one you get depends on tie-breaking. When the problem asks for the lexicographically smallest order, Kahn's with a min-heap instead of a queue does it in O((V + E) log V).

DAGdirectedorderingdependenciescycle detectionO(V + E)

Intuition

A mental model before the formal terms.

Picture a university course catalogue: each arrow says "take this before that". Laying the courses out on a single timeline so that every arrow points right is a topological order. If some chain of prerequisites loops back on itself, no timeline exists — you can never take the first course.

Two ways to build the timeline: (1) keep taking any course with no outstanding prerequisites and cross it off, which is Kahn's algorithm; (2) pick a course, chase its prerequisites all the way down, and write each course down only after everything it depends on is written — that is DFS post-order. Read in reverse, the post-order lists dependencies first.

How it works

  1. Kahn: compute indeg[v] for every vertex. Put all vertices with indeg == 0 in a queue. Pop u, append it to the order, and decrement indeg[v] for every edge u → v; any v that reaches zero joins the queue. If fewer than n vertices were output, the leftover vertices form (or feed into) a cycle.
  2. DFS: colour every vertex white. For each white vertex run DFS: mark grey on entry, recurse into white neighbours, and treat a grey neighbour as a cycle. On exit mark black and push the vertex to a list. The reverse of that list is a topological order.
  3. Both are O(V + E). Kahn is iterative by nature and gives "levels" (all vertices with no remaining prerequisites can run in parallel); DFS is a few lines shorter and produces the order that DP on DAGs / longest-path computations usually want.

Why it works

Existence: a DAG always has a vertex with in-degree 0 (walk backwards along edges; since there is no cycle the walk must stop within n steps, at a source). Removing it leaves a smaller DAG, so induction builds the whole order. Conversely a cycle has no valid position for its first vertex.

Kahn outputs a vertex only after all its predecessors have been output (its in-degree only hits zero then), so every edge points forward.

DFS: when u finishes, every vertex reachable from u has already finished (either it was explored inside u's call or had finished before — a grey one would signal a cycle). So u finishes after all its successors; reversing finish order puts u before them.

Recognition

How to tell a problem wants this.

  • Words like "prerequisite", "dependency", "must happen before", "build order", "task scheduling with constraints".
  • The input is a set of ordering constraints and the question is whether they are consistent (cycle check) or asks for *any* consistent sequence.
  • You need to compute a DP over a DAG (longest path, number of paths, earliest start time) — evaluate in topological order.
  • Implicit orderings: characters derived from sorted words (alien dictionary), version numbers, compile units.
“minimum steps” → Breadth-First Search“connected groups” → Depth-First Search“prerequisites” → Topological Sort

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Kahn's Algorithm visualization.

shirt0tie1jacket2pants0belt2shoes2socks0
Queue
shirtpantssocks
Topological order
empty
1/16Count incoming edges. Nodes with in-degree 0 have no prerequisites, so they can go first: shirt, pants, socks.
Current node (label = in-degree)In queue (in-degree 0)EmittedEdge being removedStuck in a cycle
PseudocodeLearn Kahn's Algorithm →
1indeg[v] = number of incoming edges
2queue = [v for v in nodes if indeg[v] == 0]
3while queue not empty:
4  u = queue.popleft(); order.append(u)
5  for v in neighbors(u):
6    indeg[v] -= 1
7    if indeg[v] == 0: queue.append(v)
8if len(order) < n: cycle detected
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed

Pseudocode

1indeg[v] = number of incoming edges for each v
2queue = all v with indeg[v] == 0
3order = []
4while queue not empty:
5  u = queue.pop(); order.append(u)
6  for v in adj[u]:
7    indeg[v] -= 1
8    if indeg[v] == 0: queue.push(v)
9if len(order) < n: cycle -> no topological order
10return order

Implementations

1from collections import deque
2 
3 
4def topological_sort(n: int, edges: list[list[int]]) -> list[int] | None:
5    """Umbrella topic: Kahn's algorithm is the representative implementation.
6    edges are [u, v] meaning u must come before v.
7    Returns an order, or None when the graph contains a cycle."""
81 · Build adjacency list and in-degrees
9    adj: list[list[int]] = [[] for _ in range(n)]
10    indeg = [0] * n
11    for u, v in edges:
12        adj[u].append(v)
13        indeg[v] += 1
14 
152 · Seed the queue with every in-degree-0 vertex
16    queue = deque(v for v in range(n) if indeg[v] == 0)
17 
183 · Emit from the queue, decrement neighbours
19    order: list[int] = []
20    while queue:
21        u = queue.popleft()
22        order.append(u)
23        for v in adj[u]:
24            indeg[v] -= 1
25            if indeg[v] == 0:
26                queue.append(v)
27 
284 · Every vertex emitted iff the graph is acyclic
29    return order if len(order) == n else None
Walkthrough
  1. Topological sort is the umbrella topic; Kahn's BFS peeling is implemented as the representative — the DFS variant lives under dfs-topological-sort.
  2. The build loop unpacks each [u, v] pair and counts in-degrees.
  3. deque(v for v in range(n) if indeg[v] == 0) seeds the queue from a generator in one line.
  4. popleft() is O(1); each neighbour's in-degree drops by one and the vertex enqueues at zero.
  5. len(order) == n is the cycle test — cycle vertices never reach in-degree 0 and are never emitted.
Complexity (this implementation)
time O(V + E) · space O(V + E)
Language notes
  • collections.deque gives O(1) popleft; list.pop(0) is O(n) and the classic Kahn performance bug.
  • list[int] | None (PEP 604) is the modern optional-return annotation.
  • The stdlib offers graphlib.TopologicalSorter (Python 3.9+), which raises CycleError on cycles — worth knowing, though interviews expect the manual version.
Common mistakes in this language
  • Using list.pop(0) as the dequeue — O(n) per operation.
  • Returning [] instead of None on a cycle, which is indistinguishable from sorting an empty graph.
  • Iterating edges as for u, v in edges when edges may contain weights — unpacking then raises ValueError.
Language differences that matter here
  • Queue choice: C++ std::queue, Python collections.deque, JS/TS have no O(1) stdlib queue and use an array with a moving head pointer.
  • Failure signalling: C++ std::optional + nullopt, JS/TS null in a union type, Python None — all chosen over "empty list", which is ambiguous for n = 0.
  • Python ships graphlib.TopologicalSorter in the stdlib; the other three languages have no built-in topological sort.

Complexity

Best
O(V + E)
Average
O(V + E)
Worst
O(V + E)
Space
O(V)

Lexicographically smallest order via min-heap: O((V + E) log V).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Scheduling with precedence constraints: build systems, course prerequisites, task pipelines, package installation.
  • Checking whether a set of ordering constraints is consistent (no cycle).
  • DP on a DAG (longest path, counting paths, critical path) — process vertices in topological order so every predecessor is finalised first.
Avoid it when
  • The graph may contain cycles and you still need an order of *something* — condense with Strongly Connected Components first, then topologically sort the condensation.
  • Undirected graphs — there is no direction to respect; "ordering" questions there are usually about BFS layers or trees.
  • Weighted shortest paths on a general graph — that is Dijkstra's Algorithm / Bellman-Ford, although on a DAG topological order gives shortest *and* longest paths in O(V + E).

Alternatives

Kahn's AlgorithmDFS Topological SortStrongly Connected Components

Common mistakes

  • Building edges in the wrong direction (prerequisite → course vs course → prerequisite) and reversing the meaning of the output.
  • Forgetting that vertices with no edges at all still belong in the order (initialise the queue with all zero in-degree vertices).
  • Returning a partial order when a cycle exists instead of reporting failure — always compare len(order) with n.
  • Expecting a unique answer; tests usually accept any valid order, but lexicographic-smallest variants require a heap.

Interview patterns

  • Course Schedule I/II: can all courses be finished (cycle check) and in what order.
  • Alien Dictionary: derive character constraints from adjacent words, then topologically sort the characters.
  • Longest path / minimum time to finish all tasks in a DAG with durations: DP over topological order.
  • Parallel scheduling: Kahn's "levels" give the minimum number of rounds.
Interview questions on this
Mock interviews

Example problems

Course SchedulemediumAlien Dictionaryhard