Ordering Dependencies (Topological Sort)
Learn how to order tasks with dependencies using Topological Sort and detect cycles.
What is Topological Sort?
Given a Directed Acyclic Graph (DAG), a Topological Sort is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before vertex v.
It is the standard algorithm for resolving dependencies (e.g., compiling code, scheduling tasks, course prerequisites).
The Motivation: Course Schedule
You need to take N courses. Some courses have prerequisites.
- Physics II requires Physics I.
- Calc III requires Calc II requires Calc I.
Goal: Find a valid order to take ALL courses. If impossible (due to a cycle), tell us.
The Cycle Problem
What if you have a cycle?
- Course A requires Course B.
- Course B requires Course A.
You can never start! This is a Circular Dependency. A Topological Sort is ONLY possible if the graph has NO Cycles (DAG).
Visualizing a Cycle
Visualization coming soon...
Initializing...
Watch how a simple traversal gets stuck in an infinite loop (recursion stack) when a cycle exists.
When to use Topological Sort?
Pattern Recognition Triggers:
- Dependencies: Keywords like "prerequisites", "build order", "depends on".
- Linear Ordering: You need to arrange items in a sequence respecting constraints.
- Directed Graph: The relationships are one-way.
The Intuition: Find the Start
To start, we must find a node that has NO prerequisites (Indegree = 0).
- Pick a node with
Indegree == 0. Add it to our sorted list. - "Remove" it from the graph.
- When removed, its neighbors' indegrees decrease.
- Repeat until all nodes are picked.
This is Kahn's Algorithm.
Interactive Walkthrough (Kahn's Algo)
Visualization coming soon...
Initializing...
Watch how we peel off nodes with 0 dependencies layer by layer.
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.