31. What is a topological sort and when does one exist?
MediumGraph algorithms
Technical
Show model answer
A topological order lists the vertices of a directed graph so every edge goes from earlier to later. It exists exactly when the graph has no directed cycle (it is a DAG). Compute it with Kahn's algorithm (repeatedly remove vertices with in-degree 0) or with DFS (reverse post-order). Uses: build systems, course prerequisites and task scheduling.