algorithm - 对一组有约束的项目进行排序

Question

我正在寻找一种算法，允许我订购一组以满足一组条件。条件只能是“必须出现在之前”或“必须出现在之后”。例如:

• A:必须出现在B之前
• B
• C:必须出现在A之后，必须出现在D之前
• D:必须出现在B之前
• E

两个有效的解决方案是“ACDBE”和“EACDB”。我只关心找到一个有效的解决方案。

我不知道如何实现它。也许我只是不知道它的正确名称，如果我知道的话我就能找到信息。

可以让我找到解决方案的算法是什么？或者这种算法叫什么(我应该谷歌什么)？

Answer 1

看起来您正在寻找 topological sort .

这个想法是您可以在有向图中编码您的依赖关系:您的集合元素是节点，您的条件是边。 A 和 B 之间存在一条边当且仅当“A 必须出现在 B 之前”。

拓扑排序保证为您的问题找到有效的解决方案(如果存在)，并且有一些著名的算法在图的大小上具有线性时间复杂度。