Topological Sort & Indegree Queues

Foundations

In the Graphs course, Kahn's algorithm ordered a directed graph by repeatedly taking a node with in-degree 0, one that no remaining arrow points into. Here the same queue is read in layers. Every node in the queue at one moment is free at the same time; taking them all lowers their successors' in-degrees, and the nodes that reach 0 form the next layer. Layers are the rounds of a schedule, each one runnable in parallel.

The graph usually has to be built first. Dependencies arrive as facts such as pairs [before, after], each becoming an arrow that adds 1 to the in-degree of after. If arrows form a cycle, some nodes never reach in-degree 0, so the order comes out shorter than the node count, and that shortfall is how the algorithm reports that no valid order exists.

Take five nodes with adj = [[2], [2, 3], [4], [4], []]: arrows 0 → 2, 1 → 2, 1 → 3, 2 → 4, and 3 → 4. Nodes 0 and 1 start at in-degree 0, so they are layer 1. Removing them frees 2 and 3, layer 2; removing those frees 4, layer 3. The order 0, 1, 2, 3, 4 respects every arrow, in three rounds.

• Topological Sort

  That lesson ordered a dependency graph with Kahn's algorithm. This lesson builds the graph from data first, then peels it in layers.

  Open lesson

Case Scenario

Alien Dictionary gives words sorted by an unknown alphabet and asks for an order of its letters. Each neighboring pair of words supplies one fact: their first differing letters, in that order, become an arrow. Peeling the letter graph by in-degree then yields the alphabet, or "" if the facts contradict. For words = ["wrt", "wrf", "er", "ett", "rftt"], the arrows give "wertf".

The direct approach tries every possible alphabet, all A! orders of the A letters, and checks whether each one keeps the words sorted. Five letters allow 120 orders; fifteen allow over a trillion. The neighboring pairs already say which letters must come before which, and guessing ignores that evidence entirely.