← Back to problems Related: LC 210 (order) → Course Schedule I →

Topological Sort (Kahn)

Directed graph • Indegree • BFS layer • len(order) < n ⇒ cycle

adj[u] lists vertices v with a directed edge u → v (finish u before v). Count indegrees, enqueue all zeros, repeatedly pop, append to order, relax outgoing edges. Same logic as vector<int> topoSort(int n, const vector<vector<int>>& adj) in C++.

TimeO(V+E)

SpaceO(V)

Step0/0

Indegree Ready queue Output order

Speed:

Ready

Example: n = 4, edges 0→1, 0→2, 1→3, 2→3. Press Step to walk Kahn’s algorithm.

⌨ Type It

Python: def topo_sort(n, adj) — adj is length n; adj[u] is a list of v for edges u → v. Return a list of vertices in topological order. Use a FIFO queue (e.g. collections.deque). If a directed cycle exists, the returned list has length < n (some vertices never become indegree 0).

═══ KAHN TOPO ═══

① indeg[v]++ for every edge u → v

② Queue all i with indeg[i] == 0

③ Pop u, append u, indeg[v]--; enqueue v when indeg[v]==0

④ return order # len < n ⇒ cycle