🐭 DFS 深搜 & 🌀 BFS 广搜 通关站

0先看这里：搜索到底在搜什么？

深搜和广搜，是两个“在迷宫/地图/选择树里找答案”的方法。它们把每一步选择当作「岔路口」，一个接一个地试。

GESP 六级考纲原话：掌握深度优先搜索（DFS）、宽度优先搜索（BFS）的概念及应用，能根据现实问题选择合适的搜索算法。所以考试主要看三件事：

• 会用递归写 DFS（也会看栈 stack）；会用队列 queue写 BFS；
• 会加 visited/used 标记，防止重复访问死循环；
• 拿到题目能判断：这题该用 DFS 还是 BFS？

下面第 1 节先热身，把两个「秘密武器」栈和队列搞定，后面的动画就能看得明明白白。

1热身：栈 Stack 和队列 Queue

DFS 的「退回来」靠栈，BFS 的「一圈一圈」靠队列。先动手玩一玩！

🪵 栈 Stack —— 像叠盘子：后放上去的，先拿走（后进先出 LIFO）

盘子 压入 = 放在最上面；弹出 = 只能拿走最上面的。想拿最下面的盘子？不行，得一个个来。

🚌 队列 Queue —— 像排队买奶茶：先来的先买（先进先出 FIFO）

排队的人 入队 = 站到最后面；出队 = 最前面的人离开。BFS 的「一圈一圈扩散」就是按入队的先后一个个处理。

C++ 里怎么用？

#include <bits/stdc++.h>   // 比赛常用，一次包含所有头文件
using namespace std;

int main() {
    // ---- 栈 stack：后进先出 ----
    stack<int> s;
    s.push(1);   s.push(2);   s.push(3);
    int top = s.top();        // top = 3，只看不拿走
    s.pop();                  // 真正拿走 3
    s.empty();                // 空了吗？现在 false
    s.size();                 // 现在有几个？2 个

    // ---- 队列 queue：先进先出 ----
    queue<int> q;
    q.push(1);   q.push(2);   q.push(3);
    int front = q.front();    // front = 1，最前面的
    q.pop();                  // 拿走 1
    q.empty();                // false
    q.size();                 // 2 个

    // ---- 存坐标 (x,y)：用 pair ----
    queue<pair<int,int>> q2;
    q2.push(make_pair(2, 3));
    int x = q2.front().first;    // x = 2
    int y = q2.front().second;   // y = 3
    return 0;
}

2DFS 深度优先搜索

2.1 模板：DFS 就是「递归 + 标记 + 回溯」

你有递归基础，那 DFS 只差两个小零件：① used/vis 标记防止重复走；② 回溯时撤销标记（有些题需要）。

void dfs(当前状态) {
    if (达到目标/边界) { 记录答案; return; }
    for (每一个可以做的选择) {
        if (这个选择被用过了) continue;   // ① 标记检查
        used[选择] = true;                // ① 标记
        做这个选择;
        dfs(下一步);                      // 递归往下走
        used[选择] = false;               // ② 回溯：撤销标记！
    }
}

2.2 🐭 动画：DFS 走迷宫（看栈怎么「进进出出」）

绿色是起点，红色是终点。深搜的策略是固定顺序「右 → 下 → 左 → 上」，一条道走到黑，撞墙就出栈回退。左边是栈里存的格子。

注意看：深搜经常「东撞西撞」，找到的路径不一定最短！但它的好处是——只要有条路，就一定能找到，而且能顺便把所有走法都试一遍。

2.3 递归版代码（考试最爱考）

上面的动画是「手写栈」版（方便你看栈怎么动）。考试里直接用递归更省事，因为递归就是系统帮你用栈！

#include <bits/stdc++.h>
using namespace std;

int n, m;
char mp[105][105];        // 地图：'#'墙  '.'路
bool vis[105][105];
int dx[4] = {0, 1, 0, -1};   // 右 下 左 上
int dy[4] = {1, 0, -1, 0};

// 深搜：看看能不能从 (x,y) 走到终点
bool dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return false;  // 越界
    if (mp[x][y] == '#') return false;                      // 撞墙
    if (vis[x][y]) return false;                            // 走过（别绕圈）
    vis[x][y] = true;                                       // 标记！
    if (mp[x][y] == 'T') return true;                       // 到终点啦

    for (int k = 0; k < 4; k++) {
        if (dfs(x + dx[k], y + dy[k])) return true;         // 只要有一步能到终点
    }
    return false;                                           // 四个方向都不行
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> mp[i];
    int sx, sy;                                             // 找起点 S
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (mp[i][j] == 'S') { sx = i; sy = j; }
    cout << (dfs(sx, sy) ? "YES" : "NO") << endl;
    return 0;
}

2.4 🌳 动画：DFS 枚举全排列（看递归树怎么长）

把 1、2、3 排成所有可能的顺序（3! = 6 种）。DFS 会从「起点」一层层往下选数，选完一层就往深处走，走到底就输出一种排列，然后回溯换下一个数。这就是递归树！

// 全排列：把 1~n 的所有排列方式都输出（DFS 经典题）
#include <bits/stdc++.h>
using namespace std;

int n;
int a[15];                 // a[k] 存第 k 个位置放哪个数
bool used[15];             // used[i]：数字 i 用过了吗

void dfs(int k) {          // 准备填第 k 个位置
    if (k > n) {           // 填完了，输出这一种排列
        for (int i = 1; i <= n; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;    // 数字 i 已经用过了
        used[i] = true;           // 标记
        a[k] = i;
        dfs(k + 1);               // 递归填下一个位置
        used[i] = false;          // 回溯：撤销标记，让 i 给别的方案用
    }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}

3BFS 广度优先搜索

3.1 模板：BFS = 队列 + 一层层记录距离

void bfs(起点) {
    queue<状态> q;
    q.push(起点);
    dist[起点] = 0;              // 起点距离是 0
    while (!q.empty()) {
        取出队头 now;
        for (每个邻居 nxt) {
            if (nxt 越界 / 撞墙 / 已访问) continue;
            dist[nxt] = dist[now] + 1;   // 层数 + 1
            q.push(nxt);                 // 入队，等会儿处理它
        }
    }
}

3.2 🌀 动画：同一个迷宫，用 BFS 走一遍

看颜色！每个格子的颜色代表它离起点几「层」：蓝色离得近，越往外越暖色。队头先出队，把它的 4 个邻居入队，一层一层推进。

对比一下：BFS 走的路线更「整齐」，像波纹一样铺开，找到终点时走的步数一定是最少的。

3.3 BFS 求最短路径（GESP 超高频）

// 迷宫最短路：从 S 到 T 最少走几步（BFS 经典题）
#include <bits/stdc++.h>
using namespace std;

int n, m;
char mp[105][105];        // '#':墙  '.':路  'S':起点  'T':终点
int step[105][105];       // step[x][y] = 到 (x,y) 的步数，-1 表示没到过
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
queue<pair<int,int>> q;

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 >> mp[i][j];
            if (mp[i][j] == 'S') { sx = i; sy = j; }
            if (mp[i][j] == 'T') { ex = i; ey = j; }
        }

    memset(step, -1, sizeof(step));   // 全部标记成"没到过"
    q.push(make_pair(sx, sy));
    step[sx][sy] = 0;                 // 起点 0 步

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

        if (x == ex && y == ey) {     // 第一次到终点 = 最短！
            cout << step[x][y] << endl;
            return 0;
        }

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;  // 越界
            if (mp[nx][ny] == '#') continue;                       // 墙
            if (step[nx][ny] != -1) continue;                      // 已经走过了
            step[nx][ny] = step[x][y] + 1;                         // 层数 + 1
            q.push(make_pair(nx, ny));
        }
    }
    cout << -1 << endl;          // 队列空了还没到 = 走不到
    return 0;
}

4DFS vs BFS：什么时候用哪个？

小测试：你来当裁判！点击选项看对不对

5图 & 二叉树上的搜索（六级必考）

迷宫是「图」的一种特例。真正的图（Graph）用点 + 边表示，存法最常用邻接表。看看在这张 6 个点的图上，DFS 和 BFS 分别怎么走——可以切换！

5.1 🕸️ 动画：图上的 DFS / BFS 遍历

深搜会沿着一条边「钻」到底再回头；广搜则从 A 出发，一层层把「朋友的朋友」都找到。

5.2 邻接表建图 + 遍历代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
vector<int> g[N];        // 邻接表：g[x] 存所有和 x 相连的点
bool vis[N];

// DFS 遍历（递归）：访问一个点，再访问它没去过的邻居
void dfs(int x) {
    vis[x] = true;
    cout << x << " ";                       // 访问顺序
    for (int i = 0; i < (int)g[x].size(); i++) {
        int y = g[x][i];
        if (!vis[y]) dfs(y);
    }
}

// BFS 遍历：队列一层层走
void bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        cout << x << " ";                   // 访问顺序
        for (int i = 0; i < (int)g[x].size(); i++) {
            int y = g[x][i];
            if (!vis[y]) {
                vis[y] = true;
                q.push(y);
            }
        }
    }
}

int main() {
    int n, m;                    // n 个点，m 条边
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);       // 无向图：两边都连
        g[v].push_back(u);
    }
    dfs(1);
    return 0;
}

5.3 🌲 二叉树上的搜索（对应关系要背下来）

// 二叉树：用指针存左右孩子
struct Node {
    int val;
    Node *left, *right;
};

// 前序遍历（DFS）
void preorder(Node *t) {
    if (t == NULL) return;
    cout << t->val << " ";      // 先根
    preorder(t->left);           // 再左
    preorder(t->right);          // 后右
}

// 层序遍历（BFS）：用队列！
void levelorder(Node *root) {
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node *t = q.front(); q.pop();
        cout << t->val << " ";
        if (t->left)  q.push(t->left);
        if (t->right) q.push(t->right);
    }
}

6例题精讲（GESP 六级风格）

例 1：全排列【DFS】⭐ 必背

题意：输入 n，按字典序输出 1~n 的所有排列，每行一个。

思路：用 dfs(k) 填第 k 位；used 标记哪个数用过；填满就输出；回溯时撤销标记。上面 2.4 节有完整代码，这里是另一个常见写法：

#include <bits/stdc++.h>
using namespace std;
int n, a[15]; bool used[15];

void dfs(int k) {
    if (k == n) {                       // 0~n-1 位都填好了
        for (int i = 0; i < n; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (used[i]) continue;
        used[i] = true;
        a[k] = i;
        dfs(k + 1);
        used[i] = false;                // 回溯！
    }
}
int main() { cin >> n; dfs(0); return 0; }

例 2：骑士游历·最少步数【BFS】⭐ 必背

题意：在 8×8 棋盘上，国际象棋的「马」（走日字）从 (x1,y1) 跳到 (x2,y2)，最少几步？

思路：马有 8 种跳法，就是 8 个「方向」。BFS 从起点扩散，第一次到终点就是最少步数。

#include <bits/stdc++.h>
using namespace std;

int step[9][9];
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
queue<pair<int,int>> q;

int main() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    memset(step, -1, sizeof(step));
    q.push(make_pair(x1, y1));
    step[x1][y1] = 0;

    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        if (x == x2 && y == y2) {
            cout << step[x][y] << endl;
            return 0;
        }
        for (int k = 0; k < 8; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > 8 || ny < 1 || ny > 8) continue;
            if (step[nx][ny] != -1) continue;
            step[nx][ny] = step[x][y] + 1;
            q.push(make_pair(nx, ny));
        }
    }
    cout << -1 << endl;
    return 0;
}

例 3：细胞计数【DFS/BFS 连通块】⭐ 必背

题意：n×m 的地图，'1' 是细胞，上下左右相邻的 1 算同一个细胞。求共有多少个细胞？

思路：扫一遍地图，遇到没访问过的 1 就计数 +1，然后 DFS 把整块连通的一起「淹没」。

#include <bits/stdc++.h>
using namespace std;

int n, m, cnt;
char mp[105][105];
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (mp[x][y] != '1') return;      // 不是细胞 或 已经被淹没
    mp[x][y] = '0';                   // 淹没它，防止重复计数
    for (int k = 0; k < 4; k++) dfs(x + dx[k], y + dy[k]);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> mp[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (mp[i][j] == '1') { cnt++; dfs(i, j); }
    cout << cnt << endl;
    return 0;
}

例 4：二叉树的遍历【DFS/BFS】

题意：给一棵二叉树（用数组存：1 号是根，2i 是左孩子，2i+1 是右孩子，-1 表示没有），输出前序遍历和层序遍历。

#include <bits/stdc++.h>
using namespace std;

int n;
int lc[1005], rc[1005];     // lc[i], rc[i]：i 的左右孩子

void preorder(int x) {      // 前序：根 左 右
    if (x == -1) return;
    cout << x << " ";
    preorder(lc[x]);
    preorder(rc[x]);
}

void levelorder(int root) { // 层序：BFS
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        cout << x << " ";
        if (lc[x] != -1) q.push(lc[x]);
        if (rc[x] != -1) q.push(rc[x]);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> lc[i] >> rc[i];
    preorder(1);  cout << endl;
    levelorder(1); cout << endl;
    return 0;
}

7练习题（先自己做，再点开答案）

建议：每道题先想 ① 用 DFS 还是 BFS？② 需要标记吗？③ 需要回溯吗？然后再动手写。

#include <bits/stdc++.h>
using namespace std;
int a[10];   // a[k] 存第 k 个选的数

void dfs(int k, int last) {   // 选第 k 个，只能从 last+1 开始
    if (k == 4) {
        for (int i = 1; i <= 3; i++) cout << a[i] << " ";
        cout << endl;
        return;
    }
    for (int i = last + 1; i <= 5; i++) {
        a[k] = i;
        dfs(k + 1, i);
    }
}
int main() { dfs(1, 0); return 0; }

#include <bits/stdc++.h>
using namespace std;
int n, m; char mp[105][105]; bool vis[105][105];
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
bool dfs(int x, int y) {
    if (x<0||x>=n||y<0||y>=m) return false;
    if (mp[x][y]=='#') return false;
    if (vis[x][y]) return false;
    vis[x][y] = true;
    if (mp[x][y]=='T') return true;
    for (int k=0;k<4;k++) if (dfs(x+dx[k],y+dy[k])) return true;
    return false;
}
int main() {
    cin>>n>>m;
    int sx=0,sy=0;
    for (int i=0;i<n;i++) for (int j=0;j<m;j++){ cin>>mp[i][j]; if(mp[i][j]=='S'){sx=i;sy=j;} }
    cout<<(dfs(sx,sy)?"YES":"NO")<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m, cnt; char mp[105][105];
int dx[8] = {-1,-1,-1,0,0,1,1,1};
int dy[8] = {-1,0,1,-1,1,-1,0,1};
void dfs(int x, int y) {
    if (x<0||x>=n||y<0||y>=m) return;
    if (mp[x][y]!='W') return;
    mp[x][y]='.';
    for (int k=0;k<8;k++) dfs(x+dx[k],y+dy[k]);
}
int main() {
    cin>>n>>m;
    for (int i=0;i<n;i++) cin>>mp[i];
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            if (mp[i][j]=='W'){ cnt++; dfs(i,j); }
    cout<<cnt<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m; char mp[105][105];
int step[105][105];
pair<int,int> pre[105][105];      // pre[x][y]：从哪个格子来的
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
queue<pair<int,int>> q;

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>>mp[i][j];
        if(mp[i][j]=='S'){sx=i;sy=j;}
        if(mp[i][j]=='T'){ex=i;ey=j;}
    }
    memset(step,-1,sizeof(step));
    q.push(make_pair(sx,sy)); step[sx][sy]=0;
    while(!q.empty()){
        int x=q.front().first, y=q.front().second; q.pop();
        if(x==ex&&y==ey) break;
        for(int k=0;k<4;k++){
            int nx=x+dx[k], ny=y+dy[k];
            if(nx<0||nx>=n||ny<0||ny>=m) continue;
            if(mp[nx][ny]=='#') continue;
            if(step[nx][ny]!=-1) continue;
            step[nx][ny]=step[x][y]+1;
            pre[nx][ny]=make_pair(x,y);   // 记住"来路"
            q.push(make_pair(nx,ny));
        }
    }
    if(step[ex][ey]==-1){ cout<<-1<<endl; return 0; }
    cout<<step[ex][ey]<<endl;

    // 用栈把终点倒推回起点，再倒序输出
    stack<pair<int,int>> path;
    int x=ex, y=ey;
    while(!(x==sx&&y==sy)){
        path.push(make_pair(x,y));
        int tx=pre[x][y].first, ty=pre[x][y].second;
        x=tx; y=ty;
    }
    path.push(make_pair(sx,sy));
    while(!path.empty()){
        cout<<path.top().first<<" "<<path.top().second<<endl;
        path.pop();
    }
    return 0;
}

// 思路：每个状态是一个 9 位数（0 表示空格）
// 用 unordered_map<int,int> dist 记"状态 - 步数"
// BFS：
//   取出队头状态 s，找到 0 的位置 p
//   0 和上下左右的数字交换，得到新状态 t
//   如果 dist 里没有 t，dist[t] = dist[s]+1，入队
// 目标状态是 123456780，第一次出现就返回步数
// 注意：判断 0 能不能往上/下/左/右移，
//       要检查 p 在第几行第几列，别让 0 从第 2 行直接"穿"到第 4 列。

#include <bits/stdc++.h>
using namespace std;
int lc[1005], rc[1005], dep[1005], k;

void bfs_level() {
    queue<int> q;
    q.push(1); dep[1] = 1;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (dep[x] == k) cout << x << " ";
        if (lc[x] != -1) { dep[lc[x]] = dep[x] + 1; q.push(lc[x]); }
        if (rc[x] != -1) { dep[rc[x]] = dep[x] + 1; q.push(rc[x]); }
    }
}
// main 里：读入 n 个节点的左右孩子，读入 k，调用 bfs_level()

8考试小贴士（GESP 实战）

• 先判算法：「最短/最少/最近」→ BFS；「所有方案/排列/判断能否」→ DFS。判错了整题白写。
• mark 标记三问：要标记吗？标记放哪（入队时/进函数时）？要撤销吗（枚举方案要，判断连通性不要）？
• 边界检查永远写在最前面：nx<0||nx>=n||ny<0||ny>=m，先挡越界再看墙，顺序别反。
• 会估算复杂度：n ≤ 10~15 常是 DFS 枚举（阶乘级）；n·m ≤ 10^4~10^6 可 BFS（线性级）。GESP 选择题常考「这种规模用哪种算法」。
• 大图用邻接表：n 上万时别用邻接矩阵（会爆内存），用 vector<int> g[N]。
• 输出格式要抠：空格、换行、多输出一个空格都可能被判 0 分。样例过了也要自己造数据测。
• 递归爆栈：递归深度几万层会栈溢出，六级一般不会这么变态，但心里有数。