转自 LeetCode 127. Word Ladder - 简书
这道题是经典的广度有优先搜索的例子，也是Dijkstra's algorithm的变形。
以题目给出的例子为例，其实就是在所有路径的权重都为1的情况下求出下列无向图中从节点hit到节点cog的最短路径：
Paste_Image.png
PS：图中相互之间只相差一个字母的单词都是相邻节点。
利用BFS算法，维持两个集合： visited 和 wordSet
Paste_Image.png
从hit开始出发，找到唯一的相邻节点：hot, 把它放进visited中,第一次循环结束。 PS： 所谓找到相邻的节点，在题目中就是找出和该单词之相差一个字母的所有单词。请看最后代码的详细实现。
Paste_Image.png
查看hot节点的所有相邻节点（已经被访问过的hit除外），找到lot和dot, 放进visited中。第二次循环结束。
Paste_Image.png
找出新家进来的lot和dot的未被访问的相邻节点，分别是log和dog放进visited中。第三次循环结束。
Paste_Image.png
找出log的未被访问的相邻节点cog，放进结合中。第四次循环结束。由于cog就是endWord，任务结束，跳出循环。
Paste_Image.png
这里总共经历了四次循环，每循环一次，其实就是从beginWord想endWord变化的一步，因此循环的次数（加上1）就是从beginWord想endWord转变经历的 number of steps。
