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 循环从 0 迭代到队列大小的原因是，随着搜索的进行：

新词已添加到您正在迭代的队列中，
同时，当前单词将从该队列中删除。

此 for 循环将迭代限制为队列中最初的单词，并确保对队列所做的修改不会影响搜索的当前阶段。

如果你再盯着它看一会儿，你就会明白是怎么回事了。

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++) {
                string word = toVisit.front();
                toVisit.pop();                         // <-- remove from front of queue 
                if (word == endWord) return dist;
                addNextWords(word, wordDict, toVisit); // <-- add to back of queue
            }
            dist++;
        }
    }

Answer 2

存在 FOR 循环以确保我们仅在访问了来自 beginWord 的当前 dist 处的所有单词后才增加 dist。另一个 usecase

BFS中队列大小的重要性

Importance of the size of the queue in BFS

c++

algorithm

breadth-first-search