3

目标：

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

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

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

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

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

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

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

参考资料

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

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

图：

图表

4

1 回答 1

1

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

对于这两个节点，使用递归生成一个将节点名称与生成链接的数组。使用您的示例， b4 比 b5 高 1 代；b3为2代；ETC：

$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;
于 2011-05-25T00:10:27.680 回答