Многовальные деревья и структуры

Question

У меня проблема в прикладной математике, которая может быть почти идеально сопоставлена ​​с поиском самого длинного пути в многодорожечном дереве.

У меня есть функция child(), которая дает дочерние узлы (точки в пространстве, удовлетворяющие условию). Единственное предостережение в том, что child() требует, чтобы все предыдущие узлы подключались к нему, включая корневой узел. Именно здесь я изо всех сил пытаюсь написать свой код рекурсивно. До сих пор у меня есть что-то вроде ниже.

def multitree(node): 
    tmp_list = child(node) 
    for child2 in tmp_list: 
      if len(child(child2)))==0:  #if you hit a leaf (dead end), go to next element 
       continue 
      else: 
       multitree(child2) 

Но на данный момент я не уверен, что вернуть. Я по существу хочу отобразить все дерево многодорожечных деревьев, пока не дойду до листа для всего. Любые идеи или советы? Спасибо, парни.

редактировать:

Update 1: Для полноты, я набросала примерное представление о том, что требует ввода ребенка(): https://i.imgur.com/3MkfsYc.png В основном, чтобы найти дочерние узлы узла, отмеченного стрелкой ребенка (в) требует список узлов между корнем и самим узлом, то есть узлы, отмеченные красной точкой.

Update 2:

Я написал ребенок (узел), как показано ниже, и я в настоящее время работает над этим -

def pathwalk(node): 

    children = child(node) 
    paths = [child(node.append(kid)) for kid in children] 

    return paths 

Answer 1

Вы можете сделать что-то вроде этого, чтобы получить только самый длинный путь. Здесь он получает вам список узлов, откуда можно извлечь любую соответствующую информацию:

def longest_path(node): 
    children = child(node) 

    if not children: # leaf node 
     return [node] 

    children_vals = [longest_path(c) for c in children] 
    longest = max(children_vals, key=len) 
    return [node] + longest 

не обрабатывает связи, или, скорее, выбирает один вариант произвольно.

(примечание: полупрофессиональный)

Answer 2

Я думаю, что нашел проблему. Поскольку я хотел сохранить список всех узлов, на которых вы находите детей (вы отслеживаете путь, по которому вы идете, см. Imgur pic). Я редактировал процедуру Illuvatar, добавляя

children_vals = [longest_path(node+[c]) for c in children] 

Таким образом, вы рекурсивно объединяете каждого родителя с его дочерним элементом.