Command Palette

Search for a command to run...

Hectal

Module 24

Topological Sort

Order tasks so every dependency comes first: Kahn's algorithm, DFS finishing order, levels, unique orders, and DP over a DAG.

Intermediate 3 lessons 7 problems ~35 min of lessons
Topological Sort

A topological order lists the nodes of a directed graph so that every edge goes from earlier to later: every prerequisite before the course that needs it, every build step before the step that uses its output. It exists exactly when the graph has no cycle (a DAG).

This module teaches the two standard algorithms, Kahn's in-degree queue and reversed DFS finishing order. It then puts them to work: counting semesters (levels), checking whether the order is unique, recovering an unknown alphabet, and computing longest paths and earliest finish times with DP in topological order.

Best after: Cycle Detection, Breadth-First Search

Part 1

Learn the ideas

  1. 24.1Kahn's AlgorithmRepeatedly take a node with no remaining prerequisites (in-degree 0), output it, and remove its outgoing edges. If nodes remain stuck, there's a cycle.14 min
  2. 24.2DFS Finishing OrderA node finishes in DFS only after everything reachable from it has finished. Reverse the finishing order and every edge points forward.10 min
  3. 24.3Levels, Uniqueness and DP on a DAGProcessing nodes in topological order guarantees all predecessors are done, so you can compute levels, longest paths and earliest finish times in one pass.12 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 24.1Course Schedule IIMediumTopological Sort

    Produce the order, not just yes or no. Here the smallest available course is always taken, so the answer is unique.

  2. 24.2Alien DictionaryHardTopological Sort

    Build the graph yourself from comparisons, then sort it, catching the invalid-prefix case.

  3. 24.3Parallel CoursesMediumTopological Sort

    Kahn's algorithm level by level: the number of levels is the minimum number of rounds.

  4. 24.4Parallel Courses IIIHardTopological Sort

    DP in topological order: earliest finish = own time + latest prerequisite finish.

  5. 24.5Sequence ReconstructionMediumTopological Sort

    A topological order is unique exactly when there is only ever one choice.

  6. 24.6Minimum Height TreesMediumTopological Sort

    Kahn's idea on an undirected tree: peel leaves layer by layer until the centre remains.

  7. 24.7Longest Increasing Path in a MatrixHardTopological Sort

    A grid with "move to a larger value" edges is a DAG, so memoised DFS (DP over the DAG) gives the longest path.