pattern heroPT–23LeetCode Extension

Topological sort

First take what waits for nothing and strike it from the others' dependencies, which frees the next ones. The order comes out in one pass, and if at some point nothing is free, the dependencies form a loop.

P18 Topological sort1×

Example problem: find an order to take courses when some courses need others first.

A0B0C2D1E1F2queuefront on the left—order—
waits for other coursesin the queuecurrent coursewhere the arrow leadsin the order

Count the arrows into each course

indegree = {A: 0, B: 0, C: 2, D: 1, E: 1, F: 2}queue = –order = –course = –next = –
01/39
restart · back · play · step
Speed
1function courseOrder(graph):
2 indegree = arrows into each course
3 queue = courses with indegree 0
4 order = []
5 while queue is not empty:
6 course = queue.popFront()
7 order.pushBack(course)
8 for next in graph[course]:
9 decrease indegree[next] by 1
10 if indegree[next] is 0:
11 queue.pushBack(next)
12 return order

← → step · space play/pause

How to recognise

tasks with dependencies, such as prerequisites, a build order or "a must come before b", or a cycle check in a directed graph.

How to solve problems like this

  1. Draw an arrow from each task to the tasks that depend on it. Count each node's in-degree: the arrows coming in.
  2. Queue every node with in-degree 0: nothing holds it back.
  3. Take from the front and add it to the order. Lower the in-degree of each node it points to, and queue those that reach 0.
  4. If the order ends up shorter than the number of nodes, there is a cycle and no valid order.

Where it's used

  • Building programs. make and Bazel build files in an order where everything a file depends on is ready first. If the dependencies loop, make warns about a circular dependency.
  • Excel. Excel recalculates cells in dependency order: first the cells others refer to, then the cells that refer to them. If formulas refer to each other in a circle, it reports a circular reference.
  • Python. The standard library has graphlib.TopologicalSorter: it hands out tasks whose dependencies are all done and raises an error on a cycle.