我想找到字梯給定字典的最大長度。 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