我想找到字梯给定字典的最大长度。 A 词梯是一个单词序列，每个单词只有一个位置与前一个单词不同。如何找到最大的词梯？
我要实现以下算法：
map，其中每个单词映射到换句话说，从它的不同之处仅在一个位置（在此map是作为邻接表实现的曲线图）map（使用bfs）我想算法的工作原理。现在我想知道从性能角度来看它是否是最佳的。你会如何优化它？
对我们的问题的答案差异很大，取决于你要求的东西。
您在此处发布的算法会为您提供一对单词，它们之间的词汇梯度最短。这被称为字图的直径的。如果你想找到这个，你在这里的方法应该没问题。
如果您想要在字典中找到最长的单词梯（即您想要查找一次只能相差一个字母的最长单词链），那么如果您将单词梯级排除在外他们的问题是NP难（通过减少哈密尔顿路径问题），这意味着可以推测没有有效的算法来解决问题。你可能不得不通过列出所有可能的单词阶梯来蛮力搜索他的单词列表。不幸的是，这在任何大小合适的字典中都是完全不可行的，因此会有一些明显荒谬的梯子可供尝试。
总之，如果你正在寻找图形直径，你的解决方案是相当不错的。如果你正在寻找实际最长的词梯，那么你很可能永远无法得到答案，因为搜索空间太大，而且这个问题在理论上是困难的。
希望这会有所帮助！
只是为了好玩，这里有一种计算图形直径的方法，对于有几条非常长的最短路径的稀疏图可能会更快。
1）计算图的最小生成树。
2）最小生成树的直径可以在两个BFS中找到。从树上的任意点开始第一个。从第一点开始，从树中最远点开始第二点。这是有效的，因为如果将任意根分配给树，则直径是距离根的两个最长距离的总和，并且您的第一个BFS会找到其中的一个。
3）沿最小生成树直径的中点分配一个相当任意的根。从点X开始的直径的上限是距该根的X的距离与任何节点与该根的最大距离之和。这只是一个上限，因为两个节点之间的最短距离不一定跟随最小生成树。
4）BFS是否从最小生成树中的根节点开始，按照它们与根的距离不递增的顺序进行搜索。在每次搜索的开始处，您都有一个从该节点开始的图直径树的上界。当上限不大于目前发现的最大直径时，您可以停止执行BFS搜索。
有一个全面实施的Mathematica这一任务的，背景信息在
http://blog.wolfram.com/2012/01/11/the-longest-word-ladder-puzzle-ever/
*嗅嗅*我发现“学校”的气息和“功课”周围飘出一股淡淡的.. –
最大长度和最大最短路径是两个完全不同的东西。你想要什么？ – Ishtar
如果我的判断正确，那么您就错过了阶梯中单词顺序的重要性。 [歌声 - 去] vs [龚歌]。取决于单词的顺序，长度将会更高或更低，而不仅仅是从每个单词到其他单词的映射。 – daniloquio