Topological Sort

Line up the nodes of a DAG so every “must come before” arrow points forward.

Definitions

• Graph: nodes connected by edges. Directed means each edge is an arrow; A to B reads “A must come before B”.
• Cycle: follow arrows back to the start; no valid order exists (a node would precede itself).
• DAG: Directed Acyclic Graph. Topological sort works only on a DAG.
• Topological order: a single ordering respecting all precedence rules. Usually more than one is valid.

In-degree (the key idea)

• In-degree of a node = number of arrows pointing into it = number of prerequisites.
• In-degree 0 means no prerequisites, so it is safe to place next.
• Placing a node removes its outgoing arrows, lowering neighbors’ in-degrees; any that hit 0 become free.

Kahn’s algorithm (in-degree + queue)

1. Compute every node’s in-degree.
2. Enqueue all nodes with in-degree 0.
3. Loop: dequeue a node, append to output; for each neighbor subtract 1, enqueue it if it hits 0.
4. Stop when the queue is empty.

degree-0 node --> output
       |
       v  (remove its arrows)
neighbor degree -1  --> if 0, enqueue

• Use collections.deque with popleft() (O(1) front removal).
• Cycle detection is free: cycle nodes never reach in-degree 0, so they never enqueue. Final check: len(order) == len(graph); if shorter, a cycle exists, return None.

DFS approach (second method)

• Recursively visit all descendants of a node, then append the node; reverse the list at the end.
• Returns a valid order that may differ from Kahn’s; both are correct.
• Plain DFS does not detect cycles (needs a third “on active path” state). Recursion can hit Python’s depth limit. Kahn’s is the common first choice.

Complexity

• Time: O(V + E) — each node enqueued/dequeued once, each edge examined once.
• Space: O(V + E) — in-degree map + queue + graph edges. Optimal; you must read every node and edge at least once.

Gotchas

• Cycle means no valid order; always keep the len(order) == len(graph) check.
• Multiple valid orders exist; don’t assert one exact list unless you fix a tie-break (e.g. always take the alphabetically smallest).
• Every neighbor must also be a key in the graph dict, even with value [], or the node is missed.
• Never use a list with pop(0) as the queue — O(V) each, making the whole run O(V^2).