# What is topological sorting?

> A topological sort orders items so every "must come before" relation holds. Knuth's Algorithm T with counts and linked lists, and where it is used.

**Topological sort**: A topological sort arranges the items of a partial order (or the vertices of a directed acyclic graph) in a sequence where every item comes after all the items that must precede it.

A **topological sort** puts items in an order that respects a set of "a must come before b" rules: tasks before the tasks that depend on them, source files before the files that include them. It exists exactly when the rules contain no cycle.

## Knuth's approach

In [§2.2.3, Linked Allocation](https://cracked.guide/guide/knuth-w036-0), Knuth's Algorithm T keeps, for every item, a **count** of how many items must come before it and a **linked list** of the items that come after it. Every item with count zero can go out now; outputting one decrements the counts of its successors, and any that reach zero join the queue. If items remain when the queue empties, there is a cycle. It runs in time proportional to items plus relations.

## Where you use it

Build systems, package managers, spreadsheet recalculation, course prerequisites and instruction scheduling. It is also a NeetCode 150 staple: Course Schedule is topological sort in disguise.

## Questions

### Is the topological order unique?

Only when the relations force a single chain. Usually many orders are valid, and which one you get depends on how ties are broken.

---

Source: https://cracked.guide/glossary/topological-sort
cracked.guide: A free, dated 145-week path to getting genuinely cracked at programming.