Orderings & Lattices · step 7 of 13

Topological sorting

A topological sort lists the elements of a finite poset so that every element appears after everything below it — a linear extension of the partial order. Every finite poset has one, and it is unique exactly when the poset is already a chain. Kahn’s algorithm produces one by repeatedly outputting an element with no unprocessed predecessors.

Practise topological sorting free → All Orderings & Lattices subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Compute in-degreesFor each element, count how many elements are immediately below it in the Hasse diagram.
Output any zero-in-degree elementAnything with no remaining predecessors is currently available. Ties may be broken arbitrarily.
Remove and updateDelete the chosen element and decrement the in-degree of everything it covered. Repeat.
Detect cyclesIf elements remain but nothing has in-degree zero, the relation has a cycle and is not a partial order — no topological sort exists.

Worked example

Topologically sort the divisors of 12 under divisibility, and say how many valid orders exist.

In-degrees (immediate predecessors): 1 has 0; 2 and 3 have 1 each; 4 has 1 (from 2); 6 has 2 (from 2 and 3); 12 has 2.
Output 1. Now 2 and 3 are both available.
Output 2, then 4 and 3 are available; output 3, then 6; then 4; then 12.
Counting all linear extensions: the constraints are 1 first, 12 last, 2 before 4 and 6, 3 before 6.

Answer. One valid order is 1, 2, 3, 4, 6, 12. In total there are 5 linear extensions of this poset.

Where marks get dropped

These are the specific errors that cost credit on topological sorting questions — QED's rubric penalises each of them separately.

Sorting numerically and calling it topological. Numeric order happens to work here but fails for posets whose labels do not match the order.
Forgetting to update in-degrees after each removal, which makes later elements look unavailable.
Assuming the sort is unique. Any incomparable pair can be output in either order, so multiple linear extensions are the norm.

Practise this until it is automatic

Unlimited fresh questions

QED generates new topological sorting problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Orderings & Lattices mastery is tracked so you know when this is exam-ready.

Topological sorting — frequently asked questions

What is a linear extension?

A total order that contains the partial order: whenever a ⊑ b in the poset, a comes before b in the extension. Topological sorting is exactly the algorithm that finds one.

How fast is Kahn’s algorithm?

O(V + E) — linear in the size of the diagram, since each element and each edge is processed once.

Where is this used?

Build systems, task schedulers, spreadsheet recalculation and package managers all topologically sort a dependency DAG, and report a cycle when the sort fails.

The rest of Orderings & Lattices

Partial orders, Hasse diagrams, bounds, lattices. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make topological sorting exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →