# 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 post-order depth-first search.

We record the DFS postorder from every vertex with in-degree zero (i.e. has no incoming edges). If we reverse the post-order traversal, we will get the topological sort. It is indeed somewhat miraculous and amazing!