C++ 算法技巧 — 搜索 (Search: DFS & BFS)

章节概述

深度优先搜索 (DFS) 和广度优先搜索 (BFS) 是遍历状态空间的基本方法，应用广泛。
DFS 用栈（通常递归实现）深入探索；BFS 用队列逐层扩展，天然求最短路径。

核心原理

1. DFS — 深度优先

数学本质：深度优先遍历树/图/状态空间，回溯时恢复上下文。

dfs(state):
    若 state 是目标: 记录/返回
    对每个合法后继 state':
        dfs(state')
        回溯: 恢复修改的状态

复杂度:

图遍历: O(V+E)
排列枚举: O(n!)
组合枚举: O(2

2. BFS — 广度优先

数学本质：按距离分层扩展，第 k 层包含所有距起点 k 步的状态。

BFS(start):
    queue.push(start); dist[start] = 0
    while queue 非空:
        u = queue.pop()
        对 u 的每个邻接 v:
            if v 未访问:
                dist[v] = dist[u] + 1
                queue.push(v)

BFS 在无权图中保证：首次到达某节点的路径即为最短路径。

3. DFS vs BFS 对比

特性	DFS	BFS
数据结构	栈 (递归调用栈)	队列 (queue)
空间复杂度	O(深度) 最坏 O(n)	O(宽度) 最坏 O(2^d)
适用场景	求所有方案、回溯	求最短步数、最少操作
找路径	找到的不一定最短	找到的一定最短

关键数据结构

B_栈_Stack — DFS 用栈 (递归调用栈)
F_队列_Queue — BFS 用队列逐层扩展
I_树_Tree_BST_AVL — 树的 DFS/BFS 遍历
H_图_Graph — 图上的搜索遍历

P1605 迷宫

题目: N×M 的迷宫，有 T 个障碍物。从起点到终点的方法总数，要求不经过障碍物且不重复走同一格。

思路: DFS 回溯，标记已访问的格子，到达终点则计数 +1。

#include <iostream>
using namespace std;
int n, m, t, sx, sy, fx, fy, ans;
int maze[10][10];
int vis[10][10];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
 
void dfs(int x, int y) {
    if (x == fx && y == fy) { ans++; return; }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m
            && !maze[nx][ny] && !vis[nx][ny]) {
            vis[nx][ny] = 1;
            dfs(nx, ny);
            vis[nx][ny] = 0;
        }
    }
}
 
int main() {
    cin >> n >> m >> t >> sx >> sy >> fx >> fy;
    for (int i = 0, x, y; i < t; i++) {
        cin >> x >> y;
        maze[x][y] = 1;
    }
    vis[sx][sy] = 1;
    dfs(sx, sy);
    cout << ans << endl;
    return 0;
}

P1443 马的遍历

题目: N×M 的棋盘，马在起点 (x,y) 走日字。求马到达棋盘上每个点的最少步数。

思路: BFS 从起点出发，逐层扩展，记录每个格子最短步数。

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
 
int n, m, dist[405][405];
int dx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int dy[] = {-1, 1, -2, 2, -2, 2, -1, 1};
 
int main() {
    memset(dist, -1, sizeof(dist));
    int sx, sy;
    cin >> n >> m >> sx >> sy;
    queue<pair<int,int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            printf("%-5d", dist[i][j]);
        printf("\n");
    }
    return 0;
}

P2404 自然数拆分

题目: 将自然数 n 拆分成若干个大于 0 的自然数之和，按字典序输出所有拆分方案。

思路: DFS 递归拆分，用数组记录当前拆分数，从小到大选数避免重复。

#include <iostream>
using namespace std;
int n, a[15];
 
void dfs(int sum, int pre, int idx) {
    if (sum == n) {
        cout << n << "=";
        for (int i = 0; i < idx; i++) {
            if (i) cout << "+";
            cout << a[i];
        }
        cout << endl;
        return;
    }
    for (int i = pre; i <= n - sum && i < n; i++) {
        a[idx] = i;
        dfs(sum + i, i, idx + 1);
    }
}
 
int main() {
    cin >> n;
    dfs(0, 1, 0);
    return 0;
}

P2392 kkksc03考前临时抱佛脚

题目: 有 4 科，每科有 s_i 道题，每道题需要 t_i 时间。每科可以同时开始做，但同一科只能一道一道做。问完成所有题的最短时间。

思路: 对每科使用 01 背包的思想，将题目分成两组使得两组时间差最小（即尽量平均分配）。

#include <iostream>
#include <cstring>
using namespace std;
int s[5], t[25], dp[1205];
 
int main() {
    for (int i = 0; i < 4; i++) cin >> s[i];
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        int sum = 0;
        for (int j = 0; j < s[i]; j++) {
            cin >> t[j];
            sum += t[j];
        }
        memset(dp, 0, sizeof(dp));
        for (int j = 0; j < s[i]; j++)
            for (int k = sum / 2; k >= t[j]; k--)
                dp[k] = max(dp[k], dp[k - t[j]] + t[j]);
        ans += sum - dp[sum / 2];
    }
    cout << ans << endl;
    return 0;
}

RootStack

探索

C++ 算法技巧 — 搜索 (Search: DFS & BFS)

章节概述

核心原理

关键数据结构

P1605 迷宫

P1443 马的遍历

P2404 自然数拆分

P2392 kkksc03考前临时抱佛脚

推荐练习题（洛谷）

相关技巧

多平台练习

关系图谱

目录

反向链接