这个DAG可以应用哪种算法？

Question

4

我有一个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。

- samoz

如果 a>b>d 且 a>c>d，你会怎么做？ - ijw

a 会有两条有向边，一条指向 b，另一条指向 c。而 b 和 c 分别会有一条有向边指向 d。 - samoz

但是如果a>b>d和a>c>d，正如你所说的a->b，a->c，b->d和c->d，那么是否可以确定b->c或c->b呢？我认为是这样的，这将使问题变得简单得多，但是你用">"的方式谈论它，这听起来并不像简单的算术... - user447688

@John：在 b 和 c 之间没有方向边意味着此比较的结果是未知的或不可知的。关键不是要弄清楚 b>c 还是 b<c——对于我们的目的来说这并不重要——而是要保留输入 DAG 中存在的“知识”和“无知”状态。 - j_random_hacker

@David 因为我需要将其应用于图中的每个节点到其他节点，这对我来说似乎有些过度。也许不是，你有什么想法吗？@John 我不知道b>c还是b<c；事实上这并不重要。该算法只是试图创建一个与提供的图一致的线性元素列表。 - samoz

显示剩余2条评论

3个回答

2

实际上，在进一步查看后，我认为拓扑排序是我在这里真正需要的。

- samoz

s/topographical/topological/; - j_random_hacker

0

如果已经有n个带有有向边的节点：

其实这只是一个排序算法，总复杂度应该是o(0.5n^2)。

一个问题是，如果我们想循环遍历一个节点的父节点，那么我们需要更多的内存来记录边缘，以便我们可以从子节点追溯到父节点。这可以在第3步中改进，我们选择一个左节点大于M的节点，这意味着我们需要保持一个节点列表，以知道哪些节点是剩余的。

- Sam Liao

我以这种形式作为输入获得了图形。我想我应该更具体一些。我正在尝试使用图形检索这些属性的线性顺序，例如a>b>c>d>等等。 - samoz

1

在第一步中，如何知道最大的子节点是哪个？ - user447688

tmp = 0; for_each_child(current,a) { if(tmp > a) { remove_edge(current, a); } else tmp = a; } 因此每条边只被检查一次。 - Sam Liao

如果我理解正确的话，您的算法将从每个节点中删除所有出边，但保留一条，从而形成路径集合。-1。（如果不是这样，请澄清一下，我会重新考虑。） - j_random_hacker

@arsane：根据您最近的评论中的代码，显然存在错误 - 它所删除的边将取决于for_each_child循环中子节点的（未指定的）顺序。此外，a是什么数量？那是该节点在图的某个拓扑排序中的位置吗？ - j_random_hacker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

这被称为传递闭包问题。严格来说，您正在寻找最小（边数最少）的有向图，其传递闭包等于输入图的传递闭包。（上面维基百科链接中的图表明了这一点。）

显然，存在一种有效的算法来解决此问题，它的时间与生成传递闭包的时间相同（即添加传递链接而不是删除它们的更常见的反问题），但是Aho、Garey和Ullman的1972年论文链接需要25美元下载，一些快速搜索也没有找到任何好的描述。

编辑：Scott Cotton的graphlib 包含一个 Java实现！ 这个Java库看起来非常有组织。