BFS, versucht den längsten Weg zwischen Knoten zu finden

Question

Momentan arbeite ich mit einer Zuweisung (BFS), wo ich den längsten Weg zwischen zwei Knoten finden soll. Beachten Sie, dass ich sowohl mit einer Queue-Klasse als auch mit einer Node-Klasse arbeite. Die Node-Klasse heißt Word in meiner Zuweisung. Die Wörter sind Wörter mit drei Buchstaben, und ich habe derzeit eine Methode (longestway), die den längsten Pfad von einem gegebenen Wort zu seinem kleinsten Kind zurückgibt.

Das Problem ist, ich möchte dies implementieren, so dass es den längsten Pfad von einem Wort in einer Liste zu seinem kleinsten Kind zurückgibt, und dann den längsten aller dieser Pfade zurückgibt.

Der Code, den ich gerade habe, funktioniert, aber es dauert viel zu lange Zeit, ich brauche Hilfe, um dieses zu beschleunigen.

Mein Code sieht derzeit wie folgt aus:

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 arbeitet derzeit in Ordnung, aber ordpar nimmt viel zu lange laufen zu lassen, und ich brauche Hilfe, um es zu beschleunigen.

Answer 1

Ein guter Anfang wäre, die Elemente aus dem Kopf der Liste zu entfernen, da Sie nur drucken und eine Offset-Variable einfügen. Außerdem rufen Sie zweimal mit demselben Argument printpath1 auf und machen doppelt so viele Berechnungen wie erforderlich.

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