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

Question

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

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

有向无环图

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

B和E是B
D和F是B

笔记：

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

score 14 · Accepted Answer

Den Roman 的链接（存档版本）似乎很有希望，但对我来说似乎有点复杂，所以我尝试了另一种方法。这是我使用的一个简单算法：

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

将x的所有祖先着色为蓝色（可以使用BFS完成）
将y的所有蓝色祖先着色为红色（再次 BFS）
对于图中的每个红色节点，将其父节点的值加count一

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

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

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

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

score 5 · Accepted Answer

我一直在寻找相同问题的解决方案，并在以下论文中找到了解决方案：

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

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

score 3 · Accepted Answer

我知道这是一个老问题和很好的讨论，但是由于我有一些类似的问题要解决，所以我遇到了JGraphT的Lowest Common Ancestor算法，认为这可能会有所帮助：

score 2 · Accepted Answer

只是一些疯狂的想法。将两个输入节点都用作根，并逐步同时执行两个 BFS 怎么样。在某个步骤，当它们的 BLACK 集合（记录访问过的节点）中有重叠时，算法停止并且重叠的节点是它们的 LCA（s）。这样一来，任何其他共同祖先的距离都会比我们发现的要长。

score 2 · Accepted Answer

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

维护一个向量数组——父母（存储每个节点的父母）。

首先做一个bfs（继续存储每个顶点的父母）并找到x的所有祖先（找到x的父母并使用parents，找到x的所有祖先）并将它们存储在一个向量中。此外，将每个父级的深度存储在向量中。
使用相同的方法找到 y 的祖先并将它们存储在另一个向量中。现在，您有两个向量分别存储 x 和 y 的祖先及其深度。
LCA 将是具有最大深度的共同祖先。深度定义为距根的最长距离（in_degree=0 的顶点）。现在，我们可以按照向量深度的降序对向量进行排序并找出 LCA。使用这种方法，我们甚至可以找到多个 LCA（如果有的话）。

score 1 · Accepted Answer

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

score 0 · Accepted Answer

我也需要完全相同的东西，在 DAG（有向无环图）中找到 LCA。LCA 问题与 RMQ（Range Minimum Query Problem）有关。

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

我发现这个教程的细节很好。我也计划实现这一点。

score 0 · Accepted Answer

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

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

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

Step2：通过使用parent找到两个顶点的共同祖先，直到我们到达根顶点时间复杂度- 2|v|

Step3: LCA 将是具有最大最短距离的共同祖先。

所以，这是 O(|V| + |E|) 时间复杂度算法。

如果我错了，请纠正我或欢迎任何其他建议。

score 0 · Accepted Answer

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

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

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

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

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

score 0 · Accepted Answer

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;
    }
}

score -2 · Accepted Answer

每个人。请在Java中尝试。

static String recentCommonAncestor(String[] commitHashes, String[][] ancestors, String strID, String strID1)
{
    HashSet<String> setOfAncestorsLower = new HashSet<String>();
    HashSet<String> setOfAncestorsUpper = new HashSet<String>();
    String[] arrPair= {strID, strID1};
    Arrays.sort(arrPair);
    Comparator<String> comp = new Comparator<String>(){
        @Override
        public int compare(String s1, String s2) {
           return s2.compareTo(s1);
        }};
    int indexUpper = Arrays.binarySearch(commitHashes, arrPair[0], comp);
    int indexLower = Arrays.binarySearch(commitHashes, arrPair[1], comp);
    setOfAncestorsLower.addAll(Arrays.asList(ancestors[indexLower]));
    setOfAncestorsUpper.addAll(Arrays.asList(ancestors[indexUpper]));
    HashSet<String>[] sets = new HashSet[] {setOfAncestorsLower, setOfAncestorsUpper};
    for (int i = indexLower + 1; i < commitHashes.length; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            if (sets[j].contains(commitHashes[i]))
            {
                if (i > indexUpper)
                    if(sets[1 - j].contains(commitHashes[i]))
                        return commitHashes[i];
                sets[j].addAll(Arrays.asList(ancestors[i]));
            }
        }
    }
    return null;
}

这个想法很简单。我们假设 commitHashes 按降级顺序排列。我们找到字符串的最低和最高索引（哈希 - 不意味着）。很明显（考虑后代顺序）共同祖先只能在上索引之后（哈希中的较低值）。然后我们开始枚举提交的哈希并构建后代父链的链。为此，我们有两个哈希集由提交的最低和最高哈希的父母初始化。setOfAncestorsLower，setOfAncestorsUpper。如果下一个哈希提交属于任何链（哈希集），那么如果当前索引高于最低哈希的索引，那么如果它包含在另一个集合（链）中，我们返回当前哈希作为结果。如果不是，我们将其父项 (ancestors[i]) 添加到 hashset，它跟踪集合的祖先集合，当前元素包含在其中。

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

11 回答 11

Related

Reference