BFSで最長のパスを探す

Question

私は794の3文字の長文のリストを持っています。私の任務は、与えられた単語への最長経路を持つ単語を見つけることです。

定義（子供）：親ワードに
子供は親1と単語と置き換えるだけで1つの文字です。

例：
「することができます」、（それらの単語がリストに存在していることを与えられた）単語「走り」への子であるエトセトラ「RUN」、「ラップ」。

定義（パス）：
パスは、各単語が前に単一の文字を交換することにより生成された一連の単語です。

#Pseudo code 
Given a word 
    Put the word in a queue 
    Keep a list with all visited words 
    As long as the queue is not empty 
     Get the first word in the queue 
     Generate a list with all the children to this word 
     For every children in that list 
      If the child is not in the list of visited words 
       Append the child to the list of visited words 
       Put the child in the queue 
    Print the path to the last grandchild. 

私の考えでは、我々は我々が（すでに訪問されていないことがあり、子供）の可能な子どもを使い果たすまで、新しい子を生成し続けるので、これは最長パスを与えるということです。

質問：
私の考えは有効ですか？実際に動作するかどうかをテストするにはどうすればよいですか？

---

実際のコードは以下で見ることができますが、コメントなしでは意味をなさない可能性があります。

編集
ツリーとリストは少し遅くなる可能性があるので、それらをセットに置き換えました。

from Queue import Queuenode; import Bintree 
with open('word3',encoding='utf-8') as f: 
    lista=f.readlines() 
    lista=[x.strip('\n') for x in lista] 
alfabet='abcdefghijklmnopqrstuvwxyzåäö' 
class Word: 
    def __init__(self, w, f = None): 
     self.word = w 
     self.parent = f 
children=Bintree.Bintree() 
for i in lista: 
    children.put(i) 
def barn(far): 
    barnlista=[] 
    for i in range(3): 
     for j in range(29): 
      empty='' 
      empty+=far[0:i]+alfabet[j]+far[i+1:] 
      if empty!=far and children._exists(empty): 
       barnlista+=[empty] 
    return barnlista 
ko=Queuenode() 
def vag(item): 
    start=item 
    counter=0 
    while start!=None: 
     counter+=1 
     print(start.word) 
     start=start.parent 
    print(counter) 
def bfsx(startord): 
    ko.put(Word(startord)) 
    besokta=[startord] 
    while not ko.isempty(): 
     first=ko.get() 
     lista=barn(first.word) 
     for child in lista: 
      if child not in besokta: 
       besokta+=[child] 
       ko.put(Word(child,first)) 
    vag(first) 

Answer 1

IIUCでは、これは動作することが保証されていません（実際にはそうでないケースを構築することができます）。

ノードから開始して、とします。直接経路があります。→ bです。直接経路→cと間接経路c ⇒bもあります。

あなたがの子供を反復するとき、あなたはC前Bが発生したと仮定します。 bを処理し、訪問したとマークします。ある時点でcが発生し、最終的にはbを再考します。あなたのアルゴリズムは短いサブパス→ Bではなく、長い1 → C ⇒ B検討していきますので、その時点で、しかし、Bはすでに、訪問したと考えられています。

グラフの背後にある物語がDAGではないことを明確にしているので、「訪問済み」マークも取り除くことはできません。 「訪問済み」ロジックを削除すると、無限ループに遭遇します。