广度优先遍历的使用（注释详尽版），代码一：

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
using namespace std;//LeetCode第127题
class Solution {
public:/** 字典wordId 给每个单词分配一个id，相当于一个微型数据库，在图中数字更好操作，所以这里的目的是建立从字符串到数字的映射关系 */unordered_map<string, int> wordId;/**//图的实现。edge[0]的列表表示id为0的字符串连通向哪些id//建图的时候如果直接对比两个字符串是否只相差一个字符，需要O(n^2)复杂度，所以采用一种优化建图的思路：利用中间状态//比如单词hit，我们让它指向"*it","h*t","hi*"三个模糊状态，同时让这三个模糊状态指向hit：hit-h*t,hit-*it,hit-hi*//这样在BFS时，从每个真正的单词发散出去的都是它的模糊状态，而从模糊状态一定可以得到其它可以一步变成它的单词//这样做有两个地方需要注意：一是步数其实是两倍，因为多遍历了一倍的模糊态。//二是从单词A到模糊态a后，模糊态a可以再发散到单词A(A在a通向的id列表中)，因此要跳过已经遍历过的单词*/vector<vector<int>> edge;/** nodeNum就是编号 */int nodeNum = 0;/** 如果字典wordId里面没有该字符串，则把该字符串加进去添加一个词到nodeNum映射容器wordId中，同时为这个nodeNum添加一个空的边集合（不指向任何id)*/void addWord(string& word) {if (!wordId.count(word)) {wordId[word] = nodeNum++;/** 加入了一个空的vector<int>数组!edges的索引跟id同步增加，所以一直是匹配的*/edge.emplace_back();}}/** 添加一个单词到id映射中，并建立它和模糊态的双向连接关系 */void addEdge(string& word) {addWord(word);/** 先取word对应的int值给id1 *//** id1是特定单词的编号，id2是模糊态的编号 */int id1 = wordId[word];/** 遍历word的每一个字符 */for (char& it : word) {char tmp = it;it = '*';addWord(word);int id2 = wordId[word];//建立单词和模糊态的双向连接关系edge[id1].push_back(id2);edge[id2].push_back(id1);//将模糊态恢复成原单词it = tmp;}}/** 开始BFS */int ladderLength(string beginWord, string endWord, vector<string>& wordList) {/** 遍历输入的数组里面的字符串 */for (string& word : wordList) {addEdge(word);}addEdge(beginWord);if (!wordId.count(endWord)) {return 0;}//这里不能用一个step变量记录当前经历了几步，因为遍历是按具体单词 -> 模糊态 ->具体单词这样的层级，//在从模糊态到具体单词时，有可能遍历到上一层已遍历过的单词。/**所以用一个数组记录从起始态到某个单词经历了多少次变动*///nodeNum是一个计数器，这里nodeNum刚好是算上模糊态的所有词总数/**由于一共只有nodeNum个词，步数不可能大于nodeNum*/vector<int> dis(nodeNum, INT_MAX);int beginId = wordId[beginWord], endId = wordId[endWord];//说明是访问过了begin的单词dis[beginId] = 0;queue<int> que;que.push(beginId);//从beginWord这个状态开始，向下逐层BFSwhile (!que.empty()) {int x = que.front();que.pop();if (x == endId) {//除以2的原因是多遍历一倍的模糊态层数，/** +1是因为题意要求转换序列的长度，而不是转换次数 *///所以转换次数显然不用加1return dis[endId] / 2 + 1;}//遍历当前单词nodeNum连接到的每个状态//遍历特定word对应序号的边数组/** 本质上是一层一层遍历，每一层的编号dis[xxx]是一样的 */for (int& it : edge[x]) {if (dis[it] == INT_MAX) {//是没遍历过的状态//dis[it]是对应模糊态的worddis[it] = dis[x] + 1;que.push(it);}}}return 0;}
};int main(){string beginWord;string endWord;string tmp;vector<string> wordList;cin >> beginWord >> endWord;while (cin >> tmp) {wordList.emplace_back(tmp);}Solution sol;int ans = sol.ladderLength(beginWord, endWord, wordList);cout << ans << endl;return 0;
}

输入：

hit
cog
hot dot dog lot log cog
Z

输出：

5

代码二（126题）：

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<queue>
using namespace std;class Solution {
public:vector<vector<string>> findLadders(string beginWord, string endWord, vector<string> &wordList) {vector<vector<string>> res;// 因为需要快速判断扩展出的单词是否在 wordList 里，因此需要将 wordList 存入哈希表，这里命名为「字典」/** dict里面存的就是vector里面的字符串 */unordered_set<string> dict = {wordList.begin(), wordList.end()};// 修改以后看一下，如果根本就不在 dict 里面，跳过/** set的find函数如果找不到目标则返回end */if (dict.find(endWord) == dict.end()) {return res;}// 特殊用例处理，删除指定元素dict.erase(beginWord);//第 1 步：广度优先遍历建图//记录扩展出的单词是在第几次扩展的时候得到的，key：单词，value：在广度优先遍历的第几层/** 为什么要加两个大括号呢？map的形式是这样子的：{{}，{}，{}，{}} */unordered_map<string, int> steps = {{beginWord, 0}};//记录了单词是从哪些单词扩展而来，key：单词，value：单词列表，这些单词可以变换到 key ，它们是一对多关系unordered_map<string, set<string>> from = {{beginWord, {}}};//step是层数int step = 0;bool found = false;/** q的初始化就先放一个beginWord进去 */queue<string> q = queue<string>{{beginWord}};int wordLen = beginWord.length();while (!q.empty()) {step++;int size = q.size();for (int i = 0; i < size; i++) {/** 等价于 string currWord = q.front(); *///那加上move是为了什么呢//std::move并不能移动任何东西，它唯一的功能是将一个左值强制转化为右值引用，继而可以通过右值引用使用该值，//以用于移动语义。从实现上讲，std::move基本等同于一个类型转换：static_cast<T&&>(lvalue);//std::move是为性能而生。//std::move是将对象的状态或者所有权从一个对象转移到另一个对象，只是转移，没有内存的搬迁或者内存拷贝。const string currWord = move(q.front());string nextWord = currWord;q.pop();//将每一位替换成 26 个小写英文字母/** 注意注意，这里是每一位都要替换成26个小写的英文字母 */for (int j = 0; j < wordLen; ++j) {/** 依次取字符串的每一个字母赋值给origin *//** origin用于保存这个字母 */const char origin = nextWord[j];for (char c = 'a'; c <= 'z'; ++c) {nextWord[j] = c;if (steps[nextWord] == step) {from[nextWord].insert(currWord);}if (dict.find(nextWord) == dict.end()) {continue;}// 如果从一个单词扩展出来的单词以前遍历过，距离一定更远，为了避免搜索到已经遍历到，且距离更远的单词，需要将它从 dict 中删除dict.erase(nextWord);// 这一层扩展出的单词进入队列q.push(nextWord);// 记录 nextWord 从 currWord 而来from[nextWord].insert(currWord);// 记录 nextWord 的 stepsteps[nextWord] = step;if (nextWord == endWord) {found = true;}}nextWord[j] = origin;}}if (found) {break;}}// 第 2 步：深度优先遍历找到所有解，从 endWord 恢复到 beginWord ，所以每次尝试操作 path 列表的头部if (found) {/** 开个Path来记录路径 */vector<string> Path = {endWord};dfs(res, endWord, from, Path);}return res;}void dfs(vector<vector<string>> &res, const string &Node, unordered_map<string, set<string>> &from,vector<string> &path) {if (from[Node].empty()) {/** 首先res存入了一个数组，其次这里使用的是逆序迭代器 */res.push_back({path.rbegin(), path.rend()});return;}for (const string &Parent: from[Node]) {path.push_back(Parent);dfs(res, Parent, from, path);path.pop_back();}}
};int main(){string beginWord;string endWord;string tmp;vector<string> wordList;cin >> beginWord >> endWord;while (1) {cin >> tmp;if(tmp=="Z")break;wordList.emplace_back(tmp);}Solution sol;vector<vector<string>> ans=sol.findLadders(beginWord,endWord,wordList);for(auto& vec:ans){for(auto ele:vec){cout<<ele<<" ";}cout<<endl;}return 0;
}

输入：

hit
cog
hot dot dog lot log cog Z

输出：

hit hot dot dog cog
hit hot lot log cog

我是花花，祝自己也祝您变强了~