蓝桥杯一篇搞定bfs算法和dfs算法(C++示例版)

 1.DFS(深度优先搜刮算法)

一.概念

深度优先搜刮（Depth-First Search，简称DFS）是一种用于遍历或搜刮树或图的算法。
DFS 算法的焦点思想是尽可能深地搜刮树或图的分支。当它从某个起始节点开始访问后，会沿着一条路径一直深入下去，直到无法继续（到达叶子节点或者所有相邻节点都已被访问），然后回溯到上一个节点，再尝试访问其他未被访问的分支，云云反复，直到所有可达节点都被访问
二.举例子加深理解

想象你在走一个迷宫，面前有三条岔路：
你会选择第一条路一直走到底，假如走不通就退回到岔路口
然后选择第二条路一直走到底，走不通再退回
末了选择第三条路

具体例子：
假设有这样一棵树：

1.     A
2.    / \
3.   B   C
4. / \   \
5. D   E   F

复制代码

DFS的遍历顺序如下：
从根节点A开始
选择第一个子节点B（先不理会C）
从B继续选择第一个子节点D（先不理会E）
D没有子节点了，退回B
选择B的第二个子节点E
E没有子节点，退回B
B的所有子节点都访问过了，退回A
选择A的第二个子节点C
从C选择唯一子节点F
F没有子节点，退回C
C的所有子节点都访问过了，退回A
最终访问顺序就是：A → B → D → E → C → F
三.底子代码模板

这里列出些我认为关键的部门(不全或者错误的地方可以评论区讨论交流)

1. #include<bits/stdc++.h>  //万能头文件
2. using namespace std;
3. int n;
4. vector<int>book;
5. //上面book数组n可以是要遍历的数组长度，
6. //如果是矩阵的话可以使用二维数组，这里0表示未被访问过 1表示被访问过
7. //还可以使用bool数组，这里可以灵活使用
9. //dfs实现
10. void dfs(){
11. //3.优化算法(剪枝)(一般纯dfs算法的时间复杂度都很高，做题时会导致运行超时)
12. //例如：记忆化数组，多余遍历的条件
13. if(...){
14.   ...
15.   return;
16. }
18. //1.终止条件(满足什么时候返回的条件)
19. if(...){
20.    ...
21.    return;   
22. }
23. //2.搜索条件(满足什么条件可以继续搜索)  这里以查找给定一维数组为例
24. for(int j=0;j<n;j++)//遍历数组
25.    if(book[j]==0){ //判断条件根据题目要求写
26.      book[j]=1 //标记已经被访问过
27.      dfs()     //往下继续搜索,可以理解为当前book[j]的值为1的情况下继续从j=0开始遍历(即该数已经被访问过)
28.      book[j]=0 //回溯  
29.     }
30.   }
31. }
33. int main(){
34.   cin>>n;
35.   book=vector<int>(n,0);//初始book数组
36.   dfs(...)
37. }

复制代码

四.例题:八皇后问题

注:标题来源于洛谷P1219 [USACO1.5] 八皇后 Checker Challenge，如有侵权请及时联系删除，新人发文还望包涵
一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

##以上是我做的html八皇后问题动画截图，需要源码的在评论区留言
输入格式
一行一个正整数 n，表示棋盘是 n×n 巨细的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数
解题代码

1. #include<bits/stdc++.h>  
2. using namespace std;  
3. int n;  
4. int ans = 0;  // 定义一个整数变量 ans，用于记录满足条件的方案数，初始化为 0
5. vector<vector<int>> book;  // 定义一个二维向量 book，用于标记棋盘上每个位置是否已经放置了棋子
6. vector<int>dp;  // 定义一个一维向量 dp，用于记录每一行棋子所在的列数
8. // 判断在 (x, y) 位置放置棋子是否合法的函数
9. bool is(int x, int y) {
10.     // 检查当前列上方是否已经有棋子
11.     for (int i = 0; i < x; i++) {
12.         if (book[i][y] == 1) {
13.             return false;  // 如果上方有棋子，返回 false，表示该位置不合法
14.         }
15.     }
16.     // 检查左上方对角线是否已经有棋子
17.     for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
18.         if (book[i][j] == 1) {
19.             return false;  // 如果左上方对角线上有棋子，返回 false，表示该位置不合法
20.         }
21.     }
22.     // 检查右上方对角线是否已经有棋子
23.     for (int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++) {
24.         if (book[i][j] == 1) {
25.             return false;  // 如果右上方对角线上有棋子，返回 false，表示该位置不合法
26.         }
27.     }
28.     return true;  // 如果以上条件都不满足，说明该位置合法，返回 true
29. }
31. // 打印结果
32. void print() {
33.     for(int j = 0; j < dp.size(); j++) {
34.         cout << dp[j] << " ";  // 输出每一行棋子所在的列数
35.     }
36.     cout << endl;  // 换行
37. }
39. // 深度优先搜索函数，用于尝试在每一行放置棋子
40. void dfs(int x) {
41.     if (x == n) {  // 如果已经遍历完所有行
42.         ans++;  // 方案数加 1
43.         if(ans <= 3) {  // 如果方案数小于等于 3
44.             print();  // 打印当前方案
45.         }
46.         return;  // 回溯
47.     }
48.     for (int y = 0; y < n; y++) {  // 遍历当前行的每一列
49.         if (is(x, y)) {  // 如果在 (x, y) 位置放置棋子合法
50.             book[x][y] = 1;  // 标记该位置已经放置了棋子
51.             dp.push_back(y + 1);  // 将该列数加入 dp 向量
52.             dfs(x + 1);  // 递归调用 dfs 函数，尝试下一行
53.             dp.pop_back();  // 回溯，移除最后添加的列数
54.             book[x][y] = 0;  // 取消该位置的标记
55.         }
56.     }
57. }
59. int main() {
60.     cin >> n;  
61.     book = vector<vector<int>>(n, vector<int>(n, 0));  // 初始化 book 二维向量，所有元素初始化为 0
62.     dfs(0);  // 从第 0 行开始进行深度优先搜索
63.     cout << ans;  
64.     return 0;  
65. }

复制代码

2.BFS(广度优先搜刮算法)

一.概念

BFS 是一种用于遍历或搜刮图或树结构的算法。
它从给定的起始顶点（或节点）开始，起首访问起始顶点的所有相邻顶点，然后再依次访问这些相邻顶点的相邻顶点，以此类推，直到遍历完所有可达顶点或找到目标顶点。其焦点思想是按照条理顺序逐层扩展搜刮范围，就像水波一样从中心向四周扩散。
二.举例子(与dfs形成对照)

迷宫最短路径问题：
BFS会像水波纹一样从起点向外扩散
包管第一次到达终点时找到的就是最短路径
而DFS可能会绕远路，找到的路径不一定最短
照旧那颗树

1.     A
2.    / \
3.   B   C
4. / \   \
5. D   E   F

复制代码

BFS的遍历顺序如下：
从根节点A开始
访问A的所有直接子节点（B和C）
然后访问B的子节点（D和E），再访问C的子节点（F）
最终访问顺序：A → B → C → D → E → F

三.底子代码模板

1. #include <bits/stdc++.h>
2. using namespace std;
3. int n;
4. vector<int> vis;  // 访问标记数组，0未访问，1已访问
5. queue<int> q;      // BFS队列
7. // BFS实现
8. void bfs(int start) {
9.     // 1.初始化队列和访问标记
10.     q.push(start);
11.     vis[start] = 1;
12.    
13.     // 2.BFS主循环
14.     while (!q.empty()) {
15.         int u = q.front();  // 取出队首元素
16.         q.pop();
17.         
18.         // 3.处理当前节点（根据题目要求）
19.         // cout << u << " ";  // 示例：输出访问顺序
20.         
21.         // 4.遍历相邻节点（这里以遍历数组为例）
22.         for (int v = 0; v < n; v++) {
23.             // 5.判断条件（根据题目要求修改）
24.             if (!vis[v] && /* 其他条件 */) {
25.                 vis[v] = 1;  // 标记已访问
26.                 q.push(v);   // 加入队列
27.             }
28.         }
29.     }
30. }
32. int main() {
33.     cin >> n;
34.     vis = vector<int>(n, 0);  // 初始化访问数组
35.     bfs(0);  // 从0号节点开始BFS
36.     return 0;
37. }

复制代码

四.例题：环球变暖

你有一张某海疆 N×N 像素的照片，. 表示海洋、 # 表示陆地，如下所示：

1. .......
2. .##....
3. .##....
4. ....##.
5. ..####.
6. ...###.
7. .......

复制代码

其中 "上下左右" 四个方向上连在一起的一片陆地构成一座岛屿。例如上图就有 2 座岛屿。
由于环球变暖导致了海面上升，科学家推测未来几十年，岛屿边缘一个像素的范围会被海水沉没。具体来说假如一块陆地像素与海洋相邻（上下左右四个相邻像素中有海洋），它就会被沉没。
例如上图中的海疆未来会酿成如下样子：

1. .......
2. .......
3. .......
4. .......
5. ....#..
6. .......
7. .......

复制代码

请你计算：依照科学家的推测，照片中有多少岛屿会被完全沉没。
输入格式
第一行包含一个整数 N。(1≤N≤1000)。
以下 N 行 N 列代表一张海疆照片。
照片包管第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。
输出格式
一个整数表示答案。
标题来源:洛谷 P8662 [蓝桥杯 2018 省 AB] 环球变暖
解题代码

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int N = 1010;
5. char g[N][N];      // 存储地图
6. bool vis[N][N];    // 标记数组
7. int n;             // 地图大小
8. int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 四个方向
10. // 检查当前陆地是否会被淹没
11. bool will_flood(int x, int y) {
12.     for (int i = 0; i < 4; i++) {
13.         int nx = x + dx[i], ny = y + dy[i];
14.         if (g[nx][ny] == '.') // 如果四周有海洋就会被淹没
15.             return true;
16.     }
17.     return false;
18. }
20. // BFS遍历岛屿并检查是否会被完全淹没
21. bool bfs(int x, int y) {
22.     queue<pair<int, int>> q;
23.     q.push({x, y});
24.     vis[x][y] = true;
25.    
26.     bool is_flooded = true; // 假设整个岛屿会被淹没
27.    
28.     while (!q.empty()) {
29.         auto t = q.front();
30.         q.pop();
31.         
32.         // 如果当前陆地不会被淹没，则整个岛屿不会被完全淹没
33.         if (!will_flood(t.first, t.second))
34.             is_flooded = false;
35.         
36.         // 遍历四个方向
37.         for (int i = 0; i < 4; i++) {
38.             int nx = t.first + dx[i], ny = t.second + dy[i];
39.             // 检查边界和是否访问过
40.             if (nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny] && g[nx][ny] == '#') {
41.                 vis[nx][ny] = true;
42.                 q.push({nx, ny});
43.             }
44.         }
45.     }
46.    
47.     return is_flooded;
48. }
50. int main() {
51.     cin >> n;
52.     for (int i = 0; i < n; i++) cin >> g[i];
53.    
54.     int res = 0; // 记录会被完全淹没的岛屿数量
55.    
56.     for (int i = 0; i < n; i++) {
57.         for (int j = 0; j < n; j++) {
58.             // 找到未访问的陆地，开始BFS
59.             if (g[i][j] == '#' && !vis[i][j]) {
60.                 if (bfs(i, j)) // 如果岛屿会被完全淹没
61.                     res++;
62.             }
63.         }
64.     }
65.    
66.     cout << res << endl;
67.     return 0;
68. }

复制代码

##假如文章中有错误的地方还请在评论区指正，有建议也可以提出，毕竟我也只是个学者也在积极学习中，你们的建议同时也会帮助我成长。
好了今天的内容就分享到这里，假如对你有帮助还请给个免费的赞吧，非常感谢。假如你也对算法感爱好点个关注，每日更新实用算法。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。