Tag: 图算法

validation和规范化部分有序集

我有一对像这样的对： [[“a”, “b”], [“b”, “d”], [“a”, “c”], [“e”, “d”], [“a”, “d”], …, [“s”, “f”]] 检查给定数组是否可以表示部分排序的有效方法是什么？ 也就是说，给定数组中没有“循环”，如[“a”, “b”], [“b”, “c”], [“c”, “a”] 。 如果确认数组表示偏序，我想通过去除所有可以通过自反性或传递性导出的对来对其进行标准化。 例如，在上文中，由于存在[“a”, “b”]和[“b”, “d”] ，所以该对[“a”, “d”]是多余的，应该被移除。 1到2之间的顺序无关紧要。 如果2应该在1的过程之前或之内完成，那么，这很好。 我最好在Ruby 1.9.3中使用它，但只需伪代码即可。