算法找到在向无环图最低的共同祖先？ [英] Algorithm to find lowest common ancestor in directed acyclic graph?

问题描述

想象一下，一个向无环图如下，其中：

Imagine a directed acyclic graph as follows, where:

• 在A是根（总有一个根）
• 在每个节点都知道它的父（S）
• 节点名称是任意的 - 没有什么可以从中推断
• 我们知道，从该节点添加到树的顺序A至G另一个源（例如，他们是在一个版本控制系统的提交）

我可以用什么算法来确定两个任意节点最低的共同祖先（LCA），例如，共同的祖先：

What algorithm could I use to determine the lowest common ancestor (LCA) of two arbitrary nodes, for example, the common ancestor of:

• B和E为B
• D和F为B

请注意：

• 在这里不一定从根（例如，G有两条路径）的单一路径，一个给定的节点，所以你不能简单地<一个href="http://www.stoimen.com/blog/2012/08/24/computer-algorithms-finding-the-lowest-common-ancestor/"相对=nofollow>移动路径从根到两个节点，并期待最后等于元素
• 在我发现LCA算法树木，尤其是二叉树，但他们这里不适用，因为一个节点可以有多个家长（即这不是一棵树）

推荐答案

我一直在寻找一个解决同样的问题，我发现了以下文件的解决方案：

I was looking for a solution to the same problem and I found a solution in the following paper:

http://dx.doi.org/10.1016/j.ipl。 2010.02.014

总之，你是不是在找最低的共同祖先，但最低的单一的共同祖先，它们在本文中定义。

In short, you are not looking for the lowest common ancestor, but for the lowest SINGLE common ancestor, which they define in this paper.

这篇关于算法找到在向无环图最低的共同祖先？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！