BFS, пытаясь найти самый длинный путь между узлами

Question

В настоящее время я работаю с назначением (BFS), где я должен найти самый длинный путь между двумя узлами. Обратите внимание, что я работаю как с классом очереди, так и с узловым классом, класс node называется Word в моем задании. Слова являются 3-буквенными словами, и в настоящее время у меня есть метод (longestway), который возвращает самый длинный путь от данного слова до его самого маленького ребенка.

Проблема заключается в том, что я хочу реализовать это, чтобы он возвращал самый длинный путь из любого слова в списке до самого маленького его потомка, а затем возвращает самый длинный из всех этих путей.

Код, который у меня есть сейчас, работает, но он проходит слишком долго, мне нужна помощь, чтобы ускорить это.

Мой код в настоящее время ищет, как это:

def printpath1(start): 
    ordet=longestway(setlista(),start) 
    path=[] 
    p=ordet 
    while p is not None: 
     path.append(p.ordet) 
     p=p.parents 
    path.reverse() 
    #print (path) 
    return len(path) 


def ordpar(lista): 
    s=lista 
    a=[] 
    for elem in s: 
     if a[0]<printpath1(elem): 
      a.pop(0) 
      a.append(printpath1(elem)) 
    print(a) 

printpath1 в настоящее время работает нормально, но ordpar принимает слишком много времени, чтобы работать, и мне нужна помощь, чтобы ускорить его.

Answer 1

Хорошим началом было бы прекратить удаление элементов из заголовка списка, поскольку все, что вы делаете, это печать и ввод смещения. Кроме того, вы вызываете printpath1 дважды с тем же аргументом, делая в два раза больше необходимых вычислений.

offset = 0 
for elem in lista: 
    pp1 = printpath1(elem) 
    if a[offset] < pp1: 
     a.append(pp1) 
     offset += 1 
print(a[offset::])