我可以对这个DAG应用什么算法?

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

显然,存在一种有效的算法来解决这个问题,它与生成传递闭包的时间相同(即,添加传递链接而不是删除链接的更常见的逆问题),但是 link to the 1972 paper 通过aho,Garey和Ullman的下载成本是25美元,一些快速的谷歌搜索没有找到任何好的描述。

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

实际上,在多看了一眼之后,我认为 Topologicalsort 是我真正想要的。

如果这些节点已经是n个具有定向边的节点:

1. 从任意点m开始,循环其所有子边,选择最大的子边(如n),删除其他边,复杂度应为o(n)。如果不存在n(没有子边,请转到步骤3)。
2. 从N开始,重复步骤1。
3. 从M点开始,选择最小的父节点(如T),移除其他节点的边。
4. 从t开始,重复步骤3…..

实际上,它只是一个排序算法,并且总的复杂性应该是O(0.5N^2)。

一个问题是,如果我们想要循环一个节点的父节点,那么我们需要更多的内存来记录边缘,这样我们就可以从子节点追溯到父节点。这可以在步骤3中得到改进,我们从大于m的左侧节点中选择一个节点,这意味着我们需要保留一个节点列表,以了解剩下的节点。