Topological sort

Topological sort orders a directed acyclic graph so every dependency appears before the node that needs it. Kahn algorithm repeatedly removes zero-indegree nodes; DFS can produce reverse finishing order. It is common in course scheduling, build systems, migration ordering, and task planning.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers expect you to detect cycles: if not all nodes are emitted, no valid topological order exists.

Common pitfalls: Topological sort only applies to directed acyclic graphs. Be careful about edge direction, because reversing prerequisite edges changes indegree meanings.

Checklist:

• Build directed edges.
• Track indegrees or DFS colors.
• Emit all nodes.
• Report cycles clearly.