Topological sort

In short: A topological sort arranges the nodes of a directed acyclic graph so that every node comes before all nodes it points to.

In more detail: It answers “In what order must I do tasks if some must be finished before others?”. If a cycle exists, no valid order exists.

In Depth

• Kahn’s algorithm: Repeatedly take nodes without incoming edges and remove their outgoing edges.
• DFS variant: Depth-first search, push a node on a stack after fully visiting all successors, reverse at the end.
• Cycle detection: If nodes remain, there is a cycle (for example a circular dependency).
• Use: Build systems, package managers (dependencies), course planning, spreadsheet recalculation.
• Runtime: O(nodes + edges).

See also: Graph (data structure)