Python, вычисляя глубину генеалогического древа от одного члена к другому

Question

У меня есть словарь с данными древовидной структуры (ключ - имя человека, его ценность - дети). Я хотел бы рекурсивно получить глубину от одного данного члена к другому (get_depth (from_person, to_person)).

Answer 1

Я бы выбрал DFS, так как он облегчает отслеживание глубины.

def get_depth(root, target): 
    if root == target: 
     return 0 
    if not d[root]: 
     return None 
    for child in d[root]: 
     depth = get_depth(child, target) 
     if depth is not None: 
      return 1 + depth 
    return None 

return Последнего, строго говоря, не нужен, но я предпочитаю по буквам этих вещей. Не стесняйтесь задавать любые вопросы, но это должно быть достаточно понятным. Вы можете чувствовать себя более комфортно заменить None с -1, а затем проверить if depth >= 0