# Topological Sort - A linear ordering, such that if $(u, v) \in G$, $u$ appears before $v$. Defined on a dag. - Running topological sort also yields a Hamiltonian circuit, as each vertex is traversed only once. ## Solution - One approach - Perform [[dfs|DFS]] to compute finish times. - As each vertex is finished, insert it onto the front of a [[linked-list]] - Return the linked list of vertices - Another approach -- [[kahn|Kahn's Algorithm]] - $\Theta(V + E)$ time