Graphs (Topological Sort)
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.
Interactive problems
Free to open
How do you 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.
What is the time complexity of the graphs (topological sort) pattern?
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++.
Graphs (Topological Sort) problems by difficulty and complexity
The difficulty, running time and extra space of every graphs (topological sort) solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Ordering Dependencies (Topological Sort) | Medium | Ω(V + E) | Θ(V + E) | O(V + E) | O(V + E) |
| Course Schedule | Medium | Ω(V + E) | Θ(V + E) | O(V + E) | O(V + E) |
| Course Schedule II | Medium | Ω(V + E) | Θ(V + E) | O(V + E) | O(V + E) |
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 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree