Topological Sort
Learn how to linearly order vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u comes before v.
Ready to start
Queue (0 In-Degree)
Sorted Order
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Imagine you are getting dressed. You must put on socks before shoes, and underwear before pants.
You can't put on shoes first, then socks. Some tasks have dependencies.
Topological Sort gives you a valid order to perform tasks so that all dependencies are met.
Concept
Topological Sorting for a Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.
It is only possible if the graph has no cycles (DAG).
How it Works
- Calculate in-degree (number of incoming edges) for each node.
- Add nodes with 0 in-degree to a Queue.
- Process Queue: remove node
u, add to result. - Decrease in-degree of neighbors. If a neighbor becomes 0, add to Queue.
- Repeat until Queue is empty.
Step-by-Step Breakdown
Watch the visualization:
- Primary Nodes: Processing or in Queue.
- Emerald Nodes: Added to the sorted order.
- In-Degrees: Shown next to nodes or in a table.
When to Use
Use Topological Sort when:
- Scheduling tasks with dependencies (e.g., project management, build systems).
- Resolving symbol dependencies in linkers.
- Course prerequisite planning.
- Finding a cycle in a graph (if sort fails).
When NOT to Use
- Cyclic Graphs: It's impossible to topologically sort a graph with a cycle.
- Undirected Graphs: Only applies to directed graphs.
How to Identify
Problems about "ordering tasks", "prerequisites", "dependencies", or "build order" typically require Topological Sort.
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.