Task dependencies form a partial order and topological sort produces a valid build order. Why does the algorithm need a partial order rather than a total one?

Question

Accepted Answer

Because most tasks are genuinely incomparable

Answer

Because total orders cannot be sorted algorithmically

Answer

Because partial orders permit cycles, which build systems need

Answer

Because a total order would require every task to depend on every other

Task dependencies form a partial order and topological sort produces a valid build order. Why does the algorithm need a partial order rather than a total one?

Practise Relations

More questions on Relations