algorithm - 从一系列变量比较中找到至少一个解决方案

Question

在工作中，我遇到了一道算法题。问题的一般化版本是

Given a set of comparisons between two variables (Greater than or less than). Find at least one single inequation with all variables in it that complies with the comparisons above.

例如有 A > B，B > C，D > A，E > C。一个答案是 D > A > B > E > C。请注意，可以有多个答案，但只有一个答案就足够了。也可能存在没有答案的冲突。

我想知道这种问题是否有名称，以及无需检查所有组合即可解决此问题的最佳做法是什么。

谢谢!

Answer 1

是的，一个很好的问题。您听说过图论中的拓扑排序吗。

可以这样想。 x > y 表示存在从x 到 y 的有向边(如x ---> y)。因此，基本上您有一个连接顶点 A B C D 和 E 的有向边网络。申请topological sort得到答案。

拓扑排序基本上是指在排序后得到的顶点列表中，如果存在从 x 到 y 的有向边，x 将始终出现在 y 之前。