Topological Sort
Order the nodes of a graph so every task comes after everything it depends on, used for scheduling and build order.
Topological Sort Practice Problems
Easy
1 problemsMedium
5 problems- 94medium
Course Schedule
Check whether it is possible to finish every course given their prerequisites.
- 95medium
Course Schedule II
Find a valid order to take every course given their prerequisites.
- 96medium
Minimum Height Trees
Find the roots that produce the shortest possible trees from a given set of connected nodes.
- 251medium
Build Order
Find a valid compile order for a list of projects given their pairwise dependencies.
- 252medium
Find Eventual Safe States
Find every node whose paths always dead-end instead of looping forever.
Hard
2 problemsRelated concepts
| Topic | Description |
|---|---|
| Depth-First Search | Explore as far as possible down one path before backtracking, used to walk trees, graphs, and grids. |
| Breadth-First Search | Explore level by level from a starting point, the go-to way to find the shortest path in an unweighted graph. |
| Dijkstra's Algorithm | Find the shortest path from a starting node to every other node in a graph where edges have non-negative weights. |
| Bellman-Ford Algorithm | Find the shortest path from a starting node even when some edges have negative weights, and detect negative cycles. |
| Union-Find (Disjoint Set) | Track which nodes belong to the same group and merge groups quickly, used to detect cycles and build networks. |
| Kruskal's Algorithm | Build the cheapest network connecting all nodes by adding the smallest edges first, skipping any that form a cycle. |