Topological Sort

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A topological order lists every vertex so all arrows point forward. It exists exactly when the directed graph has no cycle (a DAG).

   #1
2. ↯use it when

   "Prerequisites", "depends on", "build order", "is it possible to finish?" — or an order hidden in sorted examples (alien dictionary).

   #2
3. { }template

   Kahn: count in-degrees → queue every 0 → poll, output, decrement neighbours, queue new 0s. Output count < V ⇒ cycle.

   #3
4. O( )cost

   Kahn and DFS: O(V + E) time and space. Smallest order with a PriorityQueue: O(V log V + E). Longest path on a DAG: O(V + E).

   #4
5. !trap

   [course, pre] means the arrow goes pre → course. Draw one edge on paper before you code.

   #5
6. !trap

   Directed cycle check needs three colours. A plain visited[] calls a harmless diamond a cycle.

   #6
7. !trap

   DFS gives the finish order reversed — pop the stack. Kahn's order is already correct; don't reverse it.

   #7
8. ✦pro tip

   Default to Kahn in Java: no recursion depth limit, a one-line cycle check, and it upgrades to min-heap order and DP.

   #8
9. ✦pro tip

   Process vertices in topological order and DP gets easy: critical path, earliest finish, counting paths.

   #9

Shaky on a card? Open the chapter or flip its recall cards.