寻找两个叶节点的最佳共同祖先，其中节点具有零个，一个或两个父母 [英] Finding best common ancestor of two leaf nodes where nodes have zero, one, or two parents

问题描述

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

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

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

如果父节点存在，节点就会引用父节点，并且引用所有子节点，所以如果它们存在，那么遍历树和树就是公平的游戏。节点可以有零个或多个孩子。改变数据结构不是一种选择。

接近两个输入节点的节点优于远离节点的节点（即更接近图的根节点） p>

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

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

参考资料

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

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

图表：

解决方案

我运行一个族谱网站，我已经用以下算法解决了这个问题。

对于这两个节点，使用递归生成一个将节点名称与生成关联的数组。用你的例子，b4比b5高出一代; b3是2代;

pre $ code $ 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; （$（$ d4Tree [$ nID]！= 0）和（（$ d4Tree [$ nID] + $）
 foreach（$ b5Tree as $ nID => $ gen）
 {
 （$ genSummedGen））
 {
 $ minSummedGen = $ d4Tree [$ nID] + $ gen; 
 $ minNodeID = $ nID; 
} 
} 
 return $ minNodeID; 
  

Goal:

I am looking for an algorithm to find the best common ancestor of a graph where nodes in the graph can have zero, one, or two parents. I am not sure of the terminology of "best common ancestor": better terminology might be "lowest common ancestor", or "recent common ancestor", etc. If there is better terminology then please provide URL's that describe such.

The algorithm has access to the full graph data structure.

It is possible for a given node to have zero, one, or two parents. This is key because the algorithms I've seen on the web assume that a given node has either zero or one parents, but not two parents (see references below). For instance, the m1 node in the diagram below has zero parents as it is the root (there can be multiple roots of the graphs). d3 has two parents, one is d2 and the other b2.

Nodes have references to both parents if they exist, and references to all children, if they exist, so traversal up the tree and down the tree is fair game. Nodes can have zero or more children. Changing the data structure is not an option.

Nodes closer to the two input nodes are preferable than nodes farther away (i.e., closer to roots of the graph).

By example, one possible graph is shown by the diagram given below. In this scenario, the inputs to the algorithm would be nodes b5 and d4. The best common ancestor of nodes b5 and d4 is b2. c2 would not be because b3 is in the lineage leading to b5.

Possible answers for the algorithm can be at most one node, and the empty set is a valid answer in the case that there is no common ancestor of the two input nodes.

Reference Material

Tarjan's off-line least common ancestors algorithm seems to imply zero or one parents, so if that is the solution, then the answer should include a description of how two parents are accounted for in that algorithm. The wikipedia page for Lowest common ancestor also seems to only account for data structures whose nodes have zero or one parents, not two:

In a tree data structure where each node points to its parent, ...

Diagram:

解决方案

I run a genealogy website, and I've solved this problem before with the following algorithm.

For both nodes, use recursion to generate an array which links node name with generation. Using your example, b4 is 1 generation above b5; b3 is 2 generations; 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, ...);

The base case is to check if the first node appears in the second's tree, and vice-versa. If it exists, then you have your answer.

Otherwise, iterate through one of the trees, finding common node IDs, and keeping track of the minimum generation.

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

这篇关于寻找两个叶节点的最佳共同祖先，其中节点具有零个，一个或两个父母的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！