广度优先搜索

广度优先搜索是指在访问一个节点时，首先访问和这个节点相邻的节点，如果满足condition，则加入待访问列表，等待一起进行下一层的访问，直到访问到target。一般用于访问最短距离，可用BFS解决的问题通常也可用DFS解决，BFS的空间复杂度较高。虽然BFS有通用模板，参考:BFS算法套路框架，模版伪代码：

queue<Node> q
set<Node> visited

q.push(start)
statistics=0
while(!q.empty()){
    size = q.size()
    for (i;i<size;i++){
        NowNode = q.front()
        q.pop()
        compare with target，if same, return
        visited.insert(NowNode)
        add Nodes Adjacent with NowNode if These Nodes not seen in visited and legal
    }
    statistics++
}

不同的题用法也不太一样，下面以leetcode题介绍几种BFS的类型:

Tree

经典例题1:111. Minimum Depth of Binary Tree
求树的最小高度，即root到target(第一个叶节点)的距离。树的BFS不需要设置visited,节点不存在指向父节点的指针，从root到叶子节点不会走回头路。涉及树的BFS多数要一排一排访问，所以队列里要存一下当前这一排的长度，然后一排排访问，访问过一排之后depth+1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        queue<TreeNode*> q;
        q.push(root);
        int depth=1;
        while (!q.empty())
        {
            int size=q.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode* nownode=q.front();
                q.pop();
                if(!nownode->left && !nownode->right) return depth;
                if(nownode->left) q.push(nownode->left);
                if(nownode->right) q.push(nownode->right);
            }
            depth++;
        }
        return -1;
    }
};

经典例题2:103. Binary Tree Zigzag Level Order Traversal
一排一排访问的典型例题，这个题不需要depth变量

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL) {}
};

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(!root){
            return res;
        }
        queue<TreeNode*> q;
        q.push(root);
        bool isleft=true;
        while (!q.empty())
        {
            int size = q.size();
            vector<int> trans;
            for(int i=0;i<size;i++){
                TreeNode* nowtree = q.front();
                q.pop();
                int value = nowtree->val;
                trans.push_back(value);
                if(nowtree->left) q.push(nowtree->left);
                if(nowtree->right) q.push(nowtree->right);
            }
            if(isleft) res.push_back(trans);
            else{
                reverse(trans.begin(),trans.end());
                res.push_back(trans);
            }
            isleft=!isleft;
        }
        return res;
    }
};

Surrounded Regions

经典例题1:130. Surrounded Regions
连通区域问题，发现在一幅图中的连通区域，对区域进行操作。这种问题可以用BFS也可以用DFS，找到一个点，从而发现全部点，依次找。这里是肯定需要记录是否访问过该节点，否则下一个节点反向操作时候一定会重复访问，和一个节点相邻的节点就是上下左右的点。
这里发现边界上的O是解决问题的关键，和边界连通O的O一定不是surronded by X,不能替换，其它O可以替换。而寻找和边界连通的O的方式是BFS或者DFS。BFS的标准框架是需要一个visited来做记录访问过哪些节点，但是这里可以利用一个题目的特点，可以将访问过的节点的value改成‘#’,减少数据存储，反正最后也要再全部遍历一遍图看哪些节点可以改掉‘O‘
C++ BFS[20ms 10.3MB]

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size()==0 || board[0].size()==0 || board.size()==1 || board[0].size()==1) return;

        int width = board.size();
        int length = board[0].size();

        for(int i=0;i<width;i++){
            for(int j=0;j<length;j++){
                bool isEdge = (i==0 || j==0 || i==width-1 || j==length-1);
                if(isEdge && board[i][j]!='#'){
                    if(board[i][j]=='O'){board[i][j]='#';bfs(board,i,j);}
                }
            }
        }
        for(int i=0;i<width;i++){
            for (int j = 0; j < length; j++)
            {
                if(board[i][j]=='O') board[i][j]='X';
                else if(board[i][j]=='#') board[i][j]='O';
            }
        }
        return;
    }
    void bfs(vector<vector<char>>& board,int w, int l){
        queue<pair<int,int>> q;
        pair<int,int> start=make_pair(w,l);
        q.push(start);
        while (!q.empty())
        {
            pair<int,int> nowtop = q.front();
            q.pop();
            w=nowtop.first;
            l=nowtop.second;
            //up
            if(w-1>0 && board[w-1][l]=='O'){q.push(make_pair(w-1,l));board[w-1][l]='#';}
            //down
            if(w+1<board.size() && board[w+1][l]=='O'){q.push(make_pair(w+1,l));board[w+1][l]='#';}
            //left
            if(l-1>0 && board[w][l-1]=='O'){q.push(make_pair(w,l-1));board[w][l-1]='#';}
            //right
            if(l+1<board[0].size() && board[w][l+1]=='O'){q.push(make_pair(w,l+1));board[w][l+1]='#';}
        }
        return;
    }
};

C++ DFS with Stack[28ms 10.4MB]

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size()==0 || board[0].size()==0 || board.size()==1 || board[0].size()==1) return;

        int width = board.size();
        int length = board[0].size();

        for(int i=0;i<width;i++){
            for(int j=0;j<length;j++){
                bool isEdge = (i==0 || j==0 || i==width-1 || j==length-1);
                if(isEdge && board[i][j]!='#'){
                    if(board[i][j]=='O'){board[i][j]='#';dfs(board,i,j);}
                }
            }
        }
        for(int i=0;i<width;i++){
            for (int j = 0; j < length; j++)
            {
                if(board[i][j]=='O') board[i][j]='X';
                else if(board[i][j]=='#') board[i][j]='O';
            }
        }
        return;
    }
    void dfs(vector<vector<char>>& board, int w, int l){
        stack<pair<int,int>> s;
        s.push(make_pair(w,l));
        while (!s.empty())
        {
            pair<int,int> nowtop=s.top();
            w=nowtop.first;
            l=nowtop.second;
            //up
            if(w-1>0 && board[w-1][l]=='O'){s.push(make_pair(w-1,l));board[w-1][l]='#';continue;}
            //down
            if(w+1<board.size() && board[w+1][l]=='O'){s.push(make_pair(w+1,l));board[w+1][l]='#';continue;}
            //left
            if(l-1>0 && board[w][l-1]=='O'){s.push(make_pair(w,l-1));board[w][l-1]='#';continue;}
            //right
            if(l+1<board[0].size() && board[w][l+1]=='O'){s.push(make_pair(w,l+1));board[w][l+1]='#';continue;}
            s.pop();
        }
        return;
    }
};

C++ DFS Reverse[28ms 10.2MB]

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size()==0 || board[0].size()==0 || board.size()==1 || board[0].size()==1) return;

        int width = board.size();
        int length = board[0].size();

        for(int i=0;i<width;i++){
            for(int j=0;j<length;j++){
                bool isEdge = (i==0 || j==0 || i==width-1 || j==length-1);
                if(isEdge && board[i][j]=='O'){
                    dfs(board,i,j);
                }
            }
        }
        for(int i=0;i<width;i++){
            for (int j = 0; j < length; j++)
            {
                if(board[i][j]=='O') board[i][j]='X';
                else if(board[i][j]=='#') board[i][j]='O';
            }
        }
        return;
    }
    void dfs(vector<vector<char>>& board, int w, int l) {
        if(w<0 || w>=board.size()||l<0||l>=board[0].size() || board[w][l]=='#' || board[w][l]=='X') return;
        
        board[w][l] = '#';
        dfs(board, w - 1, l); // 上
        dfs(board, w + 1, l); // 下
        dfs(board, w, l - 1); // 左
        dfs(board, w, l + 1); // 右
        return;
    }
};

manipulation

manipulation是指对某些初始节点进行操作，旋转，变换字符，变换数字等，要求必须经过某些指定set(Leetcode127 word ladder)或者不能经过某些指定set(Leetcode752 open the lock)，这些需要在判断是否加入队列时修改，最终判断是否能达到target。对这种题来讲，变化一次就是到达了相邻节点，不同题要求返回的东西不一样。
经典例题1:127. Word Ladder
看题可以得到用简单的BFS套模版就可以解，但是tle了。tle的做法是到一个单词之后，在wordlist里搜索和它距离是1的，每次都要计算一次。坏处是随着wordlist规模增长时间大幅度增长，所以会有几个case过不去。尽量把查找变成O(1),上一种做法的查找是O(N),N是wordlist长度。O(1)的做法就是把wordlist变成hash表，unordered set,每次变换字母，因为字母一共就26个，而且这道题的word长度都没有很长。第一种TLE做法的搜索复杂度O(NL) N是worldlist长度，L是单词长度。第二种做法的搜索复杂度是O(26*L)把N变成了一个常数了。每次要在比较终止条件后把元素加入visited。
C++ [128ms 13MB]

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordlist;
        for(auto& wl:wordList) wordlist.insert(wl);

        queue<string> q;
        int step=1;
        int length = beginWord.size();

        q.push(beginWord);
        while (!q.empty())
        {
            int size = q.size();
            for(int i=0;i<size;i++){
                string now = q.front();
                q.pop();
                if(now==endWord) return step;
                for(int j=0;j<length;j++){
                    char ch=now[j];
                    for(char c='a';c<='z';c++){
                        if(ch==c) continue;
                        now[j]=c;
                        if(wordlist.find(now)!=wordlist.end()){
                            q.push(now);
                            wordlist.erase(now);
                        }
                        now[j]=ch;
                    }
                }
            }
            step++;
        }
        
        return 0;
    }
};

后面为了优化时间，做了双向BFS，双向BFS是指从beginword和endword两头同时开搜，每次从最短的set开始搜，时间减半。双向BFS要处理一个case,如果end word没在wordlist里，要直接返回0.不处理这个case不行，因为可能endword变变变变到最后也是在wordlist里和beginword重逢了。但是它自己不在wordlist里，在这道题这种情况该返回0。
C++ [76ms 13.5MB]

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordlist(wordList.begin(),wordList.end());
        if(wordlist.find(endWord)==wordlist.end()) return 0;
        unordered_set<string> begins,ends,visited;
        int step=1;
        int length = beginWord.size();

        begins.insert(beginWord);
        ends.insert(endWord);
        while (!begins.empty() && !ends.empty())
        {
            unordered_set<string> tmp;
            for (auto word:begins)
            {
                if(ends.find(word)!=ends.end()) return step;
                visited.insert(word);
                for(int i=0;i<length;i++){
                    char ch = word[i];
                    for(char c='a';c<='z';c++){
                        if(ch==c) continue;
                        word[i]=c;
                        if(visited.find(word)==visited.end() && wordlist.find(word)!=wordlist.end()){
                            tmp.insert(word);
                        }
                        word[i]=ch;
                    }
                }
            }
            if(tmp.size()>ends.size()){
                begins=ends;
                ends=tmp;
            }
            else{
                begins=tmp;
            }
            step++;
        }
        return 0;
    }
};

经典例题2:126. Word Ladder II
和上一题的区别是需要返回整个单词搜索的结果，还要返回全部的最短结果。
这里就会涉及到重复单词的问题，之前我们遇到重复单词的时候，只需要判断visited里有没有就可以了，这里不能这样。举个例子：[[“hit”,”lit”,”lot”,”log”,”cog”], [“hit”,”hot”,”lot”,”log”,”cog”]],这里出现了两次lot,而按照word ladder I的方法，第二次lot是不会被访问的。但是如果不设定visited必然会出现循环。这里观察题，如果出现了同样的单词,lot，且在最终结果内，它们一定是在同一个位置，比如上面的例子在第三个位置的lot，如果不在同一个位置，一个在第三个位置，另一个lot出现在了第四个位置，那么第四个位置的一定不是最短的。所以在每一次访问过当前层之后，将这一层访问过的全部加入visited.
定义了一个结构体，有prev指针，返回结果的时候一个循环就可以了。注意在 wordlink *p= new wordlink(word); 这一句的时候注意new。指针不能指向临时变量。

struct wordlink
{
    string word;
    wordlink* prev;
    wordlink(string s): word(s), prev(nullptr) {}
};

class Solution {
public:
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> wordset(wordList.begin(), wordList.end());
        vector<vector<string>> res;
        // if(wordset.find(endWord)==wordset.end()) return res;
        queue<wordlink*> q;
        unordered_set<string> visited,tmp;
        
        int length = beginWord.size();
        bool flag=true;
        
        wordlink start = wordlink(beginWord);
        q.push(&start);
        visited.insert(beginWord);
        while (!q.empty() && flag)
        {
            int size = q.size();
            for(int i=0;i<size;i++){
                wordlink* now = q.front();
                q.pop();

                string word=now->word;

                for(int j=0;j<length;j++){
                    char ch = word[j];
                    for(char c='a';c<='z';c++){
                        if(c==ch) continue;
                        word[j]=c;
                        if(wordset.find(word)!=wordset.end()){
                            if(word==endWord){
                                flag=false;
                                vector<string> solu;
                                solu.push_back(word);
                                while (now)
                                {
                                    solu.push_back(now->word);
                                    now = now->prev;
                                }
                                reverse(solu.begin(),solu.end());
                                res.push_back(solu);
                                break;
                            }
                            else{
                                wordlink *p= new wordlink(word);
                                p->prev=now;
                                if(visited.find(word)==visited.end()){
                                    q.push(p);
                                    tmp.insert(word);
                                }
                            }
                        }
                        word[j]=ch;
                    }
                }
            }
            for(auto tmpstr:tmp) visited.insert(tmpstr);
            tmp.clear();
        }
        return res;
    }
};

总结

目前遇到的BFS题型大概这些，其实万变不离其宗，在模版的基础上加以转化就可以了。涉及图论的BFS还没有看到，所以这里先不写，后面再更新啦。