首页 文章

找到两个叶节点的最佳共同祖先，其中节点具有零个，一个或两个父节点

提问于
浏览 次
2

Goal ：

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

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

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

如果节点存在，节点就会引用父节点，并且如果它们存在则引用所有子节点，因此遍历树和树下是合理的游戏 . 节点可以有零个或多个子节点 . 更改数据结构不是一种选择 .

更靠近两个输入节点的节点优选地比距离更远的节点（即，更接近图的根）更好 .

例如，下面给出的图表显示了一个可能的图表 . 在这种情况下，算法的输入将是节点b5和d4 . 节点b5和d4的最佳共同祖先是b2 . c2不会是因为b3在通向b5的血统中 .

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

Reference Material

Tarjan's off-line least common ancestors algorithm似乎暗示零或一个父母，所以如果这是解决方案，那么答案应该包括对该算法中如何计算两个父母的描述 . Lowest common ancestor的维基百科页面似乎也只考虑其节点有零个或一个父节点而不是两个节点的数据结构：

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

Diagram ：

graph diagram

graph ancestor least-common-ancestor

1 回答

  • 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;
    回复于

相关问题