Topological Sort
Medium+90 XPOrder tasks so every prerequisite comes before the task that needs it — using DFS on a directed graph.
No visualization loaded.
Watch
—
Press Run to begin.
Imagine a list of courses where some can't be taken until you've finished others first — you need Algebra before Calculus, and so on. A topological sort lines them ALL up in one row so that every course appears after the courses it depends on. We draw the rules as arrows: an arrow from A to B means 'A must come before B'. Surprisingly, plain DFS hands us a valid order almost for free.
▸What is a 'topological order'?
It's a single line-up of all the nodes such that for every arrow A → B, A sits somewhere to the LEFT of B. If A must come before B, then in the final row A really does come before B — for EVERY arrow at once. There can be more than one valid order; we just need one that breaks no rule.
▸What's a DAG, and why must it have no cycles?
DAG = Directed Acyclic Graph: arrows have a direction, and there are NO cycles (you can't follow arrows in a loop back to where you started). Cycles are the deal-breaker: if A must come before B AND B must come before A, no line-up can satisfy both — it's like needing to take the class before its own prerequisite. So a topological order exists exactly when the graph is acyclic.
▸How does DFS magically give an order?
Run DFS from a node, but DON'T record it right away. First go explore everything it points to (everything that depends on it). Only when ALL of those are completely finished do you add the node — to the FRONT of the list. Because a node is placed only after everything downstream of it, it always lands before them in the final row. Do that for every node and the front-to-back list is a valid topological order.
▸Where is topological sort actually used?
Anywhere things have a 'do this before that' relationship. Build systems compile files in dependency order. Spreadsheets recompute cells in the order their formulas reference each other. Course schedulers respect prerequisites. Package managers install dependencies before the packages that need them. Task runners decide a legal order for jobs that depend on other jobs.
How the work grows
O(V + E) is fair — grows in step with the data. DFS touches each node once and walks each arrow once, so the work grows in a straight line with the size of the graph (V nodes + E edges). The extra memory holds the visited set, the order being built, and the recursion stack.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.