c++ - BFS中队列大小的重要性

Question

我正在尝试在 Leetcode 上解决以下问题:https://leetcode.com/problems/word-ladder/description/ 。问题是:

Given two words (beginWord and endWord), and a dictionary wordList, we have to find the length of the shortest transformation sequence from beginWord to endWord such that every intermediate word is in the dictionary, and at each step we can change only one letter. Thus, if beginWord='hit' and endWord is 'cog', and dict has ["hot","dot","dog","lot","log","cog"], then the answer is 5.

我正在尝试理解高度赞成的解决方案(比我的更好)，如下所示:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
        wordDict.insert(endWord);
        queue<string> toVisit;
        addNextWords(beginWord, wordDict, toVisit);
        int dist = 2;
        while (!toVisit.empty()) {
            int num = toVisit.size();
            for (int i = 0; i < num; i++) {    //-->why this for loop?
                string word = toVisit.front();
                toVisit.pop();
                if (word == endWord) return dist;
                addNextWords(word, wordDict, toVisit);
            }
            dist++;
        }
    }
private:
    void addNextWords(string word, unordered_set<string>& wordDict, queue<string>& toVisit) {
        wordDict.erase(word);
        for (int p = 0; p < (int)word.length(); p++) {
            char letter = word[p];
            for (int k = 0; k < 26; k++) { 
                word[p] = 'a' + k;
                if (wordDict.find(word) != wordDict.end()) {
                    toVisit.push(word);
                    wordDict.erase(word);
                }
            }
            word[p] = letter;
        } 
    } 
};

我几乎理解了整个解决方案，但我不理解迭代toVisit.size()次背后的直觉。这也不是标准 BFS 算法的一部分。有人可以指出这个循环背后的直觉 - 它到底做了什么以及为什么范围(0到1小于队列的大小)？

Answer 1

FOR 循环的存在是为了确保我们仅在访问了从 beginWord 开始的当前 dist 处的所有单词之后才递增 dist。另usecase