我可以对此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

这称为传递减少问题.从形式上讲,您正在寻找一个最小(最少边)有向图,其传递闭包等于输入图的传递闭包.(上面的维基百科链接上的图表清楚地说明了.)

显然存在一种解决这个问题的有效算法,它需要与产生传递闭包相同的时间(即添加传递链接而不是删除它们的更常见的反问题),但是Aho,Garey,1972年论文的链接,和Ullman下载25美元,一些快速谷歌搜索没有出现任何好的描述.

编辑:Scott Cotton的graphlib包含Java实现! 这个Java库看起来组织得很好.