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:

1. Compute and store the in degree d[j] for each j (this is the number of i's for which i -> j).
2. Initialise a collection (typically a queue or a stack, doesn't matter which) C to {j : d[j] == 0}.
3. 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.
4. 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...

Log in or register to write something here or to contact authors.