问题如下: 给定偏序集的子集 S 找到 S 的最大元素。
例如，考虑 http://ndp.jct.ac.il/tutorials/Discrete/node34.html 中偏序集的 hass 图.给定它的一个子集 ex: {12, 2, 8} 最大元素是 12 和 8。
我不知道我是否准确描述了问题。我认为这个问题可能涉及传递闭包的一些排序或计算，但我有点困惑。
你能给我一些快速算法的方法吗？我想把它保存在 O(n^2) 中
谢谢。
稍微澄清一下。我的应用程序正在使用 RDF 图。如果存在表示 < 关系的特定边，则两个节点是可比较的。如果存在这样的显式关系或隐式传递关系，则两个节点可能是可比较的。
因此假设 hass 图正是我的 RDF 图。如果我从 2 开始进行深度优先搜索，我怎么知道 8 和 12 不可比？它们可能不是明确的，但可能是隐含的。
最佳答案
如果您知道排序关系的最小子集，您可以在线性时间内完成此操作:将其视为 DAG，然后进行深度优先遍历以找到所有没有后继的顶点。
关于algorithm - 寻找偏序集子集的最大元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10140610/