Skip to main content
 首页 » 编程设计

python之使用 BFS 查找最长路径

2025年04月02日9over140

我有一个包含 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) 

请您参考如下方法:

IIUC,这不能保证有效(事实上,您可以构建无效的案例)。

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

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

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