图论基础与遍历算法：BFS 与 DFS

3. 经典模板

void dfs(int step) {
    if (到达目的地) {
        // 边界判定：满足最终条件，终止递归
        输出当前解;
        return;
    }
    合理剪枝; // 减少无效搜索，排除不可能的路径
    for (int i=1; i<=枚举范围; i++) {
        // 枚举当前步骤的所有可能选择
        if (当前选择满足约束条件) {
            // 筛选合法选择
            更新状态位; // 记录当前选择，修改全局/局部状态
            dfs(step+1); // 递归深入，进入下一步
            恢复状态位; // 回溯：撤销当前选择，恢复状态，尝试其他可能
        }
    }
}

4. 算法适用场景

路径搜索、组合排列、连通性分析等需要回溯尝试所有可能的场景。

（二）广度优先搜索（BFS）

1. 核心思想

'逐层扩散'，从起始顶点开始，先访问所有相邻顶点（第一层），再依次访问相邻顶点的邻接顶点（第二层），直至遍历完成。

2. 三大关键要点

• 避免重复：同 DFS，需用数组标记已访问节点，防止循环遍历。
• 队列依赖：通过队列存储待访问节点，遵循'先进先出'（FIFO）规则，确保逐层遍历的顺序。
• 边界判定：检查节点是否越界、是否为有效节点，避免非法内存访问。

3. 经典模板

// 初始化队列，存入起始状态
queue<数据类型> q;
q.push(初始状态);
标记初始状态为已访问;
while (!q.empty()) {
    // 队列非空表示还有待访问节点
    取出队头节点并弹出; // 读取当前待处理节点
    枚举当前节点的所有可达状态/相邻节点;
    for (每个可达状态 v) {
        if (v 合法且未被访问) {
            // 筛选合法未访问节点
            标记 v 为已访问; // 立即标记，避免重复入队
            q.push(v); // 合法节点入队，等待后续处理
            按需更新结果/状态;
        }
    }
}

4. 算法适用场景

无权图最短路径、层级遍历、区域统计等需要按距离/层级推进的场景。

四、题目与题解

（一）组合的输出（基础 DFS 例题）

题目描述

题解代码

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

int n, m;
vector<int> chosen;

void dfs(int x) {
    // 剪枝操作：减少无效递归，提升效率
    if (chosen.size() > m || chosen.size() + n - x + 1 < m) return;
    
    if (chosen.size() == m) {
        for (int i = 0; i < chosen.size(); i++) {
            cout << setw(3) << chosen[i];
        }
        puts("");
        return;
    }
    
    // 第一种选择：选取当前数字 x
    chosen.push_back(x);
    dfs(x + 1);
    chosen.pop_back();
    
    // 第二种选择：不选取当前数字 x
    dfs(x + 1);
}

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

（二）30×60 数字矩阵最大连通分块（DFS 连通性例题）

题目描述

小蓝有一个 30 行 60 列的数字矩阵，矩阵中的每个数都是 0 或 1。如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置，则称两个位置连通。与某一个标为 1 的位置连通的所有位置（包括自己）组成一个连通分块。请问矩阵中最大的连通分块有多大？

运行限制

• 最大运行时间：1s
• 最大运行内存：256M

题解代码

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

const int N = 1010;
char g[N][N];
int n = 30;
int m = 60;
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};

int dfs(int x, int y) {
    if (g[x][y] == '0') return 0;
    g[x][y] = '0';
    int ans = 1;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
        ans += dfs(nx, ny);
    }
    return ans;
}

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

（三）红与黑（BFS 区域统计例题）

题目描述

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

输入格式

输入包括多个数据集合。每个数据集合的第一行是两个整数 W 和 H，分别表示 x 方向和 y 方向瓷砖的数量。在接下来的 H 行中，每行包括 W 个字符。每个字符表示一块瓷砖的颜色，规则如下：

1. .：黑色的瓷砖；
2. #：红色的瓷砖；
3. @：黑色的瓷砖，并且你站在这块瓷砖上。 当在一行中读入的是两个零时，表示输入结束。

输出格式

对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数。

数据范围

1 ≤ W, H ≤ 20

输入样例

6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0

输出样例

45

题解代码

#include<iostream>
#include<queue>
#include<string>
using namespace std;

const int N = 25;
char g[N][N];
int n, m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

struct node {
    int x, y;
};

int bfs(int sx, int sy) {
    int res = 0;
    queue<node> q;
    q.push({sx, sy});
    g[sx][sy] = '#';
    
    while (q.size()) {
        node tmp = q.front();
        q.pop();
        res++;
        
        for (int i = 0; i < 4; i++) {
            int x = tmp.x + dx[i];
            int y = tmp.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] == '#') continue;
            q.push({x, y});
            g[x][y] = '#';
        }
    }
    return res;
}

int main() {
    while (cin >> m >> n && (m | n)) {
        for (int i = 0; i < n; i++) cin >> g[i];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == '@') ans = bfs(i, j);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

（四）路径之谜（DFS 剪枝进阶例题）

题目描述

小明冒充 XX 星球的骑士，进入了一个奇怪的城堡。城堡里边什么都没有，只有方形石头铺成的地面。假设城堡地面是 n×n 个方格。按习俗，骑士要从西北角走到东南角。可以横向或纵向移动，但不能斜着走，也不能跳跃。每走到一个新方格，就要向正北方和正西方各射一箭。（城堡的西墙和北墙内各有 n 个靶子）同一个方格只允许经过一次。但不必走完所有的方格。如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？

本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）。

输入描述

第一行一个整数 N (0≤N≤20)，表示地面有 N×N 个方格。 第二行 N 个整数，空格分开，表示北边的箭靶上的数字（自西向东）。 第三行 N 个整数，空格分开，表示西边的箭靶上的数字（自北向南）。

输出描述

输出一行若干个整数，表示骑士路径。 为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号：0,1,2,3 ⋯⋯

输入输出样例

示例

输入：

4 2 4 3 4 4 3 3 3 

输出：

0 4 5 1 2 3 7 11 10 9 13 14 15 

运行限制

• 最大运行时间：5s
• 最大运行内存：256M

题解代码

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

int n;
int s[1000];
int z[1000];
int res[100000];
int book[100][100];
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void dfs(int x, int y, int dep, int s[], int z[], int &tep) {
    if (tep == 1) return;
    
    if (x == n - 1 && y == n - 1) {
        for (int i = 0; i < n; i++) {
            if (s[i] != 0 || z[i] != 0) return;
        }
        tep = 1;
        for (int i = 0; i < dep; i++) printf("%d ", res[i]);
        return;
    }
    
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        
        if (book[tx][ty] == 1 || tx < 0 || tx > n - 1 || ty < 0 || ty > n - 1 || s[ty] - 1 < 0 || z[tx] - 1 < 0) continue;
        
        res[dep] = tx * n + ty;
        book[tx][ty] = 1;
        s[ty]--;
        z[tx]--;
        
        dfs(tx, ty, dep + 1, s, z, tep);
        
        book[tx][ty] = 0;
        s[ty]++;
        z[tx]++;
    }
    return;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < n; i++) cin >> z[i];
    
    book[0][0] = 1;
    s[0]--;
    z[0]--;
    
    int tep = 0;
    dfs(0, 0, 1, s, z, tep);
    return 0;
}

五、关键总结与学习心得

1. 存储选型：稠密图优先用邻接矩阵，稀疏图优先用邻接表，核心是平衡空间与查询效率。
2. 算法选型：DFS 适合回溯求所有可能（组合、路径），BFS 适合逐层求最短/区域（无权图、瓷砖统计），剪枝是 DFS 提升效率的关键。
3. 核心规范：无论是 DFS 还是 BFS，都必须先做边界判断、再标记访问、最后处理逻辑，这是避免程序出错的核心要点。
4. 路径之谜核心技巧：二维坐标与格子编号的互转（pos=x×n+y）、箭靶数量的检查与回溯，是解决此类网格路径问题的通用方法。