DAG中多个节点的最小公共祖先

Question

如何在有向无环图中找到多个节点的最不常见祖先？

我已经找到了很多关于这个主题的论文，但它们似乎都在DAG中为两个节点找到了LCA。

有针对多个节点的好算法吗？

Answer 1

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

正如你可能知道的，有一种算法可以在每个查询的预处理为O（nlgn）和处理为O（1）的树中找到LCA，因此找到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）操作。

然而，这只适用于多树的DAG（或者，无菱形偏序集）。对于不具有多树/无菱形偏序集属性的一般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