排序部分有序列表的最佳方法是什么?


问题内容

最好用一个小例子来说明。
鉴于关系

A < B < C
A < P < Q

正确的输出将是

ABCPQ or APQBC or APBCQ ... etc.

换句话说,给定关系所在的任何顺序均有效。

我对最容易实现的解决方案最感兴趣,但是在速度和时间上最好的O(n)也很有趣。


问题答案:

这称为拓扑排序

标准算法是输出一个最小的元素,然后将其删除并重复直到完成。