首页 文章

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

提问于
浏览 次
26

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

  • "A"是根（总是只有一个根）

  • 每个节点都知道其父节点

  • 节点名称是任意的 - 没有什么可以从它们推断出来

  • 我们从另一个来源得知节点是按照A到G的顺序添加到树中的（例如它们是版本控制系统中的提交）

Directed Acyclic Graph

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

  • B和E是B.

  • D和F是B.

注意：

algorithm graph directed-acyclic-graphs lowest-common-ancestor

10 回答

  • 1

    只是一些疯狂的想法 . 如何将两个输入节点用作根，并逐步同时执行两个BFS . 在某一步骤，当它们的BLACK集（记录访问节点）中存在重叠时，算法停止并且重叠的节点是它们的LCA . 通过这种方式，任何其他共同的祖先将具有比我们发现的更长的距离 .

    回复于
  • 0

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

    回复于
  • 8

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

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

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

    回复于
  • -2

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

    假设您想用x和y两个节点计算LCA（x，y） . 每个节点必须具有值 color 和 count ，resp . 初始化为白色和0 .

    • 将x的所有祖先颜色为蓝色（可以使用BFS完成）

    • 将y的所有蓝色祖先染成红色（BFS再次）

    • 对于图中的每个红色节点，将其父项' count 递增1

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

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

    DAG example where LCA can have two values

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

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

    回复于
  • 0

    如果图形具有周期，则松散地定义'ancestor' . 也许你的意思是DFS或BFS的树输出上的祖先？或者也许是'ancestor'你的意思是有向图中的节点最小化了来自 E 和 B 的跳数？

    如果你是're not worried about complexity, then you could compute an A* (or Dijkstra'的最短路径）从每个节点到 E 和 B . 对于可以同时到达 E 和 B 的节点，您可以找到最小化 PathLengthToE + PathLengthToB 的节点 .

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

    如果你只能去"up"树，那么我建议你从 E 执行BFS，并从 B 执行BFS . 图中的每个节点都有两个与之关联的变量：来自 B 的跃点和来自 E 的跃点 . 让 B 和 E 都具有图形节点列表的副本 . B 的列表按 B 的跃点排序，而 E 的列表按 E 的跃点排序 .

    对于 B 列表中的每个元素，尝试在 E 的列表中找到它 . 将匹配项放在第三个列表中，按 B 跳从 E 的跃点排序 . 在您耗尽 B 的列表后，您的第三个排序列表应该包含LCA . 这允许一个解决方案，多个解决方案（通过他们的BFS订购任意选择 B ），或者没有解决方案 .

    回复于
  • 1

    我也需要完全相同的东西，在DAG（有向无环图）中找到LCA . LCA问题与RMQ（范围最小查询问题）有关 .

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

    我发现THIS TUTORIAL细节和好 . 我也计划实施这个 .

    回复于
  • 0

    我提议O（| V | | E |）时间复杂度解决方案，我想这个方法是正确的，否则请纠正我 .

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

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

    步骤2：使用父级找到两个顶点的共同祖先，直到我们到达根顶点时复杂度 - 2 | v |

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

    所以，这是O（| V | | E |）时间复杂度算法 .

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

    回复于
  • 0

    http://www.gghh.name/dibtp/2014/02/25/how-does-mercurial-select-the-greatest-common-ancestor.html

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

    回复于
  • 5

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

    维护一组向量 - parents （存储每个节点的父节点） .

    • 首先做一个bfs（继续存储每个顶点的父节点）并找到x的所有祖先（找到x的父级并使用 parents ，找到x的所有祖先）并将它们存储在向量中 . 此外，将每个父项的深度存储在向量中 .

    • 使用相同的方法查找y的祖先并将它们存储在另一个向量中 . 现在，您有两个向量分别存储x和y的祖先及其深度 .

    • LCA将是具有最大深度的共同祖先 . 深度定义为距离根的最长距离（顶点与in_degree = 0） . 现在，我们可以按照深度的递减顺序对向量进行排序，并找出LCA . 使用这种方法，我们甚至可以找到多个LCA（如果有的话） .

    回复于
  • 0

    大家 . 请用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按降级顺序排序 . 我们找到字符串的最低和最高索引（哈希 - 并不意味着） . 显然（考虑后代顺序）共同的祖先只能在上指数之后（哈希中的较低值） . 然后我们开始枚举提交的哈希和构建后代父链的链 . 为此，我们有两个hashset由commit的最低和最高哈希的父项初始化 . setOfAncestorsLower，setOfAncestorsUpper . 如果下一个散列-commit属于任何链（hashsets），那么如果当前索引高于最低散列的索引，那么如果它包含在另一个集合（链）中，我们将返回当前散列作为结果 . 如果没有，我们将其父（祖先[i]）添加到hashset，它跟踪set的祖先集合，其中包含当前元素 . 基本上就是全部

    回复于

相关问题