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

Question

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

• “A”是根(总是只有一个根)
• 每个节点都知道它的父节点
• 节点名称是任意的——无法从中推断出任何内容
• 我们从另一个来源得知，节点是按照 A 到 G 的顺序添加到树中的(例如，它们是版本控制系统中的提交)

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

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

注意:

• 从根到给定节点不一定只有一条路径(例如“G”有两条路径)，所以你不能简单地 traverse paths from root to the two nodes and look for the last equal element
• 我找到了树的 LCA 算法，尤其是二叉树，但它们不适用于这里，因为一个节点可以有多个父节点(即这不是树)

Answer 1

Den Roman's link ( Archived version ) 看起来很有希望，但对我来说似乎有点复杂，所以我尝试了另一种方法。这是我使用的一个简单算法:

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

1. 将 x 的所有祖先着色为蓝色(可以使用 BFS 完成)
2. 将 y 的所有blue 祖先着色为red(再次是 BFS)
3. 对于图中的每个红色节点，将其父节点的count加1

每个 red 节点的 count 值设置为 0 都是一个解决方案。

可能有不止一种解决方案，具体取决于您的图表。例如，考虑这张图:

LCA(4,5) 可能的解是 1 和 2。

请注意，如果您想找到 3 个或更多节点的 LCA，它仍然有效，您只需要为每个节点添加不同的颜色即可。