我可以将什么算法应用于此 DAG？
我有一个代表属性列表的 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。
I have a DAG representing a list of properties. These properties are such that if a>b, then a has a directed edge to b. It is transitive as well, so that if a>b and b>c, then a has a directed edge to c.
However, the directed edge from a to c is superfluous because a has a directed edge to b and b has a directed edge to c. How can I prune all these superfluous edges? I was thinking of using a minimum spanning tree algorithm, but I'm not really sure what is the appropriate algorithm to apply in this situation
I suppose I could do a depth first search from each node and all its outgoing edges and compare if it can reach certain nodes without using certain edges, but this seems horribly inefficient and slow.
After the algorithm is complete, the output would be a linear list of all the nodes in an order that is consistent with the graph. So if a has three directed edges to b,c, and d. b and c also each of which has a directed edge to d, the output could be either abcd or acbd.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这称为传递归约问题。 正式地说，您正在寻找一个最小（最少边）的有向图，其传递闭包等于输入图的传递闭包。 （上面的维基百科链接上的图表清楚地表明了这一点。）
显然，存在一种有效的算法来解决这个问题，该算法花费与生成传递闭包相同的时间（即添加传递链接而不是删除它们的更常见的逆问题） ，但是 链接到Aho、Garey 和 Ullman 于 1972 年发表的论文下载费用为 25 美元，快速谷歌搜索并没有找到任何好的描述。
编辑：Scott Cotton 的
graphlib包含Java 实现! 这个 Java 库看起来组织得很好。This is called the transitive reduction problem. Formally speaking, you are looking for a minimal (fewest edges) directed graph, the transitive closure of which is equal to the transitive closure of the input graph. (The diagram on the above Wikipedia link makes it clear.)
Apparently there exists an efficient algorithm for solving this problem that takes the same time as for producing a transitive closure (i.e. the more common inverse problem of adding transitive links instead of removing them), however the link to the 1972 paper by Aho, Garey, and Ullman costs $25 to download, and some quick googling didn't turn up any nice descriptions.
EDIT: Scott Cotton's
graphlibcontains a Java implementation! This Java library looks to be very well organised.实际上，经过更多查看后，我认为 Topologicalsort 才是我真正想要的这里。
Actually, after looking around a little more, I think a Topologicalsort is what I'm really after here.
如果这些已经是n个具有有向边的节点：
实际上这只是一个排序算法，总的复杂度应该是o(0.5n^2)。
一个问题是，如果我们想要循环一个节点的父节点，那么我们需要更多的内存来记录边缘，以便我们可以从子节点追溯到父节点。 这可以在步骤 3 中得到改进，我们从左侧节点中选择一个大于 M 的节点，这意味着我们需要保留一个节点列表来知道还剩下哪些节点。
If these are already n nodes with directed edges:
Actually it's just a ordering algorithm, and the totally complexity should be o(0.5n^2).
One problem is that if we want loop one node's parent nodes, then we need more memory to log edge so we can trace back from child to parent. This can be improved in the step 3 where we choose one node from the left nodes bigger than M, this means we need to keep a list of nodes to know what nodes are left..