Graph Algorithms the Fun Way

9 TOPOLOGICAL SORT

In addition to their physical corollaries, such as one-way streets, we can use directed edges in a graph to specify a dependency or ordering between nodes. Incoming edges to a node represent links from actions that must be completed before reaching the current node. Meanwhile, outgoing edges point to actions enabled by the completion of the current node.

Consider the example of a recipe for chocolate chip cookies. Each node represents a step in the recipe, including instructions such as “Add the flour” and “Stir the mixture.” Some of the steps have a clear and non-negotiable ordering. We wouldn’t want to stir the mixture ...