algorithm - 我可以将什么算法应用于此 DAG？

Question

我有一个代表属性列表的 DAG。这些属性是这样的，如果 a>b，则 a 具有到 b 的有向边。它也是传递性的，因此如果 a>b 且 b>c，则 a 具有到 c 的有向边。

但是，从 a 到 c 的有向边是多余的，因为 a 有一条到 b 的有向边，b 有一条到 c 的有向边。我怎样才能修剪所有这些多余的边缘？我正在考虑使用最小生成树算法，但我不确定在这种情况下应用什么合适的算法

我想我可以从每个节点及其所有传出边进行深度优先搜索，并比较它是否可以在不使用某些边的情况下到达某些节点，但这似乎效率低下且速度缓慢。

算法完成后，输出将是所有节点的线性列表，其顺序与图形一致。因此，如果 a 具有到 b、c 和 d 的三个有向边。 b 和 c 也都有到 d 的有向边，输出可以是 abcd 或 acbd。

Answer 1

这叫做 transitive reduction problem .正式地说，您正在寻找一个最小(最少边)有向图，其传递闭包等于输入图的传递闭包。 (上面维基百科链接上的图表很清楚。)

显然存在一种解决此问题的有效算法，它与生成传递闭包所花费的时间相同(即添加传递链接而不是删除它们的更常见的逆问题)，但是 link to the 1972 paper Aho、Garey 和 Ullman 的下载费用为 25 美元，而且一些快速谷歌搜索没有找到任何好的描述。

编辑:Scott Cotton's graphlib包含 Java implementation ! 这个 Java 库看起来组织得很好。