Topological Sort

A topological sort of a dag (directed acyclic graph) $G = (V, E)$ is a linear ordering of all its vertices such that $if$ G contains an edge $(v, w)$, then $v$ appears before $w$ in the ordering. In other words, it is the ordering of the vertices that respects the direction of the edges. (If the graph contains a cycle, then no linear ordering is possible.)

For example, we can imagine using topological sort to plan a course schedule. (Although it would be difficult to graduate on time if we could only take one class at a time.)

The algorithm is quite simple and uses postorder depthfirst search.
We record the DFS postorder from every vertex with indegree zero (i.e. has no incoming edges). If we reverse the postorder traversal, we will get the topological sort. It is indeed somewhat miraculous and amazing!