Name given to an
algorithm for
extending a
partial order relation to a
total order.
The input is a set of ordered pairs i -> j, meaning "i must come before j". The output is a permutation of 1, ..., n such that i is located before j whenever i -> j. Of course, for some inputs (those that specify a loop) this is not possible; the algorithm reports this error condition.
Here's the algorithm:
- Compute and store the in degree d[j] for each j (this is the number of i's for which i -> j).
- Initialise a collection (typically a queue or a stack, doesn't matter which) C to {j : d[j] == 0}.
- While C is not empty:
- Remove some element i from C.
- Output i.
- For each j such that i -> j, decrement d[d]; if this zeros it, add j to C.
- If we output n values in the previous step, the sort succeeded; otherwise it failed, and a loop exists in the input.
Properly implemented, the algorithm runs in
time complexity O(
n2) on a
RAM machine. This is quite easy in practice! Just store a linked list of
j's for which
i -> j for each
i; use this step to calculate
d[], too. The rest is
an easy exercise for the reader...