Topological Sort — ordering DAGs
Topological Sort
A topological sort of a DAG is a linear ordering of its nodes such that every edge u -> v places u before v. Build systems, package managers, and course planners all rely on it.
Two conditions matter: the graph must be directed and acyclic. A cycle means at least two nodes each demand to come before the other.
Kahn's algorithm (BFS-based)
Compute the in-degree of every node. Start with every zero-in-degree node in a queue. Pop, emit, decrement in-degree of neighbours. When neighbour hits zero, enqueue.
If emitted order has fewer nodes than the graph, the leftover nodes form a cycle. Kahn's is my default because the cycle check is free.
DFS-based toposort
Run DFS, push each node onto output when its recursion completes (post-order). Reverse at the end. A node finishes only after all its descendants finish.
Use the three-colour scheme to catch cycles: hitting a GRAY neighbour = back-edge = cycle.
Ties are not unique
Any zero-in-degree node is a valid next pick. Two toposorts on the same DAG can differ. For deterministic output, use a heapq in Kahn's (lexicographic toposort).
Common bugs to avoid
- Mutating the original in-degree map — copy it.
- Skipping isolated nodes — seed queue from every zero-in-degree node.
- Undirected input — meaningless. Reject.
Try it
- Add a cycle (e.g.
(5, 3)) and confirm Kahn's raises. - Modify Kahn's to use a
heapqso ties break by smallest id.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Write
compute_in_degree(n, edges)that returns a list where index i holds the in-degree of node i. Nodes are labeled 0..n-1 and each edge is a pair [u, v] meaning u must come before v. - Exercise 2
Implement
course_order(num_courses, prereqs)using Kahn's algorithm. Each prereq [a, b] means you must take b before a. Return any valid ordering as a list, or an empty list if it's impossible. - Exercise 3
Write
has_cycle(n, edges)that returns True if the directed graph contains a cycle, False otherwise. Use the fact that Kahn's algorithm processes fewer than n nodes when a cycle exists.