Topological Sort

Implement topologicalSort(graph) — given a directed acyclic graph (a DAG), return an ordering of its nodes such that every edge points forward: if there is an edge u → v, then u appears before v in the result. This is the ordering behind build systems (compile a module before the modules that import it), course planning (take the prerequisite before the class), and task schedulers (run a job only after its dependencies finish). When the dependency graph contains a cycle — A needs B, B needs A — no such ordering exists, and the function must say so.

Signature

// graph: Record<string, string[]>
//   Adjacency list. Each KEY is a node. Each VALUE is the list of nodes
//   that node points TO (its successors / the things that depend on it).
//   An edge u → v means 'u must come before v' in the output.
// returns: string[]
//   A valid topological ordering of every node in the graph.
// throws: Error if the graph contains a cycle (no valid ordering exists).
function topologicalSort(graph: Record<string, string[]>): string[];

A node with no outgoing edges still appears in the output — it just has an empty array as its value (e.g. d: []).

Examples

// Linear chain: a → b → c → d. Exactly one valid order.
topologicalSort({ a: ['b'], b: ['c'], c: ['d'], d: [] });
// → ['a', 'b', 'c', 'd']

// Diamond: a points to b and c, both point to d.
topologicalSort({ a: ['b', 'c'], b: ['d'], c: ['d'], d: [] });
// → ['a', 'b', 'c', 'd']  OR  ['a', 'c', 'b', 'd']
// Both are valid: b and c can come in either order, but a is always
// first and d is always last. MULTIPLE valid orderings can exist.

// Cycle: a → b → a. No ordering can put both before each other.
topologicalSort({ a: ['b'], b: ['a'] });
// → throws Error('cycle detected')

Notes

• The output is not unique. Whenever two nodes have no path between them, either order is valid. Don't test for one exact array unless the graph is a strict chain — test the invariant that every edge u → v has u before v.
• Every node appears exactly once. The result length equals the number of keys in graph, with no duplicates and no omissions.
• Disconnected nodes are still nodes. A graph can have several unrelated clusters, or lone nodes with no edges at all. All of them must appear in the output.
• A self-loop is a cycle. An edge a → a makes a depend on itself; that has no valid ordering, so throw.
• Assume every successor is also a key. If a: ['b'] appears, then b is a key in graph too (possibly with an empty array). You don't need to defend against successors that were never declared as keys.
• Don't worry about weighted edges, undirected graphs, or returning the cycle itself — throwing a plain Error on a cycle is enough.