Topological Sort
Topological sort orders the nodes of a DAG so that for every directed edge u→v, node u appears before v in the ordering.
Topological sort = getting dressed in the right order. Underwear before pants, socks before shoes. You can't put on a shirt after the jacket. Dependencies dictate the sequence.
Two algorithms: (1) Kahn's algorithm (BFS-based): start with all nodes with in-degree 0, process them, decrement in-degrees of neighbors, add new zero-in-degree nodes to queue. (2) DFS-based: do DFS, add each node to front of result after all its descendants are visited. If a cycle exists, Kahn's detects it (result has fewer than n nodes). Use cases: build systems, course prerequisites, task scheduling, package dependency resolution.
Kahn's algorithm gives a unique topological sort iff there is always exactly one node with in-degree 0 at each step (the DAG is a path). Otherwise, multiple valid orderings exist and Kahn's gives one of them depending on queue ordering. Cycle detection: in Kahn's, if the processed count < n, a cycle exists. In DFS, a 'gray' (in-progress) node being visited again indicates a cycle — 'white' = unvisited, 'gray' = in current DFS path, 'black' = done. For all valid topological sorts, use backtracking — exponential in worst case but shows the algorithmic structure.
When I see 'dependency ordering' or 'prerequisites', I think topological sort. I prefer Kahn's algorithm for interviews because cycle detection is explicit and the code is straightforward: build the in-degree map, push all zero-in-degree nodes to a queue, process BFS-style. I verify correctness by checking if result length equals the number of nodes — if not, a cycle exists. For DFS-based topo sort, I add nodes to a stack after completing their DFS, then reverse the stack.
Topological sort only works on a DAG (directed acyclic graph). If the problem doesn't explicitly say 'no cycles', check for them. Also: the order of equal-priority nodes is not unique — if the problem needs lexicographically smallest order, use a min-heap instead of a plain queue in Kahn's algorithm.