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 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’s Algorithm
• $\Theta (V+E)$ time