广度优先搜索1

广度优先搜索1

二叉树的广度优先搜索BFS

员工的重要性

N叉树的层序遍历

腐烂的橘子

单词接龙

最小基因变化

打开转盘锁

二叉树的广度优先搜索BFS(宽度优先搜索，或横向优先搜索)

也就是二叉树的层次遍历

利用队列结构：初始状态：顶级根节点入队队列不空就循环出队，出队的节点尾插入vector,出一个节点就入出队的节点的左节点和右节点(没有左或者右就不入)循环结束vector就记录了层次遍历的所有节点

返回一维数组

//层次遍历(利用队列)
vector<TreeNode*> levelTraverse(TreeNode* des) {//空树，直接返回空数组if (!des) return {};//队列queue<TreeNode*> qu;qu.push(des);//结果数组vector<TreeNode*> res;//保存层次遍历的节点TreeNode* element;//层次遍历while (!qu.empty()) {element = qu.front();res.push_back(element);qu.pop(); //出队一个根节点//入队这个根的两个子节点(先左后右)if (element->left) qu.push(element->left);if (element->right) qu.push(element->right);}return res;
}

返回二维数组，常规双循环写法

//借助队列容器完成二叉树的广度优先搜索-->层次遍历
//常规写法：双层循环
//空树，直接返回空数组
if(!root) return {};
queue<TreeNode*> q;
vector<vector<int>> res;
q.emplace(root);
int levelSize = q.size();
TreeNode* front = nullptr;
while(!q.empty()){res.push_back(vector<int>(0, 0));for(size_t i=0; i<levelSize; ++i){front = q.front();//使用vector.back(),可以访问vector尾部元素res.back().push_back(front->val); //res[res.size()-1].push_back();//子节点入队if(front->left) q.push(front->left);if(front->right) q.push(front->right);q.pop();}levelSize = q.size();
}
return res;

返回二维数组，带层深的单层循环写法

//带level的层次遍历 | 单层循环 --> 效率过慢,没有双层循环的常规写法快
//空树，直接返回空数组
if(!root) return {};
queue<TreeNode*> q;
vector<vector<int>> res;
q.emplace(root);
int level = 0; //层深度
int levelSize = q.size();
TreeNode* front = nullptr;
while (levelSize){front = q.front(); //获取队列头if(level == res.size()) // 每向下走一层就给vector增加一行容量res.push_back(vector<int>(0, 0));res[level].push_back(front->val);//子节点入队if(front->left) q.emplace(front->left);if(front->right) q.emplace(front->right);q.pop(); //子节点入队的父出队levelSize--;if(!levelSize){ //第几层levelSize = q.size();++level;} 
}
return res;

广度优先搜索不同与深度优先搜索，会先搜索下一层的所有节点，然后一次搜索下一层节点的后续节点，只需要借助队列数据结构就可以实现

深度优先搜索2–>员工的重要性可以用广度优先搜索解决

员工重要性就是要访问所有直系和间接下属关系的节点，深度优先遍历和广度优先遍历都可以实现

/*
// Definition for Employee.
class Employee {
public:int id;int importance;vector<int> subordinates;
};
*/class Solution {
public:int getImportance(vector<Employee*> employees, int id) {int res = 0;bfs(employees, id, res);return res;}//广度优先搜索void bfs(vector<Employee*> employees, int id, int &res){//队列queue<int> qu;qu.push(id);while(!qu.empty()){int cur = qu.front();vector<int>& sub = id_sub(employees, cur);for(int i=0; i<sub.size(); ++i)qu.push(sub[i]);res+=id_im(employees, cur);qu.pop();}}//通过id获取直系下属vector<int>& id_sub(vector<Employee*> employees, int id){for(int i=0; i<employees.size(); ++i)if(id == employees[i]->id)return employees[i]->subordinates;return employees[0]->subordinates;}//通过id获取自己的重要性int id_im(vector<Employee*> employees, int id){for(int i=0; i<employees.size(); ++i)if(id == employees[i]->id)return employees[i]->importance;return -1;}
};

N叉树的层序遍历

双队列层次遍历法

只消层次遍历就可以解决，重点是每遍历一层就需要作为vector存储入vector<vector>结果中，因此，需要两个队列，遍历完一层就节点入队另一个空队列，这样每遍历完一层非空队列中就是一整层的节点

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:vector<vector<int>> levelOrder(Node* root) {if(nullptr == root) return {};return bfs_tree(root);}//广度优先搜索就能搞定vector<vector<int>> bfs_tree(Node* root){vector<vector<int>> res;queue<Node*> qu;queue<Node*> qu_assist; //辅助队列qu.push(root);vector<int> tmp; //存储某一层的所有节点while(!qu.empty() || !pty()){queue<Node*>& non_empty_qu = !qu.empty() ? qu:qu_assist; //拿到非空队列(存储了上一层的所有节点)queue<Node*>& empty_qu = qu.empty() ? qu:qu_assist; //拿到空队列tmp.clear(); //清空上一层结果while(!non_pty()){ //非空队列出队Node* cur = non_empty_qu.front(); //非空队列队头vector<Node*>& ch = cur->children; //拿到要出队节点的下一层所有节点for(int i=0; i<ch.size(); ++i) //下一层节点入空队empty_qu.push(ch[i]);tmp.push_back(cur->val); //保存当前层节点non_empty_qu.pop(); //非空队列出队}res.push_back(tmp); //保存当前层的vector<int> 入vector<vector<int>>结果集}return res;}
};

改进，单队列就能搞定

每探索完一层，在进行下一层之前计数上一层的节点数，保证队列只会保存某一层所有节点

/*
// Definition for a Node.
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) {val = _val;}Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};
*/class Solution {
public:vector<vector<int>> levelOrder(Node* root) {if(nullptr == root) return {};return bfs_tree(root);}//广度优先搜索就能搞定vector<vector<int>> bfs_tree(Node* root){vector<vector<int>> res;queue<Node*> qu;qu.push(root);vector<int> tmp;while(!qu.empty()){tmp.clear();int sz = qu.size();while(sz--){Node* cur = qu.front();vector<Node*>& ch = cur->children;for(int i=0; i<ch.size(); ++i)qu.push(ch[i]);tmp.push_back(cur->val);qu.pop();}res.push_back(tmp);}return res;}
};

腐烂的橘子

参考N叉树的层序遍历双队列层次遍历法

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int min = INT_MAX;char flag = 0; //0:全是空单元格;1:没有坏果char has_bad = 0; //有坏果vector<int> bad_x;vector<int> bad_y;for(int i=0; i<grid.size(); ++i){for(int j=0; j<grid[0].size(); ++j){if(2 == grid[i][j]){ //保存所有坏果坐标bad_x.push_back(i);bad_y.push_back(j);has_bad = 1; //有坏果}elseflag = flag == 1?flag:grid[i][j]; //有好果就证明一定非全空单元格}}min = bfs_tree(grid, bad_x, bad_y); //双队列层次遍历if(!has_bad && !flag) return 0; //没有坏果有没有好果，则全是空单元格if(!has_bad && 1 == flag) return -1; //没有坏果并且剩余全是空单元格，则全是好果return min;}vector<vector<int>> spread = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};//广度优先搜索int bfs_tree(vector<vector<int>> grid, vector<int> x, vector<int> y){//辅助数组-->标记单元格是否访问过vector<vector<char>> visited(grid.size(), vector<char>(grid[0].size(), 0));queue<int> qu_x;queue<int> qu_y;queue<int> qu_assist_x;queue<int> qu_assist_y;for(int i=0; i<x.size(); ++i){qu_x.push(x[i]);qu_y.push(y[i]);visited[x[i]][y[i]] = 1;}int i = -1; //从-1开始是因为，最后一层节点还需要出队，因此会多数一次while(!pty() || !qu_pty()){queue<int>& non_empty_qu_x = !pty() ? qu_x:qu_assist_x; //拿到非空队列(存储了上一层的所有节点x)queue<int>& non_empty_qu_y = !pty() ? qu_y:qu_assist_y; //拿到非空队列(存储了上一层的所有节点y)queue<int>& empty_qu_x = pty() ? qu_x:qu_assist_x; //拿到空队列queue<int>& empty_qu_y = pty() ? qu_y:qu_assist_y; //拿到空队列while(!non_empty_pty()){ //非空队列出队int cur_x = non_empty_qu_x.front(); //非空队列队头xint cur_y = non_empty_qu_y.front(); //非空队列队头y//四个方向的格子入空队for(int i=0; i<4; ++i){int tmp_x = cur_x + spread[i][0];int tmp_y = cur_y + spread[i][1];if(tmp_x>=0 && tmp_x <grid.size()&&tmp_y>=0 && tmp_y<grid[0].size()&&grid[tmp_x][tmp_y] == 1 &&visited[tmp_x][tmp_y] == 0){empty_qu_x.push(tmp_x);empty_qu_y.push(tmp_y);visited[tmp_x][tmp_y] = 1;grid[tmp_x][tmp_y] = 2;}}non_empty_qu_x.pop(); //非空队列出队non_empty_qu_y.pop(); //非空队列出队}++i;}//判断是否有好的橘子for(int i=0; i<grid.size(); ++i){for(int j=0; j<grid[0].size(); ++j){if(1 == grid[i][j])return -1;}}return i;}
};

简化

将坐标队列queue<pair<int, int>>和time联系起来

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {queue<pair<int, int>> q; //x,y坐标对queue<int> ti;int time = 0;vector<vector<int>> spread = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};for(int i=0; i<grid.size(); ++i)for(int j=0; j<grid[0].size(); ++j)if(2 == grid[i][j]){q.push(make_pair(i, j));ti.push(0);}while(!q.empty()){pair<int, int> cur = q.front();q.pop();time = ti.front();ti.pop();//四个方向的格子for(int i=0; i<4; ++i){int tmp_x = cur.first+spread[i][0];int tmp_y = cur.second+spread[i][1];if(tmp_x>=0 && tmp_x <grid.size()&&tmp_y>=0 && tmp_y<grid[0].size()&&grid[tmp_x][tmp_y] == 1){grid[tmp_x][tmp_y] = 2;q.push(make_pair(tmp_x, tmp_y));ti.push(time+1);}}}//判断是否有好的橘子for(int i=0; i<grid.size(); ++i){for(int j=0; j<grid[0].size(); ++j){if(1 == grid[i][j])return -1;}}return time;}
};

单词接龙

使用queue<pair<string, int>>队列将string是广度优先搜索第几层记录下来，一层循环就能搞定

队列不空就出队，对出队的pair先判断first是不是等于endWord，是的话返回pair的second值(就是优先级搜索的层级数)；否则出队的元素与遍历wordList的每个字符串使用differOnce函数判断字符串是否只相差一个字符，相差一个就可以作为广度优先搜索的下一层，遍历到的wordList入队的同时层次值作为pair的第二个值+1同时入队，就能轻易的得到入队的任何一个节点是第几层

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {int flag = 0;for(int i=0; i<wordList.size(); ++i){if(!endWordpare(wordList[i]))flag = 1;if (!beginWordpare(wordList[i])) { //删除wordList中的beginWord，减少后续循环代价(不删除也是正确的，效率会有所影响)ase(wordList.begin()+i);--i;}}if(!flag) return 0; //endWord不在字典中queue<pair<string, int>> qu;qu.push(make_pair(beginWord, 1));//广度优先搜索while(!qu.empty()){pair<string, int> cur = qu.front();qu.pop();if(!cur.firstpare(endWord)) return cur.second;for(int i=0; i<wordList.size(); ++i){if (differOnce(wordList[i], cur.first)) {qu.push(make_pair(wordList[i], cur.second + 1));ase(wordList.begin() + i); //wordList利用过的字符串就删除，以提高下次一次循环匹配字符串效率--i;}}}return 0;}bool differOnce(const string& a, const string& b){int count = 0;for(int i=0; i<a.size(); ++i)if(a[i] != b[i])++count;if(count == 1) return true;return false;}
};

最小基因变化

与单词接龙思路完全一致

class Solution {
public:int minMutation(string start, string end, vector<string>& bank) {int flag = 0;for(int i=0; i<bank.size(); ++i){if(!endpare(bank[i]))flag = 1;if (!startpare(bank[i])) { //删除bank中的start，减少后续循环代价(不删除也是正确的，效率会有所影响)ase(bank.begin()+i);--i;}}if(!flag) return -1; //bend不在字典中queue<pair<string, int>> qu;qu.push(make_pair(start, 0));//广度优先搜索while(!qu.empty()){pair<string, int> cur = qu.front();qu.pop();if(!cur.firstpare(end)) return cur.second;for(int i=0; i<bank.size(); ++i){if (differOnce(bank[i], cur.first)) {qu.push(make_pair(bank[i], cur.second + 1));ase(bank.begin() + i); //bank利用过的字符串就删除，以提高下次一次循环匹配字符串效率--i;}}}return -1;}//判断相差基因序列相差一个碱基对bool differOnce(const string& a, const string& b){int count = 0;for(int i=0; i<a.size(); ++i)if(a[i] != b[i])++count;if(count == 1) return true;return false;}
};

打开转盘锁

与最小基因变化不同的是一旦某一层深度优先搜索遍历到deadends中的元素，这个节点需要出队并且其之后的元素都不能再入队

下次层节点可以是某一位+1或者某一位-1

class Solution {
public:int openLock(vector<string>& deadends, string target) {for(int i=0; i<deadends.size(); ++i){if(!targetpare(deadends[i])) //target在deadends中则一定不能解锁，return -1return -1;}//广度优先搜索queue<pair<string, int>> qu;qu.push(make_pair("0000", 0));while(!qu.empty()){int flag = 0; //出队的节点在deadends中pair<string, int> cur = qu.front();qu.pop();if(!cur.firstpare(target)) return cur.second;for(int i=0; i<4; ++i){string tmp = cur.first;tmp[i] = tmp[i] == '9'? '0' : tmp[i]+1; //tmp[i] += 1;if(!deadendsHasTarget(deadends, tmp)) //判断要入队的下一层节点是不是在deadends中qu.push(make_pair(tmp, cur.second + 1));tmp = cur.first;tmp[i] = tmp[i] == '0'? '9' : tmp[i]-1; //tmp[i] -= 1;if(!deadendsHasTarget(deadends, tmp))qu.push(make_pair(tmp, cur.second + 1));}}return -1;}bool deadendsHasTarget(vector<string>& deadends, string target){for(int i=0; i<deadends.size(); ++i){if(!deadends[i]pare(target))return true;}return false;}
};

时间复杂度有点太大了，没有过OJ,而且应该是产生了死循环

原因：会走回头路。比如说我们从 “0000” 拨到 “1000”，但是等从队列拿出 “1000” 时，还会拨出一个 “0000”，这样的话会产生死循环

初始状态：0000，每一位可以向上拨也可以向下拨

因此广度优先搜索第二层：

0001、0010、0100、1000、0009、0090、0900、9000

广度优先搜索第三层

上一层的0001向下拨就会产生0000，就这样产生死循环

改进

class Solution {
public:int openLock(vector<string>& deadends, string target) {// 记录需要跳过的死亡密码set<string> deads;for (string s : deadends) deads.insert(s);// 记录已经穷举过的密码，防止走回头路set<string> visited;queue<string> q;// 从起点开始启动广度优先搜索int step = 0;q.push("0000");visited.insert("0000");//广度优先搜索while (!q.empty()) {int sz = q.size();/* 将当前队列中的所有节点向周围扩散 */for (int i = 0; i < sz; i++) {string cur = q.front();q.pop();/* 判断是否到达终点 */if (deads.find(cur) != d())continue;if (!curpare(target))return step;/* 将一个节点的未遍历相邻节点加入队列 */for (int j = 0; j < 4; j++) {string up = plusOne(cur, j);if (visited.find(up) == d()) { //up没有访问过q.push(up);visited.insert(up);}string down = minusOne(cur, j);if (visited.find(down) == d()) { //down没有访问过q.push(down);visited.insert(down);}}}/* 在这里增加步数 */step++;}// 如果穷举完都没找到目标密码，那就是找不到了return -1;}// 将 s[j] 向上拨动一次string plusOne(string s, int j) {s[j] = s[j] == '9'? '0':s[j]+1;return s;}// 将 s[i] 向下拨动一次string minusOne(string s, int j) {s[j] = s[j] == '0'? '9':s[j]-1;return s;}};

继续优化–>双向 BFS 优化

传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。

BFS和双向BFS它俩的最坏复杂度都是 O(N)，但是双向BFS会快一点：

图示中的树形结构，如果终点在最底部，按照传统 BFS 算法的策略，会把整棵树的节点都搜索一遍，最后找到 target；而双向 BFS 其实只遍历了半棵树就出现了交集，也就是找到了最短距离。从这个例子可以直观地感受到，双向 BFS 是要比传统 BFS 高效的

使用双向 BFS 的前提是必须知道终点在哪里

class Solution {
public:int openLock(vector<string>& deadends, string target) {unordered_set<string> deads;for (string s : deadends) deads.insert(s);// 用集合不用队列，可以快速判断元素是否存在unordered_set<string> q1;unordered_set<string> q2;unordered_set<string> visited;int step = 0;q1.insert("0000");q2.insert(target);while (!q1.empty() && !q2.empty()) {// 哈希集合在遍历的过程中不能修改，用 temp 存储扩散结果unordered_set<string> temp;/* 将 q1 中的所有节点向周围扩散 */for (string cur : q1) {/* 判断是否到达终点 */if (deads.find(cur) != d())continue;if (q2.find(cur) != q2.end())return step;visited.insert(cur);/* 将一个节点的未遍历相邻节点加入集合 */for (int j = 0; j < 4; j++) {string up = plusOne(cur, j);if (visited.find(up) == d())temp.insert(up);string down = minusOne(cur, j);if (visited.find(down) == d())temp.insert(down);}}/* 在这里增加步数 */step++;// temp 相当于 q1// 这里交换 q1 q2，下一轮 while 就是扩散 q2q1 = q2;q2 = temp;}return -1;}// 将 s[j] 向上拨动一次string plusOne(string s, int j) {s[j] = s[j] == '9'? '0':s[j]+1;return s;}// 将 s[i] 向下拨动一次string minusOne(string s, int j) {s[j] = s[j] == '0'? '9':s[j]-1;return s;}
};

双向 BFS 还是遵循 BFS 算法框架的，只是不再使用队列，而是使用 Hashtable实现的unordered_set方便快速判断两个集合是否有交集