python - 使用 BFS 查找最长路径

Question

我有一个包含 794 个三字母长单词的列表。我的任务是找到给定单词的最长路径的单词。

定义( child ):
父词的子词是只替换了一个字母的父词。

示例:
“can”、“run”、“rap”等都是单词“ran”的子词(假设这些单词存在于列表中)。

定义(路径):
路径是一系列单词，其中每个单词都是通过交换前一个字母生成的。

#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.

我的想法是，这将给出最长的路径，因为我们会继续生成新的 child ，直到用完可能的 child (即尚未访问过的 child )。

问题:
我的想法有效吗？我如何测试它是否真的有效？

---

实际代码可以在下面查看，但如果没有注释，可能没有任何意义。

编辑
由于树和列表可能有点慢，我用集合替换了它们。

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，这不能保证有效(事实上，您可以构建无效的案例)。

假设您从节点 a 开始；存在一条直接路径a → b；还有一个直接路径 a → c 和一个间接路径 c ⇒ b。

假设当您遍历 a 的子级时，您在 c 之前遇到了 b。您处理 b 并将其标记为已访问。稍后您会遇到 c，并最终再次考虑 b。然而，此时 b 已被视为已访问，因此您的算法将考虑较短的子路径 a → b 而不是较长的子路径 a → c ⇒ b 。

您也不能去掉“已访问”标记，因为图表背后的故事清楚地表明它不是 DAG。如果去掉“已访问”逻辑，就会遇到死循环。