我代表的属性列表的DAG。 这些性质使得如果A> B，则具有向边到b。 它是可传递的一样，所以，如果A> B和B> C，则有向边至c。
然而，从A到C的有向边是多余的，因为一个具有向边到B和B具有向边至c。 我怎么能修剪所有这些多余的边缘？ 我想用最小生成树算法，但我真的不知道什么是合适的算法在这种情况下适用
我想我能做到从每个节点和所有传出边缘的深度优先搜索和比较，如果它可以在不使用某些边缘达到一定的节点，但这似乎效率极其低下，速度慢。
算法完成后，输出会在与图形一致的顺序存放的所有节点的线性表。 因此，如果有三个导向边缘B，C，和d。 b和c也是其中的每一个具有导向边缘到d中，输出可以是任一abcd或者ACBD。
这就是所谓的传递减少的问题 。 正式地说，你正在寻找最小（最少边缘）的有向图，传递闭包，其中等于输入图形的传递闭包。 （上述维基百科链路上的图清楚）。
显然存在对解决这一问题，即采用相同的时间作为制造传递闭包（即添加传递链接，而不是除去它们的更常见的逆问题），然而，一个有效的算法链路1972年纸通过阿霍，Garey，和乌尔曼花费$ 25下载和一些快速谷歌搜索不转了任何美好的描述。
编辑： 斯科特棉花graphlib包含Java实现 ！ 这个Java库看起来是非常良好的组织。
事实上，环顾四周多一点之后，我觉得Topologicalsort是什么，我在这里后我真的。
如果这些都已经在向边n个节点：
其实这只是一个排序算法，以及完全的复杂性应该是O（0.5N ^ 2）。
一个问题是，如果我们要一个节点的父节点，那么我们就需要更多的内存来记录边缘，所以我们可以从孩子追溯到父。 这可以在步骤3在这里我们选择从左边的节点除M更大的一个节点得到改善，这意味着我们需要保持节点列表知道节点剩下什么..
