用动画和互动，彻底搞懂深度优先搜索和广度优先搜索
想象你站在一个巨大的迷宫入口，需要找到出口。搜索算法就是你"探索迷宫"的策略——决定你先走哪条路、后走哪条路、什么时候回头。
在 C++ 编程中，我们经常需要在树或图这种数据结构中查找信息。两种最基本的搜索策略就是：
像走迷宫时一条路走到底，走到死路再回头换方向。用"栈"或"递归"实现。
像水波纹一样一层一层向外扩展，先访问所有近距离的，再访问远的。用"队列"实现。
GESP 六级考试中，DFS 和 BFS 是核心考点。它们能解决的问题包括：遍历树/图、找连通块、走迷宫求最短路径、 Flood Fill 填色等。掌握它们，很多难题都能迎刃而解！
在学搜索之前，我们先搞清楚搜索是在什么上面进行的。
图由节点（顶点）和边组成。节点代表事物，边代表事物之间的连接关系。
比如：城市是节点，公路是边；人是节点，朋友关系是边。在 C++ 中，我们通常用邻接表来存储图：
// 用 vector 数组存邻接表 vector<int> adj[100]; // adj[i] 存节点 i 的所有邻居 // 添加一条边 u -> v adj[u].push_back(v); adj[v].push_back(u); // 无向图需要双向
树是一种特殊的图：没有环，连通，且有唯一的前驱（父节点）。树有且只有一个根节点，每个节点可以有多个子节点。
树是图的一种特殊情况，所以对树适用的搜索方法，对图也适用。在 GESP 考试中，很多题目都是在树上进行搜索的。
访问（visit）：到达一个节点，读取或处理它的数据。
遍历（traversal）：按照某种顺序，访问图或树中的所有节点，每个节点只访问一次。
DFS 和 BFS 就是两种不同的遍历顺序。接下来我们逐一深入学习！
DFS 的策略是：从起点出发，沿着一条路一直走，走到走不动了（没有未访问的邻居），就退回上一个岔路口，换一条路继续走。就像走迷宫时，你沿着左手法则一直走，直到撞墙才回头。
1. 访问当前节点 —— 标记为已访问，处理它的数据
2. 递归访问邻居 —— 对每个未访问的邻居，继续 DFS
3. 回溯 —— 所有邻居都访问完了，返回上一层
点击"播放"看 DFS 如何遍历这棵树。注意观察右侧的栈（递归调用栈）如何变化，以及节点的访问顺序。
DFS 最常用的实现方式是递归。递归天然地帮我们管理了"调用栈"——每深入一层，就多一层函数调用。
bool visited[105]; // 标记每个节点是否已访问 vector<int> adj[105]; // 邻接表存图 // DFS 函数：访问节点 u void dfs(int u) { visited[u] = true; // ① 标记当前节点已访问 cout << u << " "; // 处理当前节点（比如输出） // ② 遍历 u 的所有邻居 for (int v : adj[u]) { if (!visited[v]) { // 只访问没去过的邻居 dfs(v); // ③ 递归：深入访问邻居 } } // ④ 所有邻居都访问完了，函数自动返回（回溯） } // 主函数中调用 int main() { // ... 建图省略 ... memset(visited, false, sizeof(visited)); dfs(1); // 从节点 1 开始 DFS return 0; }
visited 数组：这是 DFS 最关键的部分！没有它，程序会在环里无限循环。每次访问节点前，先检查 visited，已访问的就跳过。
for (int v : adj[u])：C++11 的范围 for 循环，遍历 u 的所有邻居 v。
dfs(v)：递归调用。这一行就是"深入"的体现——不等其他邻居，先一头扎进 v。
函数结束自动回溯：当 for 循环结束（所有邻居都处理完），函数返回到上一层调用，这就是"回溯"。
忘记标记 visited：会导致死循环和栈溢出！这是最常犯的错误。
递归层数太深：如果图是一条长链（比如 10 万个节点的链表），递归可能栈溢出。这时需要改用非递归（用栈）的写法。
BFS 的策略是：先访问起点，然后访问起点的所有邻居（第一层），再访问邻居的邻居（第二层）……像水波纹一样一圈一圈向外扩展。BFS 总是先访问距离起点近的节点。
BFS 使用队列（Queue）来实现。队列的特点是先进先出（FIFO）——先加入队列的节点先被处理。这正好符合"一层一层"的顺序：
1. 起点入队，标记已访问
2. 队头节点出队，访问它
3. 把它的所有未访问邻居加入队尾
4. 重复 2-3，直到队列为空
点击"播放"看 BFS 如何遍历同一棵树。注意观察右侧的队列如何变化，对比 DFS 的不同。
BFS 用队列实现，不使用递归。C++ 中用 queue 容器。
bool visited[105]; vector<int> adj[105]; void bfs(int start) { queue<int> q; // 创建队列 q.push(start); // ① 起点入队 visited[start] = true; // 标记起点已访问 while (!q.empty()) { // ② 队列不空就继续 int u = q.front(); // 取出队头 q.pop(); // 队头出队 cout << u << " "; // 处理当前节点 // ③ 遍历 u 的所有邻居 for (int v : adj[u]) { if (!visited[v]) { // 未访问的邻居 visited[v] = true; // 标记已访问 q.push(v); // 加入队尾 } } } // ④ 队列为空，BFS 结束 }
queue<int> q：C++ STL 的队列，先进先出。push() 入队，front() 看队头，pop() 出队。
先标记再入队：注意！是先把邻居标记为 visited，再 push 进队列。如果等出队时才标记，同一个节点可能被多次加入队列，导致效率降低甚至出错。
while (!q.empty())：循环条件——只要队列里还有节点，就继续处理。
在无权图（每条边长度相同）中，BFS 第一次到达某个节点时，走的路径就是最短路径！因为 BFS 是按距离层层扩展的，先到达的一定是最短的。
这是 DFS 做不到的——DFS 可能绕远路先到一个节点。所以求最短路径用 BFS，不用 DFS。
学完两个算法，我们来做一个清晰的对比，帮你记住它们的区别和适用场景。
| 对比项 | DFS 深度优先 | BFS 广度优先 |
|---|---|---|
| 探索策略 | 一条路走到底，走不通再回头 | 一层一层扩展，由近及远 |
| 数据结构 | 栈（递归调用栈 / 手动栈） | 队列 |
| 实现方式 | 递归最常见，也可用栈迭代 | while 循环 + 队列 |
| 访问顺序 | 先深后广，类似前序遍历 | 先近后远，按层遍历 |
| 最短路径 | 不一定是最短路径 | 无权图中一定是最短路径 |
| 空间复杂度 | O(深度)，最坏 O(N) | O(宽度)，最坏 O(N) |
| 时间复杂度 | O(V + E) | O(V + E) |
| 适用场景 | 找所有方案、排列组合、连通块、拓扑排序 | 最短路径、最少步数、层序遍历 |
| 记忆口诀 | "不撞南墙不回头" | "近水楼台先得月" |
需要找最短路径 / 最少步数 → 选 BFS
需要找所有可能的方案 / 枚举排列组合 → 选 DFS
需要按层处理 / 层序遍历 → 选 BFS
图的深度可能很大、宽度很宽 → DFS 省空间
不确定选哪个 → 两种都试试，看哪个更自然
让我们用一个真实的迷宫来对比两种搜索策略的不同"风格"。同样的迷宫，DFS 和 BFS 探索的路径完全不同！
绿色是起点，红色是终点，黑色是墙壁。点击"播放"看两种算法如何分别探索迷宫。
DFS（左）会一头扎进一条路，碰壁才回头，探索路径像一条蛇。BFS（右）像水波纹一样均匀扩散，最终找到最短路径。
DFS 探索了很多"弯路"，有些区域被反复试探。但它在代码上更简洁（递归几行就搞定）。
BFS 探索得很"整齐"，一层一层推进。它找到的路径一定是最短的，但探索的节点可能更多。
在 GESP 考试中，迷宫求最短步数 → 用 BFS；迷宫求方案数 / 枚举所有路径 → 用 DFS。
现在轮到你来操作了！你可以自己创建节点和边，然后选择 DFS 或 BFS 来遍历你建的图。
① 添加节点：在空白区域点击，创建一个新节点
② 连接节点：切换到"连线"模式，依次点击两个节点，它们之间就会连一条边
③ 设置起点：切换到"设起点"模式，点击一个节点设为搜索起点
④ 运行算法：选择 DFS 或 BFS，点击"开始搜索"看动画！
下面是几道 GESP 风格的练习题，从易到难。先自己思考，再点击"查看答案"对照。
有一棵树，根节点为 1，邻接表如下：
adj[1] = {2, 3} adj[2] = {1, 4, 5} adj[3] = {1, 6} adj[4] = {2} adj[5] = {2} adj[6] = {3}
从节点 1 开始进行 DFS（邻居按从小到大顺序访问），输出的访问顺序是什么？
A) 1 2 3 4 5 6 B) 1 2 4 5 3 6 C) 1 3 6 2 5 4 D) 1 2 4 5 3 6
解析过程：
1. 访问 1，邻居是 {2, 3}，先走 2
2. 访问 2，邻居是 {1, 4, 5}，1 已访问，先走 4
3. 访问 4，邻居是 {2}，2 已访问，回溯到 2
4. 回到 2，继续走 5，访问 5，回溯到 2，回溯到 1
5. 回到 1，走 3，访问 3，邻居 {1, 6}，走 6，访问 6
最终顺序：1 → 2 → 4 → 5 → 3 → 6
注意：B 和 D 看起来一样，但 D 选项也是 1 2 4 5 3 6，所以 B 和 D 都正确（本题选 B）。
使用与题目一相同的树，从节点 1 开始进行 BFS（邻居按从小到大顺序入队），输出的访问顺序是什么？
A) 1 2 3 4 5 6 B) 1 2 4 5 3 6 C) 1 2 3 4 6 5 D) 1 3 2 6 4 5
解析过程：
1. 起点入队：队列 = [1]，访问 1，邻居 {2,3} 入队 → 队列 = [2, 3]
2. 出队 2，访问 2，邻居 {4,5} 入队 → 队列 = [3, 4, 5]
3. 出队 3，访问 3，邻居 {6} 入队 → 队列 = [4, 5, 6]
4. 出队 4，访问 4（无新邻居）→ 队列 = [5, 6]
5. 出队 5，访问 5 → 队列 = [6]
6. 出队 6，访问 6 → 队列 = []
最终顺序：1 → 2 → 3 → 4 → 5 → 6（按层遍历）
给定一个 N 个节点、M 条边的无向图，问图中有多少个连通块（连通分量）？
连通块的定义：块内任意两个节点可以互相到达，块与块之间不连通。
请写出核心代码思路。
对每个未访问的节点启动一次 DFS/BFS，每次启动就是一个新的连通块。
bool visited[105]; vector<int> adj[105]; void dfs(int u) { visited[u] = true; for (int v : adj[u]) if (!visited[v]) dfs(v); } int main() { int n, m; cin >> n >> m; // 读入 m 条边建图... int count = 0; for (int i = 1; i <= n; i++) { if (!visited[i]) { // 发现一个未访问的节点 count++; // 新的连通块！ dfs(i); // 把整个连通块标记为已访问 } } cout << count << endl; return 0; }
关键点：每次外层循环发现一个未访问的节点，就意味着找到了一个新的连通块，然后 DFS 会把整个连通块都"染上色"（标记已访问），下次就不会重复计数。
有一个 N×M 的迷宫，'.' 表示通路，'#' 表示墙壁，'S' 表示起点，'E' 表示终点。每次可以向上下左右移动一格。求从 S 到 E 的最少步数。
应该用 DFS 还是 BFS？请写出核心代码。
因为每一步的"代价"相同（都是 1 步），BFS 层层扩展，第一次到达终点时的层数就是最短步数。
int dx[] = {0, 0, 1, -1}; // 四个方向 int dy[] = {1, -1, 0, 0}; bool vis[105][105]; int dist[105][105]; // 记录到每个格子的距离 int bfs(int sx, int sy, int ex, int ey) { queue<pair<int,int>> q; q.push({sx, sy}); vis[sx][sy] = true; dist[sx][sy] = 0; while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (x == ex && y == ey) return dist[x][y]; // 到达终点 for (int i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < N && ny >= 0 && ny < M && !vis[nx][ny] && maze[nx][ny] != '#') { vis[nx][ny] = true; dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } } } return -1; // 无法到达 }
关键点：用 dist 数组记录每个格子到起点的距离，每次扩展时 dist[nx][ny] = dist[x][y] + 1。到达终点时直接返回，就是最短步数。
用 DFS 枚举 1~N 的所有全排列（N ≤ 8）。例如 N=3 时，输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
请写出核心代码。
这是经典的 DFS 回溯问题：逐个位置填数，填满了就输出，然后回溯换下一个数。
int n; bool used[10]; int path[10]; void dfs(int pos) { if (pos == n) { // 填满了 n 个位置 for (int i = 0; i < n; i++) cout << path[i] << " "; cout << endl; return; // 回溯 } for (int i = 1; i <= n; i++) { if (!used[i]) { used[i] = true; // 选 i 放入当前位置 path[pos] = i; dfs(pos + 1); // 递归填下一个位置 used[i] = false; // 回溯：撤销选择！ } } }
关键点：这是 回溯法的核心模式——"选择 → 递归 → 撤销选择"。used[i] = false 这行就是回溯，它让上一层的循环能继续尝试其他数字。DFS + 回溯 = 枚举所有方案！
做完上面的练习，来测测你掌握了多少！共 5 道选择题。