我有一个代表属性列表的 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。
这称为传递约简问题。正式地说，您正在寻找一个最小（最少边）有向图，其传递闭包等于输入图的传递闭包。（上面的维基百科链接上的图表很清楚。）
显然，存在一种有效的算法来解决这个问题，它与产生传递闭包所需的时间相同（即添加传递链接而不是删除传递链接的更常见的逆问题），但是链接到Aho，Garey的 1972 年论文， Ullman 的下载费用为 25 美元，而且一些快速的谷歌搜索并没有找到任何好的描述。
编辑：Scott Cotton'sgraphlib包含一个Java 实现！ 这个 Java 库看起来组织得很好。
实际上，在环顾四周之后，我认为拓扑排序是我真正想要的。
如果这些已经是具有有向边的 n 个节点：
实际上它只是一个排序算法，总复杂度应该是o(0.5n^2)。
一个问题是，如果我们想要循环一个节点的父节点，那么我们需要更多的内存来记录边缘，以便我们可以从子节点追溯到父节点。这可以在第 3 步中改进，我们从左侧节点中选择一个大于 M 的节点，这意味着我们需要保留一个节点列表以了解还剩下哪些节点。