用BF查找最长路径

Question

我有一张单子，有794个三个字母长的单词。我的任务是找到一个单词的最长路径。在

定义（子级）：
父词的子词是只替换一个字母的父词。在

示例：
‘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.

我的想法是，这将给我们提供最长的路径，因为我们继续产生新的孩子，直到我们用尽可能的孩子（也就是说，还没有访问过的孩子）。在

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

---

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

编辑
因为树和列表可能有点慢，所以我用集合替换它们。在

^{pr2}$

Answer 1

IIUC，这并不能保证有效（事实上，你可以在不起作用的地方构建案例）。在

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

假设当您迭代a的子对象时，您在c之前遇到b。处理b并将其标记为已访问。在某个时候，你会遇到c，并最终重新考虑b。然而，的算法被认为是短的。在

你也不能去掉“已访问”标记，因为图表背后的故事清楚地表明它不是一个DAG。如果删除“访问”逻辑，将遇到无限循环。在