家族树中最近共同祖先的查找算法实现技术问询

问题背景 #

现有人员对象格式如下：

{
  id: 444,
  ancestors: [
    { id: 142, father: 837, mother: 221, children: [ 844, 371, 473, 113 ] },
    // 更多数据...
  ]
}

已实现多人共同祖先的查找逻辑：

const allAncestors = people.map(({ ancestors }) => ancestors).flat(1);
const commonAncestors = allAncestors.filter(({ id }) => {
  for (const person of persons) {
    if (!person.ancestors.find(ancestor => ancestor.id === id)) 
      return false;
  }
  return true;
});

但不清楚如何查找最近的共同祖先，此处“最近”指代际（两人间的步数）最少，仅纵向遍历树，不进行横向遍历。

解决方案 #

要找到最近的共同祖先，核心是计算每个共同祖先到目标人员的代际距离，再筛选出符合“代际最少”定义的祖先。具体步骤如下：

1. 为每个人员建立祖先-代际映射 #

先给每个目标人员的祖先标注代际步数（自己为0，父母为1，祖父母为2，以此类推）。注意需确保ancestors数组是按代际从近到远排序的：

// 生成每个人员的祖先代际映射表，key为祖先id，value为代际步数
const personAncestorGenerations = people.map(person => {
  const generationMap = new Map();
  // 若不需要将自身纳入祖先范围，可删除此行
  generationMap.set(person.id, 0);
  // 遍历祖先数组，按索引+1赋值代际（前提是数组从近到远排序）
  person.ancestors.forEach((ancestor, index) => {
    generationMap.set(ancestor.id, index + 1);
  });
  return generationMap;
});

2. 计算每个共同祖先的代际指标 #

遍历已找到的共同祖先，计算两类核心指标：

• 总代际步数：所有目标人员到该祖先的代际距离之和
• 最大代际步数：所有目标人员到该祖先的最远代际距离（更贴合“最近共同祖先”的常规定义）

// 去重共同祖先id，避免重复计算
const uniqueCommonAncestorIds = new Set(commonAncestors.map(anc => anc.id));

// 计算每个共同祖先的代际指标
const ancestorScores = Array.from(uniqueCommonAncestorIds).map(ancestorId => {
  const generations = personAncestorGenerations.map(map => map.get(ancestorId));
  const totalGeneration = generations.reduce((sum, gen) => sum + gen, 0);
  const maxGeneration = Math.max(...generations);
  return {
    ancestorId,
    totalGeneration,
    maxGeneration
  };
});

3. 筛选最近的共同祖先 #

根据需求选择筛选规则：

• 按总代际步数最少筛选：

const closestByTotal = ancestorScores.sort((a, b) => a.totalGeneration - b.totalGeneration)[0];
const closestAncestorByTotal = commonAncestors.find(anc => anc.id === closestByTotal.ancestorId);

• 按最大代际步数最少筛选（推荐）：

const closestByMax = ancestorScores.sort((a, b) => a.maxGeneration - b.maxGeneration)[0];
const closestAncestorByMax = commonAncestors.find(anc => anc.id === closestByMax.ancestorId);

注意事项 #

• 如果ancestors数组未按代际排序，需先通过递归/迭代构建每个人员的祖先层级树，再计算代际步数。
• 若存在多个祖先的代际指标相同，可根据需求返回所有符合条件的祖先。

内容的提问来源于stack exchange，提问作者GirkovArpa