Topological Sort

A topological sort puts the vertices of a directed graph in a line so that every edge points forwards, and the topic teaches two ways to find one. It opens on the order itself and on in-degrees, the count of what each task waits on. Kahn's algorithm follows as a trace, outputting each vertex once nothing it waits on is left, and a gotcha shows that a stack in place of the queue gives a different order that is just as correct. A code card writes Kahn's algorithm in Python, Java and TypeScript, and a concept card explains why a short output means a cycle. Depth-first search gives the second method, its finishing order reversed. An exercise schedules the jobs of a kitchen refit, and a recap compares the two methods.