相关疑难解决方法(0)

想象一下有向无环图如下,其中:

• "A"是根(总有一个根)
• 每个节点都知道它的父节点
• 节点名称是任意的 - 没有什么可以从它们推断出来
• 我们从另一个来源得知节点是按照A到G的顺序添加到树中的(例如它们是版本控制系统中的提交)

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

• B和E是B.
• D和F是B.

注意:

• 从根开始到给定节点不一定有一条路径(例如"G"有两条路径),因此您不能简单地遍历从根到两个节点的路径并查找最后一个相等的元素
• 我发现树的LCA算法,特别是二叉树,但它们不适用于此,因为一个节点可以有多个父节点(即这不是一棵树)