The Graphs (Topological Sort) Pattern
Topological sort orders the nodes of a directed acyclic graph so every edge points forward. It is produced either by repeatedly removing nodes with no remaining prerequisites (Kahn’s algorithm) or by reversing a DFS finish order.
3
Interactive problems1
Free to openHow to recognise a graphs (topological sort) problem
Tasks have prerequisites and you need a valid order, or you need to detect whether the dependencies contain a cycle. Course schedules, build orders and dependency resolution are all this.
Time and space complexity
O(V + E). If the algorithm finishes having emitted fewer than V nodes, the graph contains a cycle — which is how cycle detection falls out for free.
Graphs (Topological Sort) practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Related patterns and concepts
The underlying technique is covered from first principles in the graphs (topological sort) lesson in the DSA visualizer curriculum. Graphs (Topological Sort) is one of the 16 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.