GESP 六级 · 算法基础

🔍 深度搜索 DFS & 广度搜索 BFS

从零开始，用动画和代码彻底搞懂两种最核心的搜索算法

📖 什么是「搜索」？

想象你在一个巨大的迷宫里，需要找到出口。你会怎么走？

在计算机的世界里，搜索就是系统地遍历图或树中的所有节点，找到你需要的东西——比如一条路径、一个目标，或者所有可能的方案。

🗺️ 生活中的搜索 你在找家里的钥匙。你可以一个房间一个房间地找（广度搜索），也可以进了一个房间就把里面所有角落翻遍再换下一个房间（深度搜索）。

先认识「图」和「树」

在学习 DFS 和 BFS 之前，我们需要知道它们在什么上面跑：

💡 关键概念：visited 数组
在图中搜索时，一个节点可能被多条边连接。如果不做标记，就会重复访问，甚至无限循环！所以我们用一个 visited 数组来记录哪些节点已经访问过了。这就像在迷宫里做记号——走过的地方就不再走了。

🟣 深度优先搜索 DFS

Depth-First Search —— 一条路走到黑，碰壁再回头

核心思想

DFS 的策略是：从起点出发，沿着一条路一直走，走到走不动了（没有未访问的邻居），就退回上一个路口，换一条路继续走。

🏰 比喻：探索洞穴 你在探索一个洞穴系统。你总是选择一个方向一直走，走到死路就在岔路口做个标记，退回来换另一条路。这样你最终会探索完整个洞穴。这就是 DFS！

🔑 关键要素

💡 什么是「回溯」？
回溯就是撤销当前选择，回到上一步，尝试其他选择。比如走迷宫时走进死路，你要退回来换条路——这就是回溯。回溯是 DFS 的灵魂，也是全排列、组合等问题的基础。

🎬 交互动画：DFS 图遍历

点击「播放」看 DFS 如何遍历这个图。注意观察栈的变化和回溯过程！

点击「播放」或「下一步」开始动画
📦 栈 (Stack) — 后进先出
栈为空
✅ 已访问节点
还没有访问任何节点
0 / 0
速度

💻 C++ 代码：DFS 递归写法

C++ · DFS 递归模板
1#include <iostream>
2#include <vector>
3using namespace std;
4
5vector<int> adj[100];  // 邻接表
6bool visited[100];     // 标记是否访问过
7
8void dfs(int u) {
9    visited[u] = true;        // 1. 标记当前节点已访问
10    cout << u << " ";           // 2. 处理当前节点（输出）
11
12    // 3. 遍历所有相邻节点
13    for (int i = 0; i < adj[u].size(); i++) {
14        int v = adj[u][i];         // v 是 u 的邻居
15        if (!visited[v]) {         // 如果 v 还没访问过
16            dfs(v);                // 4. 递归访问 v（深入！）
17        }                           // 5. dfs(v) 返回后，自动回溯到 u
18    }
19}
20
21// 调用：从节点 1 开始搜索
22dfs(1);
💡 代码解读
第9行：标记当前节点已访问（做记号！）
第10行：处理当前节点（这里只是输出，也可以做其他操作）
第13-14行：遍历当前节点的所有邻居
第15-16行：如果邻居没访问过，递归访问它
第17行注释：递归返回时，自动回到当前节点继续循环——这就是回溯！

🟢 广度优先搜索 BFS

Breadth-First Search —— 一层一层扩展，像水波纹一样

核心思想

BFS 的策略是：从起点出发，先访问所有距离为 1 的节点，再访问所有距离为 2 的节点，一层一层向外扩展，直到访问完所有节点。

🌊 比喻：水波纹 往水里扔一颗石头，波纹会一圈一圈向外扩散。BFS 就是这样——从起点开始，一层一层地扩展，先近后远。这就是 BFS！

🔑 关键要素

💡 为什么 BFS 能找最短路径？
因为 BFS 是按距离一层一层扩展的——先访问距离为 1 的，再访问距离为 2 的……所以第一次到达终点时，一定是最短路径！这就像你问路时，先问身边的人（距离 1），再问他们身边的人（距离 2），一定能找到最近的路线。

🎬 交互动画：BFS 图遍历

同样的图，看看 BFS 的遍历顺序和 DFS 有什么不同！注意观察队列的变化。

点击「播放」或「下一步」开始动画
🚌 队列 (Queue) — 先进先出
队列为空
✅ 已访问节点
还没有访问任何节点
0 / 0
速度

💻 C++ 代码：BFS 队列写法

C++ · BFS 队列模板
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6vector<int> adj[100];  // 邻接表
7bool visited[100];     // 标记是否访问过
8
9void bfs(int start) {
10    queue<int> q;
11    q.push(start);          // 1. 起点入队
12    visited[start] = true;  // 2. 标记起点已访问
13
14    while (!q.empty()) {     // 3. 队列不空就继续
15        int u = q.front();     // 4. 取出队首
16        q.pop();               // 5. 出队
17        cout << u << " ";       // 6. 处理当前节点
18
19        // 7. 遍历所有相邻节点
20        for (int i = 0; i < adj[u].size(); i++) {
21            int v = adj[u][i];
22            if (!visited[v]) {     // 8. 如果 v 没访问过
23                visited[v] = true; // 9. 标记已访问
24                q.push(v);       // 10. 入队（排在后面）
25            }
26        }
27    }
28}
29
30// 调用：从节点 1 开始搜索
31bfs(1);
💡 代码解读
第11-12行：起点入队并标记已访问（注意：入队时就标记，不是出队时才标记！）
第14行：while 循环——队列不空就继续
第15-17行：取出队首、出队、处理节点
第20-24行：遍历邻居，没访问过就标记并入队
⚠️ 易错点：第23行标记已访问一定要在第24行入队之前做，否则同一个节点可能被多次入队！

🏘️ 迷宫对比：DFS vs BFS

同样的迷宫，看看两种算法的搜索方式有什么不同

下面是一个 10×10 的迷宫。DFS 会深入探索、走死路再回头；BFS 会一层层扩展，直接找到最短路径。

切换算法，观察探索过程的区别，特别注意探索的格子数和找到的路径长度！

0 / 0
速度

🟣 DFS 搜索

🟢 BFS 搜索

DFS 探索格子数
—
DFS 路径长度
—
BFS 探索格子数
—
BFS 路径长度（最短）
—
选择算法并点击播放，开始对比演示
💡 观察要点
1. 探索方式：DFS 会沿着一条路一直走，遇到死路才回头；BFS 会同时向所有方向扩展，像水波纹一样。
2. 路径长度：DFS 找到的路径可能很长（不是最短）；BFS 找到的一定是最短路径。
3. 探索格子数：DFS 可能探索很多死路；BFS 更「聪明」，探索的格子通常更少（在这个例子中）。

⚖️ DFS vs BFS 全面对比

对比项 🟣 DFS 深度优先 🟢 BFS 广度优先
核心策略 一条路走到黑，碰壁再回头 一层一层扩展，先近后远
数据结构 栈（Stack）/ 递归 队列（Queue）
顺序特点 先深后广 先近后远
最短路径 ❌ 不保证最短 ✅ 无权图中最短
时间复杂度 O(V + E) O(V + E)
空间复杂度 O(V)（递归深度） O(V)（队列大小）
适合问题 全排列、组合、连通块、走迷宫 最短路、最少步数、层序遍历
实现方式 递归（简洁好写） while 循环 + 队列
比喻 🏰 探索洞穴 🌊 水波纹扩散
💡 怎么选？
需要最短路径 / 最少步数？ → 用 BFS
需要找所有方案 / 排列组合？ → 用 DFS
需要连通块 / 能否到达？ → DFS 和 BFS 都行
不确定？ → 先想清楚需要「最短」还是「所有方案」，再做选择

📝 经典例题精讲

这些是 GESP 六级常考的搜索题型，一定要掌握！

DFS · 回溯
例题一：全排列问题
输入一个正整数 n（1 ≤ n ≤ 8），按照字典序输出 1~n 的所有全排列。
输入
3
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
📖 查看解析与代码

思路：这是一道经典的 DFS 回溯题。想象有 n 个位置，每个位置放一个数字。用 DFS 逐个位置填数字，填完 n 个就输出一个排列。关键是回溯——填完一个排列后，要撤销选择，尝试其他数字。

🎯 回溯三步曲 1. 选择：在当前位置选一个没用过的数字
2. 递归：进入下一个位置
3. 撤销：回到当前位置，换下一个数字试试（这就是回溯！）
C++ · 全排列 DFS
#include <iostream>
using namespace std;

int n;
int path[10];       // 存当前排列
bool used[10];     // 标记数字是否用过

void dfs(int step) {
    if (step == n) {   // 排列完成，输出
        for (int i = 0; i < n; i++)
            cout << path[i] << " ";
        cout << endl;
        return;
    }
    // 尝试每个数字
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            path[step] = i;      // ① 选择
            used[i] = true;
            dfs(step + 1);      // ② 递归
            used[i] = false;     // ③ 撤销（回溯！）
        }
    }
}

int main() {
    cin >> n;
    dfs(0);
    return 0;
}
⚠️ 易错点：第 ③ 步 used[i] = false 千万不能忘！这就是回溯的核心——撤销选择，让这个数字可以在其他分支中被使用。忘了这一步，只能输出一个排列。
BFS · 最短路
例题二：迷宫最短路径
给定一个 n×m 的迷宫，'.' 表示路，'#' 表示墙，'S' 表示起点，'E' 表示终点。求从起点到终点的最少步数。如果不能到达，输出 -1。
输入
3 3
S..
.#.
..E
输出
4
📖 查看解析与代码

思路：求最少步数 → 用 BFS！因为 BFS 一层一层扩展，第一次到达终点时的步数就是最少的。

用 dist[i][j] 记录从起点到 (i,j) 的距离，初始全设为 -1 表示未访问。起点距离设为 0，每次扩展时距离 +1。

C++ · 迷宫最短路 BFS
#include <iostream>
#include <queue>
using namespace std;

int n, m;
char maze[100][100];
int dist[100][100];  // 距离数组，-1 表示未访问
int dx[] = {0, 0, 1, -1};  // 右 左 下 上
int dy[] = {1, -1, 0, 0};

int bfs(int sx, int sy, int ex, int ey) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        if (x == ex && y == ey)
            return dist[x][y];  // 找到终点！

        // 尝试四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 检查边界、墙、是否访问过
            if (nx >= 0 && nx < n && ny >= 0 && ny < m
                && maze[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return -1;  // 无法到达
}

int main() {
    cin >> n >> m;
    int sx, sy, ex, ey;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maze[i][j];
            if (maze[i][j] == 'S') { sx = i; sy = j; }
            if (maze[i][j] == 'E') { ex = i; ey = j; }
            dist[i][j] = -1;
        }
    }
    cout << bfs(sx, sy, ex, ey) << endl;
    return 0;
}
💡 方向数组技巧
dx[] 和 dy[] 是方向数组，表示四个方向：右、左、下、上。用一个 for 循环就能遍历四个方向，比写四次 if 简洁多了！这是搜索题的常用技巧。
DFS · 连通块
例题三：岛屿数量
给定一个 n×m 的网格，'1' 表示陆地，'0' 表示水。上下左右相连的 '1' 算一个岛屿。求岛屿的数量。
输入
4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
输出
3
📖 查看解析与代码

思路：遍历整个网格，每发现一个没访问过的 '1'，就找到了一个新岛屿。然后用 DFS 把这个岛屿上所有的 '1' 都标记为已访问（这叫感染/Flood Fill）。最后数一共找到了多少个新岛屿。

C++ · 岛屿数量 DFS
#include <iostream>
using namespace std;

int n, m;
char grid[100][100];
bool vis[100][100];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void dfs(int x, int y) {
    vis[x][y] = true;  // 标记为已访问
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        // 边界检查 + 是陆地 + 没访问过
        if (nx >= 0 && nx < n && ny >= 0 && ny < m
            && grid[nx][ny] == '1' && !vis[nx][ny]) {
            dfs(nx, ny);  // 递归访问相连的陆地
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 发现一个新岛屿！
            if (grid[i][j] == '1' && !vis[i][j]) {
                dfs(i, j);  // 把整个岛屿标记
                count++;    // 岛屿数量 +1
            }
        }
    }
    cout << count << endl;
    return 0;
}
💡 Flood Fill 模式
这种「从一个点出发，DFS 把所有相连的相同格子都标记」的技巧叫 Flood Fill（泛洪填充）。就像油漆桶工具——点一个格子，所有相连的相同颜色格子都被填充。这在 GESP 中非常常见！

🎯 互动测验

来检验一下你的学习成果吧！

📚 知识总结

🟣
DFS 深度优先
栈/递归 · 一条路走到黑
回溯是灵魂
适合：排列、组合、连通块
🟢
BFS 广度优先
队列 · 一层层扩展
能找最短路径
适合：最短路、最少步数
📋
visited 数组
防止重复访问
防止无限循环
入队/递归时立即标记
🧭
方向数组
dx/dy 表示四个方向
一个循环遍历所有方向
代码简洁不易错
⏮️
回溯三步曲
① 做选择
② 递归
③ 撤销选择（恢复状态）
⚡
复杂度
DFS 和 BFS 都是
O(V + E) 时间
O(V) 空间

🎓 你已经掌握了 DFS 和 BFS！

多练习，多画图，多模拟。搜索算法的关键不是背代码，而是理解「怎么走」和「为什么这么走」。
祝你 GESP 六级考试顺利！💪