9.深搜广搜
深度优先搜索理论基础
dfs 与 bfs 区别
- dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,再换方向(换方向的过程就涉及到了回溯)。
- bfs是先把本节点所连接的所有节点遍历一遍,走到下一个节点的时候,再把连接节点的所有节点遍历一遍,搜索方向更像是广度,四面八方的搜索过程。
dfs 关键的地方就两点:
- 搜索方向,是认准一个方向搜,直到碰壁之后再换方向
- 换方向是撤销原路径,改为节点链接的下一个路径,回溯的过程。
dfs,bfs其实是基础搜索算法,也广泛应用与其他数据结构与算法中。
深度优先搜索套路总结
回溯算法,其实就是dfs的过程,这里给出
dfs的代码框架
void dfs(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择:本节点所连接的其他节点) {
处理节点;
dfs(图,选择的节点); // 递归
回溯,撤销处理结果
}
}
深搜三部曲
1.确认递归函数,参数
void dfs(参数)
通常我们递归的时候,我们递归搜索需要了解哪些参数,其实也可以在写递归函数的时候,发现需要什么参数,再去补充就可以。
一般情况,深搜需要 二维数组数组结构保存所有路径,需要一维数组保存单一路径,这种保存结果的数组,我们可以定义一个全局变量,避免让我们的函数参数过多。
例如这样:
vector<vector<int>> result; // 保存符合条件的所有路径
vector<int> path; // 起点到终点的路径
void dfs (图,目前搜索的节点)
2.确认终止条件
终止条件很重要,很多同学写dfs的时候,之所以容易死循环,栈溢出等等这些问题,都是因为终止条件没有想清楚。
if (终止条件) {
存放结果;
return;
}
终止添加不仅是结束本层递归,同时也是我们收获结果的时候。
3.处理目前搜索节点出发的路径
一般这里就是一个for循环的操作,去遍历 目前搜索节点 所能到的所有节点。
for (选择:本节点所连接的其他节点) {
处理节点;
dfs(图,选择的节点); // 递归
回溯,撤销处理结果
}
广度优先搜索理论基础
广搜的使用场景
广搜的搜索方式就适合于解决两个点之间的最短路径问题。
因为广搜是从起点出发,以起始点为中心一圈一圈进行搜索,一旦遇到终点,记录之前走过的节点就是一条最短路。
当然,也有一些问题是广搜 和 深搜都可以解决的,例如岛屿问题,这类问题的特征就是不涉及具体的遍历方式,只要能把相邻且相同属性的节点标记上就行。
BFS是一圈一圈的搜索过程,但具体是怎么一圈一圈来搜呢。
我们用一个方格地图,假如每次搜索的方向为 上下左右(不包含斜上方),那么给出一个start起始位置,那么BFS就是从四个方向走出第一步。
如果加上一个end终止位置,那么使用BFS的搜索过程如图所示:
且地图还可以有障碍,如图所示:
在第五步,第六步 我只把关键的节点染色了,其他方向周边没有去染色,大家只要关注关键地方染色的逻辑就可以。
从图中可以看出,如果添加了障碍,我们是第六步才能走到end终点。
广度优先搜索套路总结
这一圈一圈的搜索过程是怎么做到的,是放在什么容器里,才能这样去遍历。
其实,我们仅仅需要一个容器,能保存我们要遍历过的元素就可以,那么用队列,还是用栈,甚至用数组,都是可以的。
用队列的话,就是保证每一圈都是一个方向去转,例如统一顺时针或者逆时针。
因为队列是先进先出,加入元素和弹出元素的顺序是没有改变的。
如果用栈的话,就是第一圈顺时针遍历,第二圈逆时针遍历,第三圈有顺时针遍历。
因为栈是先进后出,加入元素和弹出元素的顺序改变了。
但大家都习惯用队列了
只要 加入队列就代表 走过,就需要标记,而不是从队列拿出来的时候再去标记走过。
广搜代码模板
广搜代码模板,该模板针对的就是,上面的四方格的地图: (详细注释)
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
// grid 是地图,也就是一个二维数组
// visited标记访问过的节点,不要重复访问
// x,y 表示开始搜索节点的下标
void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
queue<pair<int, int>> que; // 定义队列
que.push({x, y}); // 起始节点加入队列
visited[x][y] = true; // 只要加入队列,立刻标记为访问过的节点
while(!que.empty()) { // 开始遍历队列里的元素
pair<int ,int> cur = que.front(); que.pop(); // 从队列取元素
int curx = cur.first;
int cury = cur.second; // 当前节点坐标
for (int i = 0; i < 4; i++) { // 开始想当前节点的四个方向左右上下去遍历
int nextx = curx + dir[i][0];
int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // 坐标越界了,直接跳过
if (!visited[nextx][nexty]) { // 如果节点没被访问过
que.push({nextx, nexty}); // 队列添加该节点为下一轮要遍历的节点
visited[nextx][nexty] = true; // 只要加入队列立刻标记,避免重复访问
}
}
}
}
练习
Hjk悄悄话
题目描述
给定一个二叉树,每个节点上站一个人,节点数字表示父节点到该节点传递悄悄话需要花费的时间。
初始时,根节点所在位置的人有一个悄悄话想要传递给其他人,求二叉树所有节点上的人都接收到悄悄话花费的时间。
输入描述
给定二叉树
0 9 20 -1 -1 15 7 -1 -1 -1 -1 3 2
注: -1 表示空节点
输出描述
返回所有节点都接收到悄悄话花费的时间
38
示例1
输入:
0 9 20 -1 -1 15 15 7 -1 -1 -1 -1 3 2
输出:
38
解题思路
首先构建二叉树,然后深度优先搜索遍历每个节点,递归地将父节点的时延累加到其各个子节点上,并计算每个节点上的人接收到悄悄话的时间。最后返回叶子节点中的最大时延值,即为二叉树所有节点上的人都接收到悄悄话花费的时间。
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
struct Treenode {
int val;
Treenode* left;
Treenode* right;
Treenode(int x): val(x), left(nullptr), right(nullptr) {
}
};
Treenode* buildtree(std::vector<int>& treenums, int index) {
//终止条件
if (index >= treenums.size() || treenums[index] == -1) {
return nullptr;
}
//单层遍历
Treenode* root = new Treenode(treenums[index]);
root -> left = buildtree(treenums, 2*index + 1);
root -> right = buildtree(treenums, 2*index + 2);
return root;
}
int calculatetime(Treenode* root) {
if (root == nullptr) return 0;
int lefttime = calculatetime(root -> left);
int righttime = calculatetime(root -> right);
int maxtime = std::max(lefttime, righttime);
int total = root -> val + maxtime;
return total;
}
int main() {
std::vector<int> treenums;
std::string line;
std::getline(std::cin, line);
std::stringstream ss(line);
int num;
while (ss >> num) {
treenums.push_back(num);
}
//构建二叉树
Treenode* root = buildtree(treenums , 0);
//深搜二叉树
int time = calculatetime(root);
std::cout << time << std::endl;
return 0;
}
Hjk星球改造
在2XXX年,人们发现了一块火星地区,这里看起来很适合建设新家园。但问题是,我们不能一次性将这片地区的空气变得适合人类居住,得分步骤来。
把这片火星地区想象成一个巨大的棋盘。棋盘上的每个格子,都有三种可能的状态:
YES:这片区域的空气已经被改造好了,人类可以在这里生活。
NO:这片区域还未改造,但未来是可以被改造的。
NA:这是个死区,我们不能对其进行改造也不能穿过它。
好消息是,已经改造好的区域(YES)每当大阳日到来,它就会自动帮我们改造与其相邻的四个方向(上下左右)的NO区域,使其变成YES。
你的任务:
告诉我们,这整片待改造的火星地区是否能完全变成适合人类居住的地方。如果可以,需要多少个大阳日来完成?如果不可能,就直接“不可能”。
输入:
一个代表火星地区的棋盘,其中每个格子是:YES、NO、NA。
例如:
输入
YES YES NO
NO NO NO
YES NO NO
输出 2
说明 经过2个太阳日,完成宜居改造
需要多少个大阳日来完成改造,或者“不可能”。
题解
利用广度优先搜索(BFS)算法。在这个情况中,我们需要从所有初始状态为“YES”的单元格开始,然后每个“大阳日”尝试向四周扩展,将“NO”状态的单元格转变为“YES”。如果某次扩展后没有新的单元格被转换,则改造过程停止。如果存在“NO”单元格在BFS完成后仍然未被转换,那么完成改造是“不可能”的
#include <iostream>
#include <vector>
#include <string>
#include <queue>
int daysrequire(std::vector<std::vector<std::string>>& mars) {
//定义四个方向
std::vector<std::vector<int>> dir = {
{0, 1}, {1, 0},{0, -1}, {-1, 0}
};
std::queue<std::pair<int, int>> que;
for (int i = 0; i < mars.size(); i++) {
for (int j = 0; j < mars[0].size(); j++) {
if (mars[i][j] == "YES") {
que.push(std::make_pair(i, j));
}
}
}
if (que.empty()) return -1;
int days = 0;
//开始bfs遍历
while(!que.empty()) {
int currentsize = que.size();
for (int i = 0; i < currentsize; i++) {
int x = que.front().first;
int y = que.front().second;
que.pop();
//查看四个方向
for (int j = 0; j < 4; j++) {
int newX = x + dir[j][0];
int newY = y + dir[j][1];
if (newX >= 0 && newX < mars.size() && newY >= 0 && newY < mars[0].size() && mars[newX][newY] == "NO") {
mars[newX][newY] = "YES";
que.push(std::make_pair(newX, newY));
}
}
}
days ++;
//结束一天后检查是否所有位置被转换为YES
bool foundno = false;
for (int i = 0; i < mars.size(); i++) {
for (int j = 0; j < mars[0].size(); j++) {
if (mars[i][j] == "NO") {
foundno = true;
break;
}
}
if (foundno) break;
}
if (!foundno) return days;
}
return -1; //如果循环结束还存在NO,则返回-1表示不可能
}
int main() {
std::vector<std::vector<std::string>> mars = {
{"YES", "YES", "NO"},
{"NO", "NO", "NO"},
{"YES", "NO", "NO"}
};
int res = daysrequire(mars);
if (res == -1) {
std::cout << -1 << std::endl;
}
else {
std::cout << res << std::endl;
}
return 0;
}