查找两个叶节点的最佳公共祖先，其中节点有零个、一个或两个父节点

Question

目标：

我正在寻找一种算法来找到图的最佳共同祖先，其中图中的节点可以有零个、一个或两个父节点。我不确定“最佳共同祖先”的术语：更好的术语可能是“最低共同祖先”或“最近共同祖先”等。如果有更好的术语，请提供描述此类术语的 URL。

该算法可以访问完整的图数据结构。

给定节点可能有零个、一个或两个父节点。这是关键，因为我在网上看到的算法假设给定节点有零个或一个父节点，但没有两个父节点（请参阅下面的参考资料）。例如，下图中的 m1 节点有零个父节点，因为它是根（图中可以有多个根）。 d3 有两个父母，一个是 d2，另一个是 b2。

节点具有对双亲（如果存在）的引用，以及对所有子节点（如果存在）的引用，因此向上和向下遍历树是公平的游戏。节点可以有零个或多个子节点。改变数据结构不是一个选择。

靠近两个输入节点的节点比距离较远的节点（即，更靠近图的根）更可取。

例如，下图显示了一种可能的图表。在这种情况下，算法的输入将是节点 b5 和 d4。节点 b5 和 d4 的最佳公共祖先是 b2。 c2 不会，因为 b3 属于通向 b5 的谱系。

该算法的可能答案最多只能是一个节点，并且在两个输入节点没有共同祖先的情况下，空集是有效答案。

参考资料

Tarjan 离线最不常见祖先算法 似乎意味着零个或一个父母，所以如果这是解决方案，那么答案应该包括如何在该算法中考虑两个父母的描述。 最低共同祖先的维基百科页面似乎也只考虑节点具有零或零的数据结构一位父母，而不是两位：

在树形数据结构中，每个 节点指向其父节点，...

图表：

Answer 1

我经营一个家谱网站，我之前用以下算法解决了这个问题。

对于两个节点，使用递归生成一个数组，该数组将节点名称与生成链接起来。以您的示例为例，b4 是 b5 的 1 代； b3为2代；等：

$b5Tree = array('b4'=>1, 'b3'=>2, 'c3'=>2, 'b2'=>3, 'c2'=>3, ...);
$d4Tree = array('d3'=>1, 'b2'=>2, 'd2'=>2, 'b1'=>3, 'd1'=>3, ...);

基本情况是检查第一个节点是否出现在第二个树中，反之亦然。如果它存在，那么你就有了答案。

否则，迭代一棵树，查找公共节点 ID，并跟踪最小代。

$minNodeID = null;
foreach ($b5Tree as $nID => $gen)
{
    if (($d4Tree[$nID] != 0) and (($d4Tree[$nID]  + $gen) < $minSummedGen))
    {
        $minSummedGen = $d4Tree[$nID] + $gen;
        $minNodeID = $nID;
    }
}
return $minNodeID;