在有向无环图中找到最低共同祖先的算法？

Question

想象一下有向无环图如下,其中:

• "A"是根(总有一个根)
• 每个节点都知道它的父节点
• 节点名称是任意的 - 没有什么可以从它们推断出来
• 我们从另一个来源得知节点是按照A到G的顺序添加到树中的(例如它们是版本控制系统中的提交)

我可以使用什么算法来确定两个任意节点的最低共同祖先(LCA),例如,共同的祖先:

• B和E是B.
• D和F是B.

注意:

• 从根开始到给定节点不一定有一条路径(例如"G"有两条路径),因此您不能简单地遍历从根到两个节点的路径并查找最后一个相等的元素
• 我发现树的LCA算法,特别是二叉树,但它们不适用于此,因为一个节点可以有多个父节点(即这不是一棵树)

Answer 1

Den Roman的链接似乎很有希望,但对我来说似乎有点复杂,所以我尝试了另一种方法.这是我使用的一个简单算法:

假设您想用x和y两个节点计算LCA(x,y).每个节点必须有一个值,color并且countresp.初始化为白色和0.

1. 将x的所有祖先颜色为蓝色(可以使用BFS完成)
2. 颜色的所有蓝色的祖先Ÿ为红色(BFS再次)
3. 对于图中的每个红色节点,将其父项递增count1

具有设置为0的值的每个红色节点是解决方案.count

根据您的图表,可以有多个解决方案.例如,请考虑以下图表:

LCA(4,5)可能的解决方案是1和2.

请注意,如果您想要找到3个或更多节点的LCA,它仍然可以工作,您只需要为每个节点添加不同的颜色.

Answer 2

我正在寻找同样问题的解决方案,我在下面的论文中找到了一个解决方案:

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

简而言之,您不是在寻找最低的共同祖先,而是寻找他们在本文中定义的最低的共同祖先.

Answer 3

如果图表有循环，那么“祖先”的定义就很宽松。也许您指的是 DFS 或 BFS 的树输出上的祖先？E或者也许“祖先”是指有向图中最小化来自和的跳数的节点B？

如果您不担心复杂性，那么您可以计算从每个节点到 和 的 A* （或 Dijkstra 的最短路径E）B。E对于能够同时到达和 的节点B，可以找到最小化 的节点PathLengthToE + PathLengthToB。

编辑：现在您已经澄清了一些事情，我想我明白您在寻找什么。

如果您只能“向上”树，那么我建议您执行来自 的 BFSE以及来自 的 BFS B。图中的每个节点都有两个与之关联的变量： hops fromB和 hops from E。让B和都E拥有图节点列表的副本。B的列表按来自 的跳数排序，B而E的列表按来自 的跳数排序E。

对于B的列表中的每个元素，尝试在 的E列表中找到它。将匹配项放入第三个列表中，按 hops from B+ hops from排序E。当你用完B's 列表后，你的第三个排序列表应该在其头部包含 LCA。这允许一个解决方案、多个解决方案（通过其 BFS 排序任意选择B）或没有解决方案。