0

我有一个需要用于分析的节点层次结构。有点像这样

在此处输入图像描述

我正在尝试找到一种算法，使我能够找到两个节点之间最近的共同祖先。我知道有一些算法可以找到最低的共同祖先，但我还没有找到一个可以让我们找到最近的几个的算法。

例如，在我上面链接的图片中，如果我给它两个节点：0 和 1，它应该返回 2 和 5。即它应该返回没有后代的节点的所有共同祖先也是共同祖先。一种天真的方法是获取 0 和 1 的所有共同祖先：{7, 5, 6, 3, 2}，然后消除 7，因为它在集合中有后代。然后它也会消除 6 和 3。所以它会返回 SLCA = {5,2}。目前，我已将每个节点的所有祖先存储在一个列表中。所以这种天真的方法是可能的。但是，我想做一个更有效的方法，即使是非常大的图也可以扩展。最终，对于给定的图，我希望能够计算每对节点的成对 SLCA。我认为这种蛮力方法对于非常大的图表会很慢。

有人知道这样的算法吗？我一直在阅读这些论文，但它们非常密集，我一直在努力理解它们。

https://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/LCA-Max-witness.pdf

http://www.ccs.neu.edu/home/dherman/browse/projects/mini-javac/papers/bender01finding.pdf

https://algo2.iti.kit.edu/download/fischer10new.pdf

https://algo2.iti.kit.edu/download/fischer10new.pdf

我很感激帮助

4

1 回答 1

1

好吧，实际上您的“蛮力”算法非常有效。我们来分析一下：

找到所有共同的祖先，您可以使用两个 BFS 和一个数组来保存两个树中的节点：Time - O(V + E)，Memory: O(V)。

现在您可以找到组中所有没有后代的祖先，它们是最接近根的所有节点。这不会花费很长时间，获取该组的子图并O(V + E)及时找到没有传入边的节点（通过迭代节点）和O(V)内存。这将是你的答案。

所以总而言之-时间O(V + E)，记忆O(V)。

下一个答案不是正确答案，它找到了最近的共同祖先（我写错了，我真的不想删除它）：

复制图表，现在我们有了G1和G2。为 中的每个节点G1创建一条新边到 中的相应节点G2。'翻转'所有边缘G2- 如果从v到u现在有边缘，它是 from uto v。

调用这个新图G，调用你需要的两个节点来查找 SLCAu和v.

很容易证明，从uinG1到对应vin的最短路径G2会经过一条 from G1to边，G2并且这条边的节点（这条边上的两个节点都是对应的）将在 SLCA 组中。
那是因为如果您查看原始图，我们从每个节点获取的路径v是u最短的，这就是 SLCA 组的定义。

现在您需要找到所有最短路径长度的路径并提取所有这些节点。

时间：（O(E + V)最短路径 - BFS）
内存：O(V)（BFS）

于 2019-12-09T18:01:38.340 回答