algorithm - Least common ancestor of multiple nodes in DAG

Question

How can I find a least common ancestors of multiple nodes in a directed acyclic graph?

I've found quite a few papers on the topic but they all seem to find LCAs in DAG for two nodes.

Are there good algorithms for multiple nodes?

Answer 1

也许您可以修改用于树的算法，使其也适用于 DAG。

如您所知，有一种算法可以在树中找到 LCA，每个查询的预处理为O(nlgn)，过程为O(1) ，因此找到k个节点的 LCA 需要O(k)。可以在此处找到有关此算法的更多详细信息。

Answer 2

正如@DennisMeng、@vzn 和@user824425 已经在评论中指出的那样，在某些情况下（！）可以通过（二进制）LCA 运算符的成对递归应用来计算两个以上节点的 LCA ，例如：

lca(A, B, C, D) = lca(A, lca(B, lca(C, D)))

在函数式编程中，这基本上等同于reduce（或fold）操作。

但是，这仅适用于作为Multitrees的 DAG （或者，或者，无菱形组合）。对于不具有多树/无菱形 poset 属性的一般 DAG，不幸的是，这种方法不起作用。

考虑以下表示具有多重继承特征的类层次结构的 DAG（所有边都从底部指向顶部；X表示两个有向边的交叉）：

        Any
       /   \
  Boolean Value 
      |  X  |  \
    False True Unknown

值得注意的是，True和False节点都有两个直系祖先，Boolean和Value。这里的第一个问题是这需要一个可以返回多个节点的 LCA 运算符，例如JGraphT的getLCASet。现在，假设我们要计算 { False, True, Unknown} 的 LCA：通过简单地查看图形，很明显它Value是所有三个节点的直接祖先。直接成对归约不再适用，因为二元getLCASet运算符可以返回多个节点，但可以想象，可以使用类似堆栈的方法，将计算的祖先推回节点列表。但是，这不会产生正确的结果，例如：

  True, False, Unknown
     \   /
     (LCA)
     /   \
Boolean, Value, Unknown
     \   /
     (LCA)
       |
      Any, Unknown
        \   /
        (LCA)
          |
         Any