一、通过迷宫问题总结广度优先搜索算法
假设有一个迷宫，用二维矩阵表示，矩阵中标记为0的地方表示可以通过，标记为1的地方表示有障碍物不能通过。现在给定迷宫大小为10*10，入口位置在(1,1)位置出口在(8,10)位置，判断从入口进来，是否可以走出迷宫，每次可以任意方向走。
尝试深度优先搜索是否可以解决：
- 从入口进来，朝着一个方向走到尽头。
- 如果没有找到出口，则折返换一个方向继续。
- 直到找到出口或者所有方向都尝试完也没找到出口结束。
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
using namespace std;
struct Node
{
int x;
int y;
};
void DepthFirstSearch(vector<vector<int>>& maze,int sr,int sc,vector<struct Node>& ret)
{
//终止条件:位置非法；有障碍物；已经走出
if (sr < 0 || sr >= 10 || sc < 0 || sc >= 10)
{
//ret.pop_back();
return;
}
if (maze[sr][sc] != 0)
{
//ret.pop_back();
return;
}
if (sr == 8 && sc == 9)
{
struct Node newNode = {8,9};
ret.push_back(newNode);
return;
}
//没有找到出口且还可以继续走，则将该位置存入ret，继续往四个方向走
struct Node newNode = { sr,sc };
ret.push_back(newNode);
//将该位置标记为-1，表示已经走过
maze[sr][sc] = -1;
DepthFirstSearch(maze,sr,sc-1,ret);
DepthFirstSearch(maze, sr, sc + 1, ret);
DepthFirstSearch(maze, sr-1, sc, ret);
DepthFirstSearch(maze, sr+1, sc, ret);
//某一个位置四个方向走完都没有出去，则折返
int x = ret.back().x;
int y = ret.back().y;
if (x == sr && y == sc)
ret.pop_back();
}
int main()
{
//随机数种子
srand((unsigned)time(NULL));
//给定迷宫
vector<vector<int>> maze(10,vector<int>(10,0));
//第一行最后一行全为1，第一列和最后一列有一个出口和入口
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
if (i == 0 || i == 9 || j == 0 || j == 9)
maze[i][j] = 1;
else
{
//生成一个随机数，这个随机数要么是0要么是1
maze[i][j] = rand()%2;
}
}
}
//入口（1,0）出口（8,9）
maze[1][0] = maze[8][9] = 0;
/*maze = { {1,1,1,1,1,1,1,1,1,1},
{0,0,0,1,0,0,1,1,1,1},
{1,1,0,0,0,0,0,0,0,1},
{1,0,1,0,1,1,1,1,0,1},
{1,1,0,0,0,0,0,1,1,1},
{1,0,1,0,0,0,1,1,0,1},
{1,1,0,0,1,1,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0},
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };*/
//打印迷宫
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
cout << maze[i][j] << " ";
}
cout << endl;
}
//深度优先搜索打印出路径
vector<struct Node> path;
DepthFirstSearch(maze,1,0,path);
//打印路径
if (path.empty())
cout << "没有能够出去的路径" << endl;
for (auto e : path)
{
cout << '(' << e.x << ',' << e.y << ')' << " ";
}
cout << endl;
return 0;
}广度优先该如何解决这个问题呢？
- 深度优先搜索是指一条路走到黑，没有成功找另一条路，成功直接返回。
- 广度优先搜索，顾名思义先判断该节点的四个方向，如果有一个是出口，则找到了。
- 否则，在从这四个方向分别出发，判断它们的四个方向是否有出口
#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
using namespace std;
struct Node
{
int x;
int y;
};
int BreadthFirstSearch(vector<vector<int>>& maze,int sr,int sc,int dr,int dc,vector<struct Node>& path)
{
//入口（sr,sc）出口（dr,dc）
//注意：maze中1表示障碍物，-1表示该位置已经走过了，0表示该位置可以走
//思路：从当前路径带出四个方向，四个方向在依次带出各自的四个方向
//初始化path
struct Node newNode = {sr,sc};
path.push_back(newNode);
maze[sr][sc] = -1;
//标记是否为出口
int flag = 0;
//四个行走的方向，上下左右
int next[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
//标记起始和结束位置，注意的是每有一个位置入数组，tail++
int head = 0;
int tail = 1;
while (head < tail)
{
//从head带出它的四个方向
for (int i = 0; i < 4; i++)
{
//新位置的坐标
int nx = path[head].x + next[i][0];
int ny = path[head].y + next[i][1];
//新位置非法，继续下一个方向
if (nx < 0 || nx >= 10 || ny < 0 || ny >= 10)
continue;
//如果该位置没被走过
if (maze[nx][ny] == 0)
{
newNode = {nx,ny};
path.push_back(newNode);
maze[nx][ny] = -1;
tail++;
}
//新位置为出口，结束
if (nx == dr && ny == dc)
{
flag = 1;
break;
}
}
if (flag)
break;
head++;
}
return flag;
}
int main()
{
//随机数种子
srand((unsigned)time(NULL));
//给定迷宫
vector<vector<int>> maze(10, vector<int>(10, 0));
//第一行最后一行全为1，第一列和最后一列有一个出口和入口
//for (int i = 0; i < 10; i++)
//{
// for (int j = 0; j < 10; j++)
// {
// if (i == 0 || i == 9 || j == 0 || j == 9)
// maze[i][j] = 1;
// else
// {
// //生成一个随机数，这个随机数要么是0要么是1
// maze[i][j] = rand() % 2;
// }
// }
//}
入口（1,0）出口（8,9）
//maze[1][0] = maze[8][9] = 0;
maze = { {1,1,1,1,1,1,1,1,1,1},
{0,0,0,1,0,0,1,1,1,1},
{1,1,0,0,0,0,0,0,0,1},
{1,0,1,0,1,1,1,1,0,1},
{1,1,0,0,0,0,0,1,1,1},
{1,0,1,0,0,0,1,1,0,1},
{1,1,0,0,1,1,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,0,0,0,0,0},
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } };
//打印迷宫
for (int i = 0; i < 10; i++)
{
for (int j = 0; j < 10; j++)
{
cout << maze[i][j] << " ";
}
cout << endl;
}
//深度优先搜索打印出路径
vector<struct Node> path;
if (BreadthFirstSearch(maze, 1, 0, 8, 9, path))
cout << "找到了" << endl;
else
cout << "没找到" << endl;
return 0;
}观察上面两种方法，它们有什么区别？
1、广度优先搜索的一般过程
Bfs()
{
1. 建立起始步骤，队列初始化
2. 遍历队列中的每一种可能，whlie(队列不为空)
{
通过队头元素带出下一步的所有可能，并且依次入队
{
判断当前情况是否达成目标：按照目标要求处理逻辑
}
继续遍历队列中的剩余情况
}
}2、广度优先搜索的特点
- 通过上面一个题，可以看出深度优先搜索是在探寻一跳路径
- 广度优先搜索是找到所有路径
- 因此，广度优先搜索一定可以寻找最优解。而深度优先搜索找到的不一定是最优解。
- 广度优先搜索一般使用循环+队列进行搜索
二、例题分析
1、员工的重要性
思路：将一个员工的所有直系下属的重要性之和计算完，在计算它们的下属的下属。即，定义一个队里用广度优先搜索的思路进行计算，首先将id元素找到并入队，队头元素出队前先将其直系下属带入队列。
class Solution {
public:
int _getImportance(vector<Employee*>& employees,int id)
{
//定义并初始化队列
queue<Employee*> qu;
//找到id员工在数组中的下标,保存到队列中
int index = 0;
for(int i = 0;i < employees.size();i++)
{
if(employees[i]->id == id)
{
qu.push(employees[i]);
break;
}
}
//遍历队列，每一个队头节点将自己的直系下属带入队列在，直到队列为空
int sumImportance = qu.front()->importance;
while(!qu.empty())
{
//如果队头节点有直系下属
//计算队头元素的直系下属的重要性之和
for(int i = 0;i < qu.front()->subordinates.size();i++)
{
int subId = qu.front()->subordinates[i];
//在employees中找到该员工并保存到队列中
for(int j = 0;j < employees.size();j++)
{
if(employees[j]->id == subId)
{
sumImportance += employees[j]->importance;
qu.push(employees[j]);
break;
}
}
}
//队头节点将其所有直系下属节点带入队列后，队头节点出队
qu.pop();
}
return sumImportance;
}
int getImportance(vector<Employee*> employees, int id) {
//|广度优先搜索
return _getImportance(employees,id);
}
};2、N叉树的层序遍历
思路：层序遍历，需要注意的是这里要求一层一层的输出。因此，层序遍历时还要记录当前层节点的个数和下一层的节点个数。
class Solution {
public:
void _levelOrder(vector<vector<int>>& ret,Node* root)
{
//定义队列并初始化
queue<Node*> qu;
qu.push(root);
//记录当前层和下一层的节点个数
int cur = 1;//第一层，只有一个节点
int next = 0;//下一层，初始化为0
vector<int> tmp;
//遍历队列，用队列的头结点将其所有孩子节点带入队列
while(!qu.empty())
{
if(qu.front() != nullptr)
{
if(cur == 0)
{
//当前层遍历完了，遍历下一层
cur = next;
next = 0;
ret.push_back(tmp);
tmp.resize(0);
}
//带入孩子节点
for(int i = 0;i < qu.front()->children.size();i++)
{
qu.push(qu.front()->children[i]);
next++;
}
//所有孩子节点带入后，出队
tmp.push_back(qu.front()->val);
}
qu.pop();
cur--;
}
ret.push_back(tmp);
}
vector<vector<int>> levelOrder(Node* root) {
//广度优先搜索
vector<vector<int>> ret;
if(root == nullptr)
return ret;
_levelOrder(ret,root);
return ret;
}
};3、腐烂的橘子
这个题需要注意的是，刚开始可能就有多个橘子腐烂，所以开始时队列中可能会有多个节点。同时，每个节点带入的新节点的num应该是在该节点的基础上+1的。还有一点就是，如果没有橘子输出的结果是0.
public:
struct Node
{
int x;
int y;
int num;
};
int _orangesRotting(vector<vector<int>>&grid)
{
int ret = 0;
//定义并初始化队列
queue<Node> qu;
//找出所有腐烂的橘子加入队列中
for(int i = 0;i < grid.size();i++)
{
for(int j = 0;j < grid[0].size();j++)
{
if(grid[i][j] == 2)
{
Node newNode = {i,j,0};
qu.push(newNode);
}
}
}
//四个方向
int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
while(!qu.empty())
{
//带入四个方向
for(int i = 0;i < 4;i++)
{
int nx = qu.front().x + direction[i][0];
int ny = qu.front().y + direction[i][1];
//判断新的位置是否合法
if(nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size())
continue;
//该位置是新鲜橘子
if(grid[nx][ny] == 1)
{
Node newNode = {nx,ny,qu.front().num+1};
grid[nx][ny] = 2;
qu.push(newNode);
ret = qu.back().num;
}
}
qu.pop();
}
return ret;
}
int orangesRotting(vector<vector<int>>& grid) {
if(grid.empty())
return -1;
//判断是否有腐烂的橘子
int sr = -1,sc = -1;
for(int i = 0;i < grid.size();i++)
{
for(int j = 0;j < grid[0].size();j++)
{
if(grid[i][j] == 2)
{
sr = i;
sc = j;
break;
}
}
}
if(sr == -1 && sc == -1)
{
//如果没有橘子返回0，否则返回-1
for(int i = 0;i < grid.size();i++)
{
for(int j = 0;j < grid[0].size();j++)
{
if(grid[i][j] != 0)
return -1;
}
}
return 0;
}
//广度优先搜索找最优解
int ret = _orangesRotting(grid);
//判断是否没有好橘子
for(int i = 0;i < grid.size();i++)
{
for(int j = 0;j < grid[0].size();j++)
{
if(grid[i][j] == 1)
return -1;
}
}
return ret;
}
};
4、单词接龙
思路：为了查找快速，建立unorder_map将字符串序列保存，并且记录该字符串是否访问过。用26个英文小写字符替换单词中的每一个字母，并且查找替换后会不会出现序列中相同的单词，如果出现则保存在队列中。直到找到endWord
class Solution {
public:
struct Node
{
string str;
int count;
};
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
//保存在hashmap中，查找速度快，同时可以记录是否被访问过
unordered_map<string,int> hashMap;
for(auto e:wordList)
hashMap[e] = 0;
//定义并初始化队列
queue<struct Node> qu;
struct Node newNode = {beginWord,1};
qu.push(newNode);
//遍历队列
int flag = 1;
while(!qu.empty() && flag)
{
string& str = qu.front().str;
for(int i = 0;i < str.size() && flag;i++)
{
//对单词第i位用26个字母进行替换
for(int j = 0;j < 26;j++)
{
if(str[i] != 'a'+j)
{
string tmp = str;
tmp[i] = 'a'+j;
if(hashMap.find(tmp) != hashMap.end() && hashMap.find(tmp)->second == 0)
{
//存在这么一个单词
newNode = {tmp,qu.front().count+1};
qu.push(newNode);
hashMap[tmp] = 1;
if(tmp == endWord)
{
flag = 0;
break;
}
}
}
}
}
qu.pop();
}
if(flag == 1)
return 0;
return qu.back().count;
}
};5、最小基因变化
注意：和上一个题是同类型，思路完全相同
class Solution {
public:
struct Node
{
string str;
int count;
};
int minMutation(string start, string end, vector<string>& bank) {
//将基因库保存在unordered_map中，方便快速查找
unordered_map<string,int> hashMap;
for(auto e:bank)
hashMap[e] = 0;
//定义并初始化队列
queue<struct Node> qu;
struct Node newNode = {start,0};
qu.push(newNode);
//遍历队列
int flag = 1;//表示是否找到，为0表示找到
char list[4] = {'A','C','G','T'};
int ret;
while(!qu.empty() && flag)
{
//对队头的基因序列进行改变
string str = qu.front().str;
for(int i = 0;i < 8;i++)
{
//将str的第i位变成ACGT中的任意一个，在基因库中查看是否存在
for(int j = 0;j < 4;j++)
{
if(str[i] != list[j])
{
string tmp = str;
tmp[i] = list[j];
//基因库中存在这个基因
if(hashMap.find(tmp) != hashMap.end() &&hashMap.find(tmp)->second == 0)
{
newNode = {tmp,qu.front().count+1};
qu.push(newNode);
hashMap[tmp] = 1;
if(tmp == end)
{
ret = qu.back().count;
flag = 0;
break;
}
}
}
}
}
qu.pop();
}
if(flag == 1)
return -1;
return ret;
}
};6、打开转盘锁
思路：对锁中的每一个+1或-1，并将结构保存在set中用于下次判断是否已经使用过。对队列进行遍历，直到找到target.需要注意的是，存在两种特殊情况“0000”就是死锁或者是target，因此需要对这两种情况进行单独判断。
class Solution {
public:
struct Node
{
string str;
int count;
};
int openLock(vector<string>& deadends, string target) {
//将死亡数字保存在unordered_Set中
unordered_set<string> hashSet;
for(auto e:deadends)
hashSet.insert(e);
//判断“0000”是否为死锁
if(hashSet.find("0000") != hashSet.end())
return -1;
if(target == "0000")
return 0;
//使用hashmap保存所有的中间节点
unordered_map<string,int> hashMap;
//定义并初始化队列
queue<struct Node> qu;
struct Node newNode = {"0000",0};
qu.push(newNode);
int flag = 1;
int ret = -1;
int list[2] = {1,-1};
while(!qu.empty() && flag)
{
//每一个字符串的四位替换成0~9进行查找，判断是否会出现target
string str = qu.front().str;
for(int i = 0;i < 4 && flag;i++)
{
for(int j = 0;j < 2;j++)
{
string tmp = str;
int n = (tmp[i]-'0'+10+list[j])%10;
tmp[i] = n+'0';
if(hashSet.find(tmp) != hashSet.end())
{
//死锁
continue;
}
else if(hashMap.find(tmp) == hashMap.end())
{
//这个没有被使用过
hashMap[tmp] = 0;
newNode = {tmp,qu.front().count+1};
qu.push(newNode);
if(tmp == target)
{
flag = 0;
ret = qu.back().count;
break;
}
}
}
}
qu.pop();
}
return ret;
}
};