BFS - WordChain/Wordladder

Question

我需要帮助解决一个问题。我想找出某个词和某个给定词尾之间最长的最短路径。所有单词的长度都是4。我有一个图，其中每个节点代表一个单词，每个单词在一个位置上的不同是连接的。

我有一个清单，上面有所有的单词。我有一个正确的函数，它找到最长的最短路径，但它从单词列表中的每个单词开始，然后从单词列表中的每个单词执行BFS。

如果给出一些结尾词，我如何才能找到到给定词尾的最短路径的单词？

所谓最长的最短路径，我指的是从所有单词到结束词的最短路径，以及其中最长的路径。

--我怎么能用一个BFS ?来完成这个任务？

谢谢

Answer 1

当执行宽度优先搜索时，您可以标记图中的每个节点与源节点的距离(最短路径的长度)。因为字梯是可逆的，你可以试着从尾词开始进行宽度优先搜索，用离结束词有多远的啤酒花标记每个单词。当你这样做的时候，你可以跟踪你发现的单词，这个词离单词的开头越远越好。一旦完成，您就可以将该单词输出为一个与起始单词尽可能远的单词。

希望这能有所帮助！