如何基于存储亲子关系的字典查找多个姓名的最近共同祖先

• 为每个输入姓名生成从自身到顶层祖先的序列，按亲缘从近到远排序
• 提取所有序列的交集，得到所有输入人员的共同祖先
• 遍历第一个人的祖先序列，找到第一个出现在所有其他序列中的节点，即为最近共同祖先
• 兼容处理输入姓名不足2个、姓名不在家谱中、无共同祖先的异常场景

# 辅助函数：获取单个姓名的所有祖先序列，按亲缘从近到远排列
def get_ancestor_chain(name, family_tree):
    chain = []
    current = name
    while current:
        chain.append(current)
        # 找不到父节点则终止，已到顶层祖先
        current = family_tree.get(current)
    return chain

def ancestors(names, Family_tree):
    # 输入人数不足2直接返回
    if len(names) < 2:
        return None
    # 校验所有输入姓名是否存在于家谱中
    all_nodes = set(Family_tree.keys()).union(set(Family_tree.values()))
    for name in names:
        if name not in all_nodes:
            return None
    # 生成所有输入姓名的祖先链
    ancestor_chains = [get_ancestor_chain(name, Family_tree) for name in names]
    # 遍历第一条链的节点，找第一个所有链共有的节点
    for candidate in ancestor_chains[0]:
        is_common = True
        for chain in ancestor_chains[1:]:
            if candidate not in chain:
                is_common = False
                break
        if is_common:
            return candidate
    # 无共同祖先返回None
    return None

# 给定的家谱数据
Family_tree = { 
    'Steven': 'Mike',       'Josh': 'Mike', 
    'Mike': 'Jackson',      'Jackson': 'Greg', 
    'Drake': 'Bob',         'Greg': 'Calvin',
    'Bob': 'Greg',          'Nathalie':'Amber',
    'Amber': 'Jodie',       'Jodie': 'Calvin',
    'Erick': 'Vincent',     'Vincent': 'Jodie',
    'Emily': 'Sherri',      'Sherri': 'Jodie',
    'Keagan': 'Sherri'
}

# 测试1：两个直系兄弟的最近共同祖先
print(ancestors(['Steven', 'Josh'], Family_tree)) 
# 输出结果：Mike

# 测试2：两个分支成员的最近共同祖先
print(ancestors(['Drake', 'Steven'], Family_tree))
# 输出结果：Greg

# 测试3：三个不同分支成员的最近共同祖先
print(ancestors(['Nathalie', 'Erick', 'Emily'], Family_tree))
# 输出结果：Jodie

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