有向无环图中查找最近公共祖先的算法是什么？

Question

假设有一个有向无环图，其中：

• "A" 是根节点（始终只有一个根节点）
• 每个节点都知道它的父节点
• 节点名称是任意的 - 不能从中推断出任何信息
• 我们从另一个来源得知这些节点按顺序从 A 到 G 添加到树中（例如，它们是版本控制系统中的提交）

我应该使用什么算法来确定两个任意节点的最近公共祖先（LCA），例如以下节点的共同祖先：

• B 和 E 的 LCA 是 B
• D 和 F 的 LCA 是 B

注意：

• 从根节点到给定节点不一定只有一条路径（例如，“G”有两条路径），因此您不能简单地遍历从根到两个节点的路径并查找最后一个相等元素
• 我已经为树，特别是二叉树，找到了LCA算法，但它们不适用于这里，因为一个节点可以有多个父节点（即这不是一棵树）

- Andrew Swan

---

如果您在这里发布这个问题：http://cs.stackexchange.com/，您肯定会得到更多和更好的答案。 - A.B.

那么问题就变成了理解答案...;-) - Andrew Swan

@AndrewSwan：如果这个图是无向的，它将是循环的。在当前状态下，它是非循环的。 - Regexident

你解决了这个问题吗？ - plus-

不，唉，但现在对我来说只是学术上的兴趣。 - Andrew Swan

Answer 1

Den Roman's link (存档版本) 看起来很有前途，但对我来说似乎有点复杂，所以我尝试了另一种方法。 这是我使用的简单算法：

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

1. 将 x 的所有祖先节点颜色设置为 蓝色（可以使用 BFS 实现）
2. 将 y 的所有 蓝色 祖先节点颜色设置为 红色（再次使用 BFS）
3. 对于图中的每个 红色 节点，将其父节点的 count 值加一

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

取决于您的图形，可能会有多个解决方案。例如，请考虑下面的图形：

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

如果要查找 3 个或更多节点的 LCA，也仍然可以工作，只需为每个节点添加不同的颜色即可。

- Anthony Garcia-Labiad

---

你所描述的算法似乎存在一些不必要的复杂性，掩盖了实际情况。当你只是将计数用作标志时，为什么需要计数？当似乎只需要一种颜色来表示“先前考虑过的所有节点的祖先”，以及第二种颜色来表示“当前正在考虑的节点的祖先”时，为什么需要N种颜色？ - R.. GitHub STOP HELPING ICE

Answer 2

我曾经遇到同样的问题，后来在下面这篇论文中找到了解决方案：

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

简单来说，您不是在寻找最低公共祖先，而是在寻找最低的单一公共祖先，这个概念在这篇论文中有定义。

- Steven Obua

Answer 3

我知道这是一个老问题，也有很好的讨论。但是由于我遇到了一些类似的问题需要解决，因此我发现 JGraphT 的最近公共祖先算法可能会有所帮助：

• NativeLcaFinder
• TarjanLowestCommonAncestor

- Hamid Nazari

---

JGraphT的NaiveLcaFinder是最好的选择。Tarjan算法只适用于树形结构。 - Snicolas

Answer 4

仅仅是一些疯狂的想法。使用两个输入节点作为根节点，同时进行两个BFS遍历，逐步前进。在某个步骤时，当它们的BLACK集（记录已访问的节点）中出现重叠时，算法停止，重叠的节点即为它们的LCA。通过这种方式，任何其他共同祖先的距离都比我们发现的更远。

- Ning

Answer 5

假设您想在图中找到x和y的祖先。

维护一个存储每个节点父节点的向量数组- parents。

1. 首先进行BFS（保持存储每个顶点的父节点），并找到x的所有祖先（查找x的父节点并使用parents，找到x的所有祖先）并将它们存储在一个向量中。还要在该向量中存储每个父节点的深度。 2. 使用相同的方法查找y的祖先，并将它们存储在另一个向量中。现在，您有两个分别存储x和y祖先及其深度的向量。 3. LCA是具有最大深度的公共祖先。深度定义为从根（入度为0的顶点）到该节点的最长距离。现在，我们可以按其深度的降序对向量进行排序，并找出LCA。使用此方法，我们甚至可以找到多个LCA（如果有的话）。

- shiwang

Answer 6

这个链接 (存档版本) 描述了在Mercurial中如何完成 - 基本思路是找到指定节点的所有父节点，按距离从根节点分组，然后对这些组进行搜索。

- Den Roman

Answer 7

package FB;

import java.util.*;

public class commomAnsectorForGraph {
    public static void main(String[] args){
        commomAnsectorForGraph com = new commomAnsectorForGraph();
        graphNode g = new graphNode('g');
        graphNode d = new graphNode('d');
        graphNode f = new graphNode('f');
        graphNode c = new graphNode('c');
        graphNode e = new graphNode('e');
        graphNode a = new graphNode('a');
        graphNode b = new graphNode('b');

        List<graphNode> gc = new ArrayList<>();
        gc.add(d);
        gc.add(f);
        g.children = gc;

        List<graphNode> dc = new ArrayList<>();
        dc.add(c);
        d.children = dc;

        List<graphNode> cc = new ArrayList<>();
        cc.add(b);
        c.children = cc;

        List<graphNode> bc = new ArrayList<>();
        bc.add(a);
        b.children = bc;

        List<graphNode> fc = new ArrayList<>();
        fc.add(e);
        f.children = fc;

        List<graphNode> ec = new ArrayList<>();
        ec.add(b);
        e.children = ec;

        List<graphNode> ac = new ArrayList<>();
        a.children = ac;

        graphNode gn = com.findAncestor(g, c, d);
        System.out.println(gn.value);
    }

    public graphNode findAncestor(graphNode root, graphNode a, graphNode b){
        if(root == null) return null;
        if(root.value == a.value || root.value == b.value) return root;

        List<graphNode> list = root.children;

        int count = 0;
        List<graphNode> temp = new ArrayList<>();

        for(graphNode node : list){
            graphNode res = findAncestor(node, a, b);
            temp.add(res);
            if(res != null) {
                count++;
            }
        }

        if(count == 2) return root;

        for(graphNode t : temp){
            if(t != null) return t;
        }

        return null;
    }
}
class graphNode{
    char value;
    graphNode parent;
    List<graphNode> children;
    public graphNode(char value){
        this.value = value;
    }
}

- MINGSONG LIU

Answer 8

如果图中存在环，则“祖先”定义模糊。也许你的意思是从DFS或BFS输出的树上的祖先？或者你所说的“祖先”是指有向图中从E和B之间跳数最少的节点吗？

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

编辑： 现在你澄清了一些事情，我想我理解你所寻找的东西了。

如果您只能向“上”遍历树，则我建议您从E执行BFS，并从B执行BFS。您的图中的每个节点都将有两个与之关联的变量：从B跳数和从E跳数。让B和E都拥有图节点列表的副本。 B的列表按从B跳数排序，而E的列表按从E跳数排序。

对于B列表中的每个元素，请尝试在E的列表中找到它。将匹配项放入第三个列表中，按B跳数+E跳数排序。当您用尽B的列表后，您的第三个排序列表应包含LCA作为其头部。这允许一种解决方案、多个解决方案（按B的BFS顺序任意选择）或无解决方案。

- AndyG

---

节点的祖先必须可通过“向上”遍历图表中的边缘，即沿箭头方向遍历边缘，才能到达。 - Andrew Swan

@AndrewSwan：是的，但答案仍然不唯一。考虑A>C、B>D、C>E、C>F、D>E、D>F。如果我要求LCA(A,B)，你要选E还是F？ - tmyklebu

那个图对于这种情况是无效的，因为它有两个根节点E和F。应该只有一个根节点，这意味着任何两个节点始终只有一个LCA。我已经编辑了问题以澄清这一点。 - Andrew Swan

将 E>G 和 F>G 添加到 @tmyklebu 的示例中，您将得到一个根和两个 LCA，即 E 和 F。这是允许节点具有多个父节点的直接结果。 - beaker

@AndrewSwan：我已经对我的帖子进行了编辑。我是否正确理解了你的问题？ - AndyG

Answer 9

我也需要完全相同的东西，在有向无环图中找到LCA（最近公共祖先）。LCA问题与RMQ（区间最小查询问题）有关。

可以将LCA减少到RMQ，并从有向无环图中找到两个任意节点的所需LCA。

我发现这个教程非常详细和好。我也计划实现这个。

- Asraful

Answer 10

我提出了一个O（|V| + |E|）时间复杂度的解决方案，我认为这种方法是正确的，否则请纠正我。

给定有向无环图，我们需要找到两个顶点v和w的LCA。

步骤1：使用bfs http://en.wikipedia.org/wiki/Breadth-first_search查找所有顶点到根顶点的最短距离，并找到每个顶点的父节点，时间复杂度为O（|V| + |E|）。

步骤2：通过使用父节点找到两个顶点的公共祖先，直到达到根顶点，时间复杂度为2|v|。

步骤3：LCA将是具有最大最短距离的公共祖先。

因此，这是一个O（|V| + |E|）时间复杂度的算法。

如果我错了或有其他建议，请纠正我。

- Nitish Jain

---

如何使用父节点查找两个顶点的公共祖先？你能详细说明一下吗？ - vincent mathew