代码之家 › 专栏 › 技术社区 › Ganpat

BFS中队列大小的重要性

breadth-first-search algorithm c++

Ganpat · 技术社区 · 6 年前

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

给出两个词( beginWord 和 endWord ),和一本字典 wordList ,我们必须找到最短变换的长度序列自 开始词 到 结束字 这样每个中间产物单词在字典里,每一步我们只能更改一个信因此,如果beginWord='hit',endWord是'cog',dict有 ["hot","dot","dog","lot","log","cog"] ,那么答案是 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小于队列大小)?

2 回复 | 直到 6 年前

Reblochon Masque 6 年前

内部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++;
        }
    }

Ajay 6 年前

FOR循环的存在是为了确保只有在访问了从beginWord开始的当前dist中的所有单词之后,我们才增加dist。另一个 usecase