深度优先搜索(DFS)

顾名思义，深度优先搜素的就在于”深度”二字，通俗来讲，DFS就是从一个起始点开始，找到一个连接点进入
一直进入下去直到没有节点，若找到最后一个节点没有子节点且还存在点没有遍历，则回到上一个节点，继续
寻找节点，直到遍历完所有的点。

下图是一个无向图：

DFS

如上图所示，从节点1开始遍历，使用DFS算法，节点1有三个子节点，分别为节点2，3，4，因为这里我们没有定义
两个节点之间的距离，所以任意选择下一个节点，这里我们选择先进入节点2,如图所示：

DFS

到达节点2之后,与节点2相连的点为1,5,7,但需要注意的是不可能选择节点1,因为节点1已经走过了,所以我们要选择
节点5或者节点7,这里我们选择节点5，如下图所示:

DFS

到节点5的时候，发现节点5没有其他相连的节点了,节点2已经记录走过了,所以不能再走节点2。这个时候我们就要进行回溯，
回溯之后，我们又回到节点2，需要注意的是这里的回到节点2，是回到上一步，而不是在走一次节点2，可以理解为”撤回”操作。

这里为了方便理解，在图像里面我用箭头表示，但需要注意的是算法的原理并不是这样，是回溯

如图所示:

DFS

然后我们又回到节点2,继续寻找与节点2并且没有走过的点，可以发现与节点2相连的并且没走过只有节点7，
所以我们接着遍历节点7.如下图所示:

DFS

回到节点7之后,再次没有可遍历的节点，继续回溯到节点2,可以发现在节点2也没有为遍历的节点,就继续回溯到
节点1,然后遍历节点1的其他节点,直到遍历万所有节点，方法过程与前面类似。

实现方法: 根据前面的过程可以发现，先进入的父节点最后才出来,所以这里我们要使用堆(stack)来实现
DFS算法,把存在子节点的父节点添加到堆里面，直到堆为空结束遍历。

广度优先搜索(BFS)

根据前面的DFS的介绍,自然而然可以想到,广度优先搜索则在于广度,即先把起始点的所有节点全部遍历,然后
遍历起始点子节点的节点，流程如下：
BFS

依旧选择节点1为起始点,可以发现节点1的子节点有节点2,3,4。与DFS的不同,BFS会依次遍历节点1的所有节点。
例如我们这里先选择遍历节点2:
BFS

接下来的遍历就与DFS不一样了,我们不会继续按深度遍历下去,而是继续遍历节点1的其他节点:
BFS
BFS

可以发现我遍历节点2后,紧接着遍历的是节点3和节点4,节点1的节点全部遍历完了,紧接这遍历的是节点2的子节点,
因为我们先进入的是节点2,依次类推,直到遍历所有节点。

实现原理: DFS实现用的是堆(Stack),而BFS根据上面的描述可知,是先进先出,节点2在节点3,4之前进入遍历,
那么节点2的子节点就要先于节点3,4的子节点,这里我们使用队列(queue)来实现BFS算法。

下面我们看一个例题来方便我们更深刻理解BFS和DFS两种算法。

迷宫寻路

题目描述

机器猫被困在一个矩形迷宫里。
迷宫可以视为一个 n*m 矩阵，每个位置要么是空地，要么是墙。机器猫只能从一个空地走到其上、下、左、右的空地。

机器猫初始时位于 (1, 1)的位置，问能否走到 (n, m) 位置。

输入格式

第一行，两个正整数 n,m。

接下来 n 行，输入这个迷宫。每行输入一个长为 m 的字符串，# 表示墙，. 表示空地。

输出格式

仅一行，一个字符串。如果机器猫能走到 (n, m)，则输出 Yes；否则输出 No。

DFS解法

首先我们选择用DFS算法来解决此问题 ，若使用 dfs 访问(x,y)，若不是终点，则尝试往四个方向中的一个寻找答案。
那么这个 dfs 就可以这么写：

  • 排除非法情况，比如坐标越界和遇到障碍物；
  • 如果访问过，则跳过；
  • 如果没访问过，继续处理并标记已访问；
  • 如果得到答案，退出；
  • 否则向四个方向继续扩展。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
using namespace std;

bool dfs(vector<vector<char>>& maze, vector<vector<bool>>& visited, int x, int y, int n, int m) {
    if (x == n && y == m) {
        // 如果当前位置是目标位置，返回true，机器猫可以到达目标位置
        return true;
    }

    visited[x][y] = true; // 标记当前位置为已访问

    // 定义当前位置的上、下、左、右四个相邻位置的偏移量
    vector<pair<int, int>> neighbors = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    for (auto neighbor : neighbors) {
        int nx = x + neighbor.first;  // 相邻位置的行坐标
        int ny = y + neighbor.second;  // 相邻位置的列坐标

        // 检查相邻位置是否在迷宫范围内、未被访问过，并且是空地（不是墙）
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !visited[nx][ny] && maze[nx][ny] == '.') {
            if (dfs(maze, visited, nx, ny, n, m)) {
                return true;  // 递归调用DFS，如果找到一条路径可以到达目标位置，立即返回true
            }
        }
    }

    return false;  // 当前位置无法到达目标位置
}

bool canReachDestination(vector<vector<char>>& maze) {
    int n = maze.size() - 1;  // 获取迷宫的行数
    int m = maze[0].size() - 1;  // 获取迷宫的列数

    vector<vector<bool>> visited(n + 1, vector<bool>(m + 1, false));  // 记录位置是否已访问的标记矩阵，默认为false

    return dfs(maze, visited, 1, 1, n, m);  // 从起始位置开始进行DFS
    }

    int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> maze(n + 1, vector<char>(m + 1));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> maze[i][j];
        }
    }

    if (canReachDestination(maze)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

BFS解法

使用广度优先搜索就要使用到队列，存储待访问的点。
所以我们的 bfs 可以这么写：

  • 把起始点(1,1)入队；
  • 如果队列非空：
    • 弹出队首(x,y)； 判断(x,y) 是否非法，若非法，跳过；
    • 通过堆x,y进行上下左右移动,把(x,y) 相邻的点入队；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool canReachDestination(vector<vector<char>>& maze) {
int n = maze.size() - 1;  // 获取迷宫的行数
int m = maze[0].size() - 1;  // 获取迷宫
vector<vector<bool>> visited(n + 1, vector<bool>(m + 1, false));  // 记录位置是否已访问的标记矩阵，默认为false
    visited[1][1] = true;  // 起始位置已访问

    queue<pair<int, int>> q;  // 创建一个队列用于BFS
    q.push({1, 1});  // 将起始位置加入队列

    while (!q.empty()) {
        int x = q.front().first;  // 当前位置的行坐标
        int y = q.front().second;  // 当前位置的列坐标
        q.pop();  // 弹出队首元素

        if (x == n && y == m) {
            // 如果当前位置是目标位置，返回true，机器猫可以到达目标位置
            return true;
        }

        vector<pair<int, int>> neighbors = {{x - 1, y}, {x + 1, y}, {x, y - 1}, {x, y + 1}};
        // 定义当前位置的上、下、左、右四个相邻位置

        for (auto neighbor : neighbors) {
            int nx = neighbor.first;  // 相邻位置的行坐标
            int ny = neighbor.second;  // 相邻位置的列坐标

            // 检查相邻位置是否在迷宫范围内、未被访问过，并且是空地（不是墙）
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !visited[nx][ny] && maze[nx][ny] == '.') {
                q.push({nx, ny});  // 将相邻位置加入队列
                visited[nx][ny] = true;  // 标记相邻位置为已访问
            }
        }
    }

    // 循环结束时仍未返回，表示无法从起始位置到达目标位置
    return false;
}

int main() {
int n, m;
cin >> n >> m;
vector<vector<char>> maze(n + 1, vector<char>(m + 1
for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> maze[i][j];
        }
    }

if (canReachDestination(maze)) 
    cout << "Yes" << endl;
else 
    cout << "No" << endl;
return 0;}

若代码和讲解存在问题，请帮我纠正，谢谢！！